When should I use dual Simplex over primal Simplex?

Question

In Gurobi the user can change the method parameter in order to force Gurobi to use a particular method for solving MIPs. The user can, amongst others, choose between primal and dual simplex (not changing the parameter will result in Gurobi picking the method for you).

Are there any kinds of problems in which a user should manually pick primal or dual simplex instead of letting Gurobi figuring this out on its own?

Answer 1

Not an expert on simplex, but here's my attempt on an answer:

In general, the solution of the (previous) LP Relaxation will no longer be primal feasible when the primal LP is tightened (e.g. new cut in branch & bound).

In the dual simplex, new primal cuts correspond to new dual variables, which are initialized as nonbasic, and thus the previous solution is still dual feasible. Thus dual simplex does not need to regain feasibility.

So in a mixed-integer-programming context, dual simplex will usually outperform primal simplex.

In general it is easier to get dual feasibility than primal feasibility, and dual simplex appears to make more progress in many iterations.

Many commercial solvers also offer Barrier methods to solve LP(-Relaxations). The big drawback of interior point methods is that they can't really be warmstarted, and when solving mixed-integer-programmes using branch & bound are generally given a reasonable warm/hot-start (the solution of the previous LP Relaxation).

I've seen a recommendation before that stated that one can use IPMs to solve the root node of the MIP, and then use dual simplex afterwards. See Jakob's answer on how to do that in Gurobi.

Answer 2

Dual simplex is the method of choice for resolving an LP if you have an optimal solution and you change the problem by modifying the feasible region. Ranging the RHS, adding cuts or branching in MIP, Benders decomposition, etc. are examples where that happens. Some other problems are easy to start in the dual method, for example, when all variables have finite upper and lower bounds.

Dual simplex is often applied more successfully in combinatorial problems, where degeneracy is an issue for the primal algorithm. For example, in a collection of assignment constraints, there are $2n$ constraints but only $n$ nonzero variables in any basic solution. (There are more efficient methods for pure assignment problems, but the assignment structure is often a component of more complex problems.)

I believe that most industrial solvers now default to the dual algorithm even for general problems. There are effective dual phase-1 procedures and dual steepest-edge pricing, which make the method work well in general.

Answer 3

In addition to @Michael's comment you have to distinguish between the algorithm used to solve the root node of a problem and the algorithm used for the nodes in the branch-and-bound tree.

gurobi (and very likely also other commercial solvers) offer parameters to specify this separately:

• Method for changing the algorithm used at the root node. If you have enough RAM you can use the deterministic or even non-deterministic mode to use all three methods and use the solution from the algorithm that solves it the quickest.
• NodeMethod for changing the algorithm used at the B&B-nodes.
• One additional special case: MIQCPMethod for Mixed-integer-quadratically-constraint problems. Here you can choose between a linearized outer approximation (which is solved via dual simplex) and usage the barrier method.

In my experience the automatic choice of gurobi does a pretty good job, but if you have doubts you could try the parameter tuning tool. I've only encountered one case where the the problem in the B&B nodes were so big that using barrier was actually faster than using dual simplex.