Solving the continuous relaxation

Getting that first feasible solution to the continuous relaxation of a MIP can often be quite hard. It is always worth trying the three main LP algorithms available in the Xpress Optimizer: primal simplex, dual simplex and barrier. These LP algorithms are not selected through a control but are instead specified as options to the lpoptimize and mipoptimize commands. Use one of the following options to force a particular algorithm selection:

Note that primal and dual simplex cannot be applied to a continuous problem with quadratic or conic constraints. Barrier will always be used on such problems, irrespective of any options you specify.

The default choice of algorithm for a linear MIP depends on the number of threads you are solving a problem with. Dual simplex is always the default choice for a single-threaded solve. When more threads can be started, the Xpress Optimizer will run a concurrent LP solve, where it starts primal simplex, dual simplex and barrier in parallel. It stops with the first one to solve the continuous relaxation. There is some overhead in running all of the algorithms in parallel, so if one particular algorithm always comes up as the winner, it is better to simply force that one to always be run on its own. The concurrent LP solve can be enabled or disabled by setting the CONCURRENTTHREADS control to either the number of threads, or 1, respectively.

On some MIPs, the choice of the initial algorithm has an effect beyond just the time to solve the initial continuous relaxation. If the relaxation has many optimal solutions (what is known as dual degeneracy), the choice of algorithm will also affect which of these optional solutions is found. In general, barrier will find a more fractional solution and primal simplex will find a least fractional solution. This can substantially affect the subsequent cutting and heuristics.

For dual simplex the main controls to consider are DUALGRADIENT and PERTURB. The DUALGRADIENT control specifies how dual simplex selects its pivots and can be a value from 0 to 3, with -1 leaving the choice to the Optimizer. Dual simplex uses cost perturbation to get out of a "sticky" solution. The PERTURB control is used to specify the initial random perturbation to apply to the objective function, which can be useful for dual degenerate problems. Note that since dual simplex is also the default algorithm for reoptimizing the continuous relaxation of any sub-problem while solving a linear MIP, setting PERTURB will affect the whole MIP solve.

With primal simplex, the main control is PRICINGALG. The values to try here are from -1 to 3.

Continuous Solve Controls Summary

-p, -d, -b options

Options for lpoptimize/ mipoptimize to select the algorithm when solving the initial continuous relaxation: primal simplex, dual simplex or barrier.

CONCURRENTTHREADS

Number of threads to use for a concurrent LP solve.

DUALGRADIENT

Dual simplex pivot selection strategy (0 3).

PRICINGALG

Primal simplex pivot selection strategy (-1 3)

PERTURB

Initial perturbation value for each continuous solve (try 0 for none, or e.g. 1e-4).