Modifications and implementation of the ellipsoid algorithm for linear programming

Donald Goldfarb, Michael J. ToddMath. Program 1982 · OpenReview

Abstract

We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.
BibTeX
@inproceedings{goldfarb1982modifications,
  author = {Donald Goldfarb and Michael J. Todd},
  title = {{Modifications and implementation of the ellipsoid algorithm for linear programming}},
  booktitle = {Math. Program},
  year = {1982},
  url = {https://openreview.net/forum?id=NsPwRL0Brb},
}

Loading related content...

Figure