Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint. Is it possible to use the calculated optimal solution to do it in some clever way? Obviously, if the optimal solution still satisfies that new constraint, it will still be optimal and we are fine, so assume it does not satisfy the new constraint. Now, a constraint basically defines a hyperplane in the solution space, so I've been thinking that it might be useful to project the optimal solution onto the new hyperplane, but then this projection might still not be feasible and so we cannot yet apply the Simplex Algorithm to it...

This question is motivated by the problem that appears when we have a lot of constraints but we know that probably not all of them are necessary, so some of those halfspaces are included in others, there is a lot of redundacy. So to speed up the computation, we only iteratively add new constraints and want to iteratively compute the optimal solution to the problem with all constraints, instead of doing it all in one shot.

I don't care about the Worst Case Complexity as much as about the Average Case Complexity (for example, assuming the uniform distribution over all inputs)!

3more comments