4
$\begingroup$

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)!

$\endgroup$
  • 5
    $\begingroup$ In general (worst case), it will be just as hard to compute the new solution if you know the old solution as if you don't know the old solution. Simple example is: new problem feasible region is a polytope in (n-1) dimesnions; old problem feasible region is cone (pyramid) with new region as base. Suppose objective weighs going orthogonal to base heavily, then old solution would always be apex, giving you no information about the new problem. $\endgroup$ – Yoav Kallus Oct 17 '17 at 23:19
  • 4
    $\begingroup$ Maybe switch to the dual linear program, for which the old solution still works, and use it as an initial guess for the new problem? $\endgroup$ – Noam D. Elkies Oct 18 '17 at 0:14
  • 2
    $\begingroup$ That is done routinely with the exponentially many subtour elimination constraints in the ILP formulation of the TSP. $\endgroup$ – Manfred Weis Oct 18 '17 at 3:59
  • 6
    $\begingroup$ The method you describe is called column generation (applied to the dual problem). $\endgroup$ – Thomas Kalinowski Oct 18 '17 at 5:27
  • $\begingroup$ Yoav Kallus: What does apex mean exactly? I meant we don't have to project the old solution anywhere, maybe doing something else is more appropriate. D. Elkies: Sounds good but if this really works well, then why isn't this approach always used to find an initial feasible solution, if we take the zero vector then it is feasible for one of the primal or dual.. Manfred Weis: This is exactly the application I had in mind, yes. Thomas Kalinowski: This sounds really good! Could you give a link to a more detailed explanation of that than the one in Wikipedia? $\endgroup$ – D. Rusin Oct 18 '17 at 10:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.