I have a problem that I modeled as an LP with an exponential number of constraints, then proved a linear time time separability oracle which translates to a weakly polynomial time algorithm for the problem.

However, the ellipsoid method is known to be numerically unstable and has poor performance in practice.

My question is, are there any practical alternatives to this that can run in poly time? It is not practical to define the LP with an exponential number of constraints for me (since the exponential parameter is really big) so I am a bit stuck on how to solve an instance of this problem in a "realistic" time frame.

  • 1
    $\begingroup$ Lagrangian relaxation methods handle LP's with exponentially many constraints, via the dual, which has exponentially many variables. Lagrangian relaxation works well for so-called packing and covering LPs, multicommodity flow being the prototypical example. Historically, column generation is a traditional approach for LPs with exponentially many variables. You may find that it is supported by existing LP solvers. $\endgroup$ – Neal Young Sep 28 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.