Why do we need specific linear programming methods now?

72 Views Asked by At

I've recently studied different methods of solving linear programming (LP) problems, like simplex method, Dantzig–Wolfe decomposition, Kornai–Liptak decomposition. I suppose all these methods were a breakthrough in the times they were proposed. But how and why are they used nowadays?

I've seen examples and solved some homework problems using these methods, but with a small number of variables (like 4-6) and agree that such ways of solving those problems can be easier than "conventional" ones (like Lagrange multipliers), but in general they give just another method of solving LP problems by hand. But real-world LP problems have a lot more variables and constraints and I doubt it's reasonable to solve them with pen and paper. So, such problems are solved using computers, but again, numerical implementations of LP-specific methods are often used.

So, my main question is: what's the reason to use numerical simplex method or other LP-solvers instead of some conventional constrained numerical optimiziation methods (like projection method or penalty method)?

1

There are 1 best solutions below

0
On

The simplex is part of the active-set methods: it "guesses" the set of active constraints (= a vertex of the feasible set), then refines this guess over time. At each iteration, there's usually a single constraint updated, so it might take a while to converge.
Gradient projection allows you to modify the active set more aggressively.
Interior-point methods somehow move through the interior of the feasible set (that is, not from vertex to vertex).
Depending on your problem (number of inequality constraints, warmstart or not, ...), one of the methods may prevail over the others.

By "Lagrange multiplier method", do you mean solving the optimality (KKT) conditions? In the presence of inequality constraints, you're still left with a lot of decisions to make ("is this constraint active or inactive at the solution?")... which is essentially what active-set methods do :)