8
$\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.)

Improve this question
$\endgroup$
5
  • $\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, 2015 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, 2015 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, 2015 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, 2020 at 13:00
  • 1
    $\begingroup$ See also cstheory.stackexchange.com/q/51003/8237. As one answer there discusses, packing/covering LP's can be $(1+\epsilon)$-approximately solved by Lagrangian-relaxation / multiplicative-weights-update algorithms, which can work with separation oracles. The run times are practical if $\epsilon$ is not too small. $\endgroup$
    – Neal Young
    Jan 25, 2022 at 14:52

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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