18
$\begingroup$

When solving a Linear Optimization model (or Linear Program), there are a lot of solution approaches.

Just to name a few:

  • Primal Simplex
  • Dual Simplex
  • Ellipsoid Method (as if)
  • Interior Point Method

When should I use the Interior Point Method?
Is it just a matter of trial-and-error numerically or are there some indicators within a problem that point to preferred approaches?

I understand that the default for many solvers is to automatically choose for you unless you specify.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Interior point methods are usually better for large (sparse) problems I think. Modern solvers (Gurobi, CPLEX) choose for you (and do a good job of it, in my experience). I think they even run interior point and dual simplex concurrently sometimes. $\endgroup$
    – David M.
    Jun 12, 2019 at 21:56
  • $\begingroup$ @DavidM., I've used both Gurobi and CPLEX but never knew they might run two approaches concurrently. Thanks! $\endgroup$
    – SecretAgentMan
    Jun 12, 2019 at 22:08
  • 5
    $\begingroup$ When to use the Ellipsoid Method ? Never. $\endgroup$
    – Mark L. Stone
    Jun 13, 2019 at 1:11
  • $\begingroup$ Related: or.stackexchange.com/q/282/87 $\endgroup$
    – Marcus Ritt
    Jun 13, 2019 at 7:17

2 Answers 2

Reset to default
18
$\begingroup$

Let's start with the easy one:

Ellipsoid Method

Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues.

Primal Simplex

Mostly studied for historical interest, but there are some cases where it might outperform dual simplex (when the basis matrix in the primal revised simplex is of significantly lower dimension than in the dual revised simplex, I think). Worst case exponential time, but never happens in practice.

Dual Simplex

Usually the default choice in modern Linear Programming Solvers. Can be warmstarted and hotstarted, easy to get feasibility, and preserves dual feasibility when tightening the primal LP (such as in a MILP environment). See this question and answer for more details on this. Worst case exponential time, but extremely efficient in practice. Can efficiently exploit sparsity in the constraint matrix. One of the reasons dual simplex implementation outperform primal simplex is the Dual Steepest Edge technique, which apparently is not directly applicable to the primal algorithm. The availability of the bound flipping ratio test also adds to the superiority of the dual over the primal method.

Both primal and dual simplex will produce a basic solution (at a vertex of the feasible region).

Interior Point Method

Provable polynomial complexity. Often needs a preconditioner to perform extremely well. Can not really be warmstarted, so not much use in a MILP environment apart from solving the root node. Performs competitively when you don't know much about a problem (e.g. no warm/hotstart available). IPMs do not generally produce a basic solution (at a vertex of the feasible region).

Rule of thumb: You're usually not terribly wrong by using dual revised simplex, especially if a warm- or hotstart is available. Occasionally it can be beneficial to use interior point methods, when you don't have a hotstart but maybe a decent preconditioner for the IPM system matrix.

Example: Use IPM to solve the root node of a MIP, use Dual Simplex to solve the other nodes.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ This is a great, succinct summary. $\endgroup$
    – LarrySnyder610
    Jun 13, 2019 at 12:29
  • 2
    $\begingroup$ Good summery. What should be added is that solutions from simplex and interior point methods (without crossover) are "different in nature". Simplex algorithms produce basic solutions that have many variables at their bounds while interior point methods result in dense, more evenly distributed solutions. In some applications one or the other might be preferred. $\endgroup$
    – Philipp Christophel
    Jun 17, 2019 at 7:10
  • 2
    $\begingroup$ Another reason that could be added regarding why the dual simplex performs better than primal is that for problems with boxed variables (variables have lower and upper bounds) the dual does not need a phase 1 and can do a bound flipping ratio test (sometimes called "long step"). $\endgroup$
    – Philipp Christophel
    Jun 17, 2019 at 7:19
  • $\begingroup$ thanks for the comments, I will add it to the answer for future reference $\endgroup$
    – Michael Feldmeier
    Jun 17, 2019 at 18:47
9
$\begingroup$

Bob Bixby (as just one representative of many computational guys) talks regularly about progress in LP and MIP solving; for the 50th anniversary issue of "Operations Research" he wrote an article on history and progress in LP solving that also contains perspectives on different algorithms (here), his general message is: these algorithms became vastly more powerful over the years, no matter which one is actually used; a related question is also on SE.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Thank you for the information. It would be better if you could edit your answer to include a summary of what is available at the links (and relevant takeaways) to maximize value to future users in the event of "link rot." Thanks for your answer! $\endgroup$
    – SecretAgentMan
    Jun 17, 2019 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.