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, hybrid gradient 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:

> mipoptimize -p Primal simplex
 
> mipoptimize -d Dual simplex
 
> mipoptimize -b Barrier or Hybrid gradient (if BARALG is set to 4)

Note that primal simplex, the dual simplex and the hybrid gradient methods cannot be applied to a continuous problem with quadratic or conic constraints. The Optimizer will always solve such problems with the Barrier algorithm, irrespective of any control specifications.

The default choice of algorithm for a linear MIP depends on the number of threads. 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 (or hybrid gradient) 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. Thus, if one particular algorithm always comes up as the winner, it is better to force that one to always be run on its own. Besides the options above, a particular algorithm can also be forced by setting LPFLAGS to 1 (for dual), 2 (for primal), or 4 (for barrier). If the overhead is mostly in synchronization, you can try to set DETERMINISTIC to 2, as an intermediate way of avoiding a long waiting time without enforcing a certain algorithm but keeping the main MIP search deterministic.

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

For dual simplex the main controls to consider are DUALGRADIENT and DUALPERTURB. 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 DUALPERTURB 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 DUALPERTURB will affect the whole MIP solve. DUALSTRATEGY is relevant for numerically challenging problems, since it determines how cycling is handled.

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 (or hybrid gradient).

BARALG

Set it to 4 to use the hybrid gradient method instead of the Newton barrier algorithm.

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)

DUALPERTURB

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