- Linear Programming FAQ

 Home >  Programming >

Linear Programming FAQ

Section 1 of 3 - Prev - Next
All sections - 1 - 2 - 3

Posted-By: auto-faq 2.4
Archive-name: linear-programming-faq
Last-modified: November 1, 1997

[ ]

        Linear Programming
        Frequently Asked Questions

Optimization Technology Center of
Northwestern University and Argonne National Laboratory
[ ] Posted monthly to Usenet newsgroup sci.op-research

World Wide Web version:
Plain-text version:

Date of this version: November 1, 1997

   * Q1. "What is Linear Programming?"
   * Q2. "Where is there good software to solve LP problems?"
        o "Free" codes
        o Commercial codes and modeling systems
        o Free demos of commercial codes
   * Q3. "Oh, and we also want to solve it as an integer program."
   * Q4. "I wrote an optimization code. Where are some test models?"
   * Q5. "What is MPS format?"
   * Q6. Topics briefly covered:
        o Q6.1: "What is a modeling language?"
        o Q6.2: "How do I diagnose an infeasible LP model?"
        o Q6.3: "I want to know the specific constraints that contradict
          each other."
        o Q6.4: "I just want to know whether or not a feasible solution
        o Q6.5: "I have an LP, except it's got several objective functions."
        o Q6.6: "I have an LP that has large almost-independent matrix
          blocks that are linked by a few constraints. Can I take advantage
          of this?"
        o Q6.7: "I am looking for an algorithm to compute the convex hull of
          a finite number of points in n-dimensional space."
        o Q6.8: "Are there any parallel LP codes?"
        o Q6.9: "What software is there for Network models?"
        o Q6.10: "What software is there for the Traveling Salesman Problem
        o Q6.11: "What software is there for the Knapsack Problem?"
        o Q6.12: "What software is there for Stochastic Programming?"
        o Q6.13: "I need to do post-optimal analysis."
        o Q6.14: "Do LP codes require a starting vertex?"
        o Q6.15: "How can I combat cycling in the Simplex algorithm?"
   * Q7. "What references and Web links are there in this field?"
   * Q8. "How do I access the Netlib server?"
   * Q9. "Who maintains this FAQ list?"

See also the following pages
pertaining to mathematical programming and optimization modeling:

   * The related Nonlinear Programming FAQ.
   * The NEOS Guide to optimization models and software.
   * The Decision Tree for Optimization Software by H.D. Mittelmann and P.
   * Jiefeng Xu's List of Interesting Optimization Codes in the Public
   * Software for Optimization: A Buyer's Guide by Robert Fourer.
   * Harvey Greenberg's Mathematical Programming Glossary.

[ ]

Q1. "What is Linear Programming?"

A: (For rigorous definitions and theory, which are beyond the scope of this
document, the interested reader is referred to the many LP textbooks in
print, a few of which are listed in the references section.)

A Linear Program (LP) is a problem that can be expressed as follows (the
so-called Standard Form):

    minimize   cx
    subject to Ax  = b
                x >= 0

where x is the vector of variables to be solved for, A is a matrix of known
coefficients, and c and b are vectors of known coefficients. The expression
"cx" is called the objective function, and the equations "Ax=b" are called
the constraints. All these entities must have consistent dimensions, of
course, and you can add "transpose" symbols to taste. The matrix A is
generally not square, hence you don't solve an LP by just inverting A.
Usually A has more columns than rows, and Ax=b is therefore quite likely to
be under-determined, leaving great latitude in the choice of x with which to
minimize cx.

The word "Programming" is used here in the sense of "planning"; the
necessary relationship to computer programming was incidental to the choice
of name. Hence the phrase "LP program" to refer to a piece of software is
not a redundancy, although I tend to use the term "code" instead of
"program" to avoid the possible ambiguity.

Although all linear programs can be put into the Standard Form, in practice
it may not be necessary to do so. For example, although the Standard Form
requires all variables to be non-negative, most good LP software allows
general bounds l <= x <= u, where l and u are vectors of known lower and
upper bounds. Individual elements of these bounds vectors can even be
infinity and/or minus-infinity. This allows a variable to be without an
explicit upper or lower bound, although of course the constraints in the
A-matrix will need to put implied limits on the variable or else the problem
may have no finite solution. Similarly, good software allows b1 <= Ax <= b2
for arbitrary b1, b2; the user need not hide inequality constraints by the
inclusion of explicit "slack" variables, nor write Ax >= b1 and Ax <= b2 as
two separate constraints. Also, LP software can handle maximization problems
just as easily as minimization (in effect, the vector c is just multiplied
by -1).

The importance of linear programming derives in part from its many
applications (see further below) and in part from the existence of good
general-purpose techniques for finding optimal solutions. These techniques
take as input only an LP in the above Standard Form, and determine a
solution without reference to any information concerning the LP's origins or
special structure. They are fast and reliable over a substantial range of
problem sizes and applications.

Two families of solution techniques are in wide use today. Both visit a
progressively improving series of trial solutions, until a solution is
reached that satisfies the conditions for an optimum. Simplex methods,
introduced by Dantzig about 50 years ago, visit "basic" solutions computed
by fixing enough of the variables at their bounds to reduce the constraints
Ax = b to a square system, which can be solved for unique values of the
remaining variables. Basic solutions represent extreme boundary points of
the feasible region defined by Ax = b, x >= 0, and the simplex method can be
viewed as moving from one such point to another along the edges of the
boundary. Barrier or interior-point methods, by contrast, visit points
within the interior of the feasible region. These methods derive from
techniques for nonlinear programming that were developed and popularized in
the 1960s by Fiacco and McCormick, but their application to linear
programming dates back only to Karmarkar's innovative analysis in 1984.

The related problem of integer programming (or integer linear programming,
strictly speaking) requires some or all of the variables to take integer
(whole number) values. Integer programs (IPs) often have the advantage of
being more realistic than LPs, but the disadvantage of being much harder to
solve. The most widely used general-purpose techniques for solving IPs use
the solutions to a series of LPs to manage the search for integer solutions
and to prove optimality. Thus most IP software is built upon LP software,
and this FAQ applies to problems of both kinds.

Linear and integer programming have proved valuable for modeling many and
diverse types of problems in planning, routing, scheduling, assignment, and
design. Industries that make use of LP and its extensions include
transportation, energy, telecommunications, and manufacturing of many kinds.
A sampling of applications can be found in many LP textbooks, in books on LP
software systems, and among the application cases in the journal Interfaces.

[ ]

Q2. "Where is there good software to solve LP problems?"

A: Thanks to the advances in computing of the past decade, linear programs
in a few thousand variables and constraints are nowadays viewed as "small".
Problems having tens or hundreds of thousands of continuous variables are
regularly solved; tractable integer programs are necessarily smaller, but
are still commonly in the hundreds or thousands of variables and
constraints. The computers of choice for linear and integer programming
applications are Pentium-based PCs and the several varieties of Unix

There is more to linear programming than optimal solutions and
number-crunching, however. This can be appreciated by observing that modern
LP software comes in two related but very different kinds of packages:

   * Algorithmic codes are devoted to finding optimal solutions to specific
     linear programs. A code takes as input a compact listing of the LP
     constraint coefficients (the A, b, c and related values in the standard
     form) and produces as output a similarly compact listing of optimal
     solution values and related information.

   * Modeling systems are designed to help people formulate LPs and analyze
     their solutions. An LP modeling system takes as input a description of
     a linear program in a form that people find reasonably natural and
     convenient, and allows the solution output to be viewed in similar
     terms; conversion to the forms requried by algorithmic codes is done
     automatically. The collection of statement forms for the input is often
     called a modeling language.

Most modeling systems support a variety of algorithmic codes, while the more
popular codes can be used with many different modeling systems. Because
packages of the two kinds are often bundled for convenience of marketing or
operation, the distinction between them is sometimes obscured, but it is
important to keep in mind when attempting to sort through the many
alternatives available.

Large-scale LP algorithmic codes rely on general-structure sparse matrix
techniques and numerous other refinements developed through years of
experience. The fastest and most reliable codes thus represent considerable
development effort, and tend to be expensive except in very limited
demonstration or "student" versions. Those codes that are free -- to all, or
at least for research and teaching -- tend to be somewhat less robust,
though they are still useful for many problems. The ability of a code to
solve any particular class of problems cannot easily be predicted from
problem size alone; some experimentation is usually necessary to establish

Large-scale LP modeling systems are commercial products virtually without
exception, and tend to be as expensive as the commercial algorithmic codes
(again with the exception of small demo versions). They vary so greatly in
design and capability that a description in words is adequate only to make a
preliminary decision among them; your ultimate choice is best guided by
using each candidate to formulate a model of interest.

Listed below are summary descriptions of available free codes, and a
tabulation of many commercial codes and modeling systems for linear (and
integer) programming. A list of free demos of commercial software appears at
the end of this section.

Another useful source of information is the Optimization Software Guide by
Jorge More' and Stephen Wright, available from SIAM Books. It contains
references to about 75 available software packages (not all of them just
LP), and goes into more detail than is possible in this FAQ; see in
particular the sections on "linear programming" and on "modeling languages
and optimization systems." An updated Web version of this book is available
on the NEOS Guide. Another good soruce of feature summaries and contact
information is the Linear Programming Software Survey compiled by OR/MS
Today (which also has the largest selection of advertisements for
optimization software). Much information can also be obtained through the
web sites of optimization software developers, many of which are identified
in the writeup and tables below.

To provide some idea of the relative performance of LP codes, a Web page of
pointers to benchmarks for optimization software is being compiled by Hans
Mittelmann of Arizona State University. It currently includes tests of
several public-domain simplex and interior-point implementations. When
evaluating any performance comparison, however, whether performed by a
customer, vendor, or disinterested third party, keep in mind that all
high-quality codes provide options that offer superior performance on
certain difficult kinds of LP or IP problems. Benchmark studies of the
"default settings" of codes will fail to reflect the power of the optional
settings that are available.

"Free" codes

Some of these programs require registration or payment for some (especially
commercial) uses. Conditions of use are also subject to change. It is a good
practice to check a code's "readme" file or introductory documentation for
restrictions before committing to use it.

Based on the simplex method:

There is an ftp-able code, written in C, called lp_solve that its author
(Michel Berkelaar, email at says has solved models
with up to 30,000 variables and 50,000 constraints. The author requests that
people retrieve it from (numerical
address at last check: There is an older version to be
found in the Usenet archives, but it contains bugs that have been fixed in
the meantime, and hence is unsupported. The author also made available a
program that converts data files from MPS-format into lp_solve's own input
format; it's in the same directory, in file mps2eq_0.2.tar.Z. The
documentation states that it is not public domain, and the author wants to
discuss it with would-be commercial users. As an editorial opinion, I must
state that difficult models will give lp_solve trouble; it's not as good as
a commercial code. But for someone who isn't sure what kind of LP code is
needed, it represents a reasonable first try.

LP-Optimizer is a simplex-based code for linear and integer programs,
written by Markus Weidenauer ( Free Borland
Pascal 7.0 source is available for downloading, as are executables for DOS
and OS/2.

SoPlex is an object-oriented implementation of the primal and dual simplex
algorithms, developed by Roland Wunderling. Source code is available free
for research uses at noncommercial and academic institutions.

Among the SLATEC library routines is a Fortran sparse implementation of the
simplex method, SPLP, at Its
documentation states that it can solve LP models of "at most a few thousand
constraints and variables".

Based on interior-point methods:

The Optimization Technology Center at Argonne and Northwestern has developed
the interior-point code PCx. This code can be downloaded directly from the
PCx home page; it is freely available, except that you must contact Argonne
if you want to include it in a product for resale. A Windows 95/NT version
of PCx was announced in April 1997, and is available under the same
conditions as the original. (If you want to solve an LP without downloading
a code to your own machine, you can execute PCx remotely through the NEOS

A Fortran 77 interior-point code, BPMPD, has been developed by Csaba
Meszaros ( at the Computer and Automation Research
Institute of the Hungarian Academy of Sciences. It is available as source
code, as a Windows95/NT executable (which is also extended to solve convex
quadratic problems), and in a DLL version for Windows.

Jacek Gondzio ( has made source for his interior
point LP solver HOPDM available at Additionally,
several papers devoted to HOPDM code are available at this site. It uses a
higher order primal-dual predictor-corrector logarithmic barrier algorithm,
and according to David Gay, it "seems to work well in limited testing. For
example, it happily solves all of the examples in netlib's lp/data
directory." Prof. Gondzio notes that problem size is limited only by
available memory, and on a virtual memory system it has been used to solve
models with hundreds of thousand of constraints and variables. An older
version of the source code is kept in netlib's opt directory:

Other software of interest:

ABACUS is a C++ class library that "provides a framework for the
implementation of branch-and-bound algorithms using linear programming
relaxations that can be complemented with the dynamic generation of cutting
planes or columns" (branch-and-cut and/or branch-and-price). It relies on
CPLEX or SoPlex to solver linear programs. Further information is available
from Stefan Thienel,

A web-based service by a group at Berkeley called Interactive Linear
Programming appears to be useful for solving small models that can be
entered by hand. Along similar lines, the NEOS Guide offers a Java-based
Simplex Tool, which demonstrates the workings of the simplex method on small
user-entered problems and is especially useful for educational purposes.
Anima-LP by Chris Jones ( graphs and solves
two-dimensional linear programs interactively on any Java-compatible
browser; there is also a Macintosh version.

The Systems Analysis Laboratory at Seoul National University offers Linear
Programming software (both Simplex and Barrier) at

Will Naylor ( has a collection of software he calls
WNLIB. Routines of interest include
- simplex method for linear programming: contains anti-cycling and numerical
stability hacks. No optimization for sparse matrix.
- transportation problem/assignment problem routine: optimization for sparse
Read the INSTALL.txt file for further information. WNLIB also contains
routines pertaining to nonlinear optimization.

The next several suggestions are for public-domain codes that are severely
limited by the algorithm they use (tableau Simplex); they may be OK for
models with (on the order of) 100 variables and constraints, but it's
unlikely they will be satisfactory for larger models. In the words of Matt
Saltzman (

     The main problems with these codes have to do with scaling, use of
     explicit inverses and lack of reinversion, and handling of degeneracy.
     Even small problems that are ill-conditioned or degenerate can bring
     most of these tableau codes to their knees. Other disadvantages for
     larger problems relate to sparsity, pricing, and maintaining the
     complete nonbasic portion of the tableau. But for small, dense problems
     these difficulties may not be serious enough to prevent tableau codes
     from being useful, or even preferable to more "sophisticated" sparse
     codes. In any event, use them with care.

   * For DOS/PC users, there is an LP and Linear Goal Programming binary
     called tslin, at (the current file name is, using ZIP compression), or else I suggest contacting Prof.
     Salmi at . For North American users, the garbo server is
     mirrored on FTP site, in directory
   * Also on the garbo server is a file called, having a
     descriptor of "Linear Programming Optimizer by ScanSoft". It consists
     of PC binaries, and is evidently some sort of shareware (i.e., not
     strictly public domain).
   * There is an ACM TOMS routine for LP, #552, available at This routine was designed for
     fitting data to linear constraints using an L1 norm, but it uses a
     modification of the Simplex Method and could presumably be modified to
     satisfy LP purposes.
   * There are books that contain source code for the Simplex Method. See
     the section on references. You should not expect such code to be
     robust. In particular, you can check whether it uses a 2-dimensional
     array for the A-matrix; if so, it is surely using the tableau Simplex
     Method rather than sparse methods, and Saltzman's comments will apply.

For Macintosh users there is a free package called LinPro that is available
at Some users have reported that
it performs well, while one correspondent informs me he had trouble getting
it to solve any problems at all; perhaps this code is sensitive to memory
size of the machine. It comes with a "large example" of 100 variables, which
gives a hint of its design limits. It seems to be slower than commercial
codes, but that should not be a surprise (or a criticism of a free code).
LinPro has its own input format and does not support MPS format.

Walter C. Riley ( writes:

   * My shareware program, the R-Tek Scratchpad ( $15), is
     intended for teachers and students. It basically handles problems that
     students in an Introduction to Finite Mathematics course might
     encounter, including typical small textbook LP problems. Its primary
     advantages are that it uses readable math notation, handles fractions,
     and allows you to step through the problem to its solution. It is now
     available on the net for ftp download at or one of its mirror sites.

Stephen F. Gale ( writes:

   * Available at is a
     fairly simple Simplex Solver written for Turbo Pascal 3.0. The original
     algorithm is from the book "Some Common BASIC Programs" by Lon Poole
     and Mary Borchers (ISBN 0-931988-06-3). However, I revised it
     considerably when I converted it to Pascal. I then added Sensitivity
     Analysis based on the book "The Operations Research Problem Solver"
     (ISBN 0-87891-548-6). I have tested the program on over 30 textbook
     problems, but never used it for real life applications. If someone
     finds a problem with the program, I would be pleased to correct it. I
     would also appreciate knowing how the program was used.

The following suggestions may represent low-cost ways of solving LPs if you
already have certain software available to you.

   * All of the most popular spreadsheet programs offer an LP solver as a
     feature or add-in.
   * A package called QSB (Quantitative Systems for Business, from
     Prentice-Hall publishers) has an LP module among its routines.
   * If you have access to a commercial math library, such as SAS
     (919-677-8000), IMSL (800-222-4675 or 713-784-3131 or or NAG (708-971-2337), you may be able to use
     an LP routine from there.
   * Mathematical systems MATLAB (The Math Works, Inc., (508) 653-1415, see
     comment in the NLP FAQ) and MAPLE (Waterloo Maple Software, 450 Phillip
     Street, Waterloo, Ontario, Canada N2L 5J2 Phone: (519) 747-2373 Fax:
     (519) 747-5284) also have LP solvers. An interface from MATLAB to
     lp_solve is available from Jeff Kantor ( in A MATLAB toolkit
     for solving LP models using Interior-Point methods, called LIPSOL is
     available at - check the
     documentation in this directory (README.1ST) for more information; the
     current version is in subdirectory v0.3. There is an FTP site with
     user-contributed .m files to do Simplex located at There's a Usenet
     newsgroup on MATLAB: comp.soft-sys.matlab. If speed matters to you,
     then according to a Usenet posting by Pascal Koiran
     (, on randomly generated LP models, MATLAB was an
     order of magnitude faster than MAPLE on a 200x20 problem but an order
     of magnitude slower than lp_solve on a 50x100 problem. (I don't intend
     to get into benchmarking in this document, but I mention these results
     just to explain why I choose to focus mostly on special purpose LP

Commercial codes and modeling systems

If your models prove to be too difficult for free or add-on software to
handle, then you may have to consider acquiring a commercial LP code. Dozens
of such codes are on the market. There are many considerations in selecting
an LP code. Speed is important, but LP is complex enough that different
codes go faster on different models; you won't find a "Consumer Reports"
article to say with certainty which code is THE fastest. I usually suggest
getting benchmark results for your particular type of model if speed is
paramount to you. Benchmarking can also help determine whether a given code
has sufficient numerical stability for your kind of models.

Other questions you should answer: Can you use a stand-alone code, or do you
need a code that can be used as a callable library, or do you require source
code? Do you want the flexibility of a code that runs on many platforms
and/or operating systems, or do you want code that's tuned to your
particular hardware architecture (in which case your hardware vendor may
have suggestions)? Is the choice of algorithm (Simplex, Interior-Point)
important to you? Do you need an interface to a spreadsheet code? Is the
purchase price an overriding concern? If you are at a university, is the
software offered at an academic discount? How much hotline support do you
think you'll need? There is usually a large difference in LP codes, in
performance (speed, numerical stability, adaptability to computer
architectures) and in features, as you climb the price scale.

In the following table is a condensed version of a survey of LP software
that appeared in the June 1992 issue of OR/MS Today (a publication of
INFORMS) and that has subsequently been updated in the October 1995 and
April 1997 issues. Consult the full survey for more detailed information, or
click on the product names to browse their developers' web pages.

The table is in two parts, the first consisting of packages that are
primarily algorithmic codes, and the second containing modeling systems.
Product names are linked to product or developer web sites where known.

Under "Platform" is an indication of common environments in which the code
runs, with the choices being PC-DOS and/or versions of Microsoft Windows
(PC), Macintosh OS (M), and Unix on various computer types (U). For other
possibilities, check the full survey or contact the vendor.

Even more so than usual, I emphasize that you must use this information at
your own risk. I cannot guarantee that every entry is completely correct and
up-to-date, but I will gladly correct any mistakes that are pointed out to

Key to Features:  S=Simplex    I=Interior-Point or Barrier
                  Q=Quadratic  G=General-Nonlinear
                  M=MIP        N=Network

Product   Features Platform      Phone   E-mail address
CPLEX     SIMNQ    PC M U  702-831-7744
C-WHIZ    SM       PC U    703-412-3201
FortMP    SIMQ     PC U    630-971-2337

HI-PLEX   S        PC U              +44
HS/LP     SM       PC      201-627-1424
Planner   M        PC U    415-390-9000

LAMPS     SM       PC U              +44
LINDO     SMQ      PC      312-988-7422
LOQO      GI       PC U    609-258-0876
LPS-867   SM       PC U    609-737-6800
LS-XLSOL  SM       PC      702-831-0300
MINOS     SQG      PC      415-962-8719
MINTO     M        U       404-894-6287
MPSIII    SMN      PC U    703-412-3201
OSL       SIMNQ    PC U    914-433-4740
SAS/OR    SMNGQ    PC M U  919-677-8000

SCICONIC  SM       PC U              +44
SOPT      SIMGQ    PC U    732-264-4700
XA        SM       PC M U  818-441-1565
XPRESS-MP SIMQ     PC M    202-887-0296

Product        Platform          Phone   E-mail address
AIMMS          PC        +31 23-5350935
AMPL           PC U        702-322-7600
ANALYZE        PC          303-796-7830
DecisionPRO    PC          919-859-4101
DATAFORM       PC U        703-412-3201
GAMS           PC U        202-342-0180
LINGO          PC U        800-441-2378
MathPro        PC U        202-887-0296
MIMI           PC U        908-464-8300
MODLER         PC U        303-796-7830
MPL            PC          703-522-7900
OMNI           PC U        201-627-1424
VMP            PC U        301-622-4319
What's Best!   PC M U      800-441-2378
Visual XPRESS  PC          202-887-0296
                        +44 1604-858993

Free demos of commercial codes

An increasing number of commercial LP software developers are making demo or
academic versions available for downloading through web sites or as add-ons
to book packages. Typically these versions are limited in the size of
problem they accept or the length of time that they will operate, or are
made available only for "academic use" (mainly research or teaching at
universities). Nevertheless, they have most or all of the features of the
full versions. Most run under several variations of Microsoft Windows on
PCs, and/or certain Unix workstations; check the relevant web pages for

Downloadable free demos include:

   * AIMMS with XA and CONOPT
   * LINDO and What's Best!
   * LOQO with a built-in AMPL interface
   * MPL with CPLEX
   * Visual XPRESS with XPRESS-MP

Books that are packaged with demo software include:

   * A. Brooke, D. Kendrick and A. Meeraus, GAMS: A Users' Guide, Wadsworth
     Publishing Co/Duxbury Press, ISBN 0-894-26215-7.
   * R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Language for
     Mathematical Programming, Wadsworth Publishing Co/Duxbury Press, ISBN
   * H.J. Greenberg, Modeling by Object-Driven Linear Elemental Relations: A
     User's Guide for MODLER, Kluwer Academic Publishers, ISBN
   * L. Schrage, Optimization Modeling with LINDO, LINDO Systems, order
     directly from developer.

Many developers are also willing to arrange for you to "borrow" copies of
their full-featured versions for purposes of evaluation. Details vary,

Section 1 of 3 - Prev - Next
All sections - 1 - 2 - 3

Back to category Programming - Use Smart Search
Home - Smart Search - About the project - Feedback

© | Terms of use