7
$\begingroup$

I'm looking for an implementation of the ellipsoid algorithm for linear programming since the application I have in mind has the constraints represented as a separation oracle. Is such an implementation available anywhere?

If there isn't, is there maybe an implementation of the interior point method that works with a separation oracle? (I'm not sure IPM can work with a separation oracle, so it's possible that this part of the question is nonsense.)

$\endgroup$
4
  • $\begingroup$ I'm not aware of any such implementations that are practically usable. It's easy enough to cook up an implementation of the ellipsoid method in MATLAB but if you try to solve relatively small test problems (e.g. the afiro test problem from NETLIB which has about 50 constraints and 100 variables) you'll quickly discover the double precision arithmetic isn't up to the task. $\endgroup$ – Brian Borchers Dec 10 '15 at 15:15
  • $\begingroup$ Interior point methods don't work with a separation oracle, so that's out of the question. You might be interested in interior point cutting plane methods that effectively construct an LP as they go along. $\endgroup$ – Brian Borchers Dec 10 '15 at 15:15
  • $\begingroup$ @BrianBorchers Both your comments were very helpful, thank you. If you'd like credit for them, please post them as an answer. $\endgroup$ – G. Bach Dec 10 '15 at 16:01
  • 1
    $\begingroup$ A practical method is to used Delayed Column Generation: First solve the program without the constraints, then use the oracle to identify constraints that were violated, finally add those constraints to the program and solve again. $\endgroup$ – Thomas Ahle Oct 28 '20 at 13:00
11
$\begingroup$

Here's a longer answer that summarizes my earlier comments:

I'm not aware of any implementations of the ellipsoid algorithm that are practically usable for solving LP's. It's easy enough to cook up an implementation of the ellipsoid method in MATLAB but if you try to solve relatively small test problems (e.g. the afiro test problem from NETLIB which has about 50 constraints and 100 variables) you'll quickly discover the double precision arithmetic isn't up to the task. The problem is that the matrices involved become very ill-conditioned. If you want to play with this, I'd recommend starting with the discussion in Chavatal's Linear Programming textbook (there's an appendix on the ellipsoid method.)

Interior point methods for LP assume that the constraints are given and don't work with a separation oracle, so that's out of the question. However, you might be interested in interior point cutting plane methods that use similar ideas to effectively construct an LP outer relaxation of the feasible set as they go along.

There's a nice set of lecture notes on cutting plane approaches by Boyd and Vandenberghe at

https://web.stanford.edu/class/ee392o/localization-methods.pdf

The analytic center cutting plane method (ACCPM) of Goffin and Vial is perhaps the best known method of this type. See the code and references at

http://www.maths.ed.ac.uk/~gondzio/software/accpm.html

Although I'd recommend ACCPM, your problem could also be addressed by a variety of other approaches for general convex optimization problems such as subgradient descent, bundle methods, etc. My expertise is more in interior point methods for LP and conic optimization problems so you might get a better and more up to date answer from someone who works in this area.

$\endgroup$
1
  • $\begingroup$ Thank's for expanding this, I'll look through those resources! $\endgroup$ – G. Bach Dec 10 '15 at 16:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.