I'm looking to solve linear programs that have exponentially many constraints. Now, while that doesn't sound feasible, you can actually do that in polynomial time assuming you have a polytime algorithm that finds a violated constraint if one exists. However, you need the ellipsoid algorithm to make this work (possibly interior point).

Is there a commercial grade (or any assumed to be bug free) LP library that has an implementation of the ellipsoid algorithm? If the answer is no, which ones offer the best API for interior point methods?

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.