# Implementation of LP with separation oracle?

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

• 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. Dec 10, 2015 at 15:15
• 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. Dec 10, 2015 at 15:15
• 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. Oct 28, 2020 at 13:00
• 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. Jan 25 at 14:52

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.

• Thank's for expanding this, I'll look through those resources! Dec 10, 2015 at 16:59