Progressive Solving of Linear Programming Problem

Question

Suppose you solve a linear optimisation problem:

**Maximize:**
2a + 3b + 4c
**Subject to:**
3a + 5b + 2c <= 5
8a + 3b + 1c <= 8
C = 0

And then remove the C = 0 constraint and re-solve. (This could also be viewed as just adding a new variable).

My question is: Does already knowing the solution to the version with the constraint mean solving the problem without the constraint can be done quicker than if one had no such knowledge?

Note: When I say quicker, I mean in terms of computation time for commercial/free linear optimization solvers.

Answer 1

There is no guarantee in general. I could easily construct an example problem where an additional variable will mess up the original solution quite badly.

But the Simplex method traverses the extreme points of a polytope, one pivot per iteration, so it is reasonable to conjecture that IN GENERAL, starting the algorithm close to the previous optimum will require less iterations. All else being equal, it is still our best guess.