Linear Programming FAQ

The Linear Programming FAQ, established by John W. Gregory and maintained for many years by Robert Fourer, was last updated in 2005. Since the LP FAQ is no longer maintained, the content has been incorporated into the relevant sections of the NEOS Optimization Guide. Please follow the links below.

  1. What is Linear Programming?
  2. Where is there good software to solve LP problems?
  3. What software is available for solving integer linear programming problems?
  4. Where are some test problems for the optimization code that I wrote?
  5. What is MPS format?
  6. Topics briefly covered
    1. What is a modeling language? page under construction
    2. How can I determine whether or not an LP model has a feasible solution?
    3. How do I diagnose an infeasible LP model?
    4. How can I repair an infeasible LP model?
    5. How do I handle an LP with multiple objective functions?
    6. I have an LP that has large almost-independent matrix blocks that are linked by a few constraints. Are there solution methods that can exploit this structure?
    7. Are there algorithms available to compute the convex hull of a finite number of points in \(n\)-dimensional space?
    8. Are there parallel algorithms for solving LPs?
    9. How do I do sensitivity analysis/post-optimality analysis?
    10. Do LP algorithms require a starting vertex?
    11. How can I combat cycling in the Simplex Algorithms?
  7. What software is available for network models? page under construction
  8. What software is available for the Traveling Salesman Problem?
  9. What software is available for linear programming under uncertainty?
  10. What references are available?
  11. What resources are available online? page under construction