Newsgroups: news.answers,sci.answers,sci.op-research
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!grapevine.lcs.mit.edu!uhog.mit.edu!news.mtholyoke.edu!news.umass.edu!caen!math.ohio-state.edu!howland.reston.ans.net!news.sprintlink.net!uunet!in1.uu.net!timbuk.cray.com!walter.cray.com!jwg
From: jwg@cray.com (John Gregory)
Subject: Linear Programming FAQ
Message-ID: 
Followup-To: sci.op-research
Summary: A List of Frequently Asked Questions about Linear Programming
Originator: jwg@ceres
Keywords: FAQ, LP, Linear Programming
Lines: 1337
Nntp-Posting-Host: ceres.cray.com
Reply-To: jwg@cray.com (John Gregory)
Organization: Cray Research, Inc., Eagan MN USA
Date: 1 Apr 95 07:28:27 CST
Approved: news-answers-request@MIT.Edu
Expires: 05/03/95
Xref: senator-bedfellow.mit.edu news.answers:41116 sci.answers:2403 sci.op-research:3176

Posted-By: auto-faq 2.4
Archive-name: linear-programming-faq
Last-modified: March 1, 1995

Linear Programming - Frequently Asked Questions List
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Posted monthly to Usenet newsgroup sci.op-research
World Wide Web version:
http://www.skypoint.com/subscribers/ashbury/linear-programming-faq.html
Plain-text version:
ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq
Date of this version: April 1, 1995
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

"I'll bet with my [inter]net I can get those Things yet!" -- Dr. Seuss

 o Q1. "What is Linear Programming?"
 o Q2. "Where is there a good code to solve LP problems?"
 o Q3. "Oh, and we also want to solve it as an integer program."
 o Q4. "I wrote an optimization code. Where are some test
   models?"
 o Q5. "What is MPS format?"
 o Q6. "Just a quick question..."
 o Q7. "What references are there in this field?"
 o Q8. "How do I access the Netlib server?"
 o Q9. "Who maintains this FAQ list?"

See also the related Nonlinear Programming FAQ.


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.

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; there's no need to hide inequality constraints by the
inclusion of explicit "slack" variables, nor to write the same row
twice when it simply has a lower and upper bound on its sum. Also,
LP software can handle maximization problems just as easily as
minimization (in effect, the vector c is just multiplied by -1).

LP problems are usually solved by a technique known as the Simplex
Method, developed in the 1940's and after. Briefly stated, this
method works by taking a sequence of square submatrices of A and
solving for x, in such a way that successive solutions always improve,
until a point in the algorithm is reached where improvement is no
longer possible. A family of LP algorithms known as Interior-Point
(or Barrier) methods comes from nonlinear programming approaches
proposed in 1958 and further developed in the late 80's. These
methods can be faster for many (but so far not all) large-scale
problems. Such methods are characterized by constructing a sequence
of trial solutions that go through the interior of the solution space,
in contrast to the Simplex Method which stays on the boundary and
examines only the corners (vertices). Large-scale LP software,
whatever the algorithm, invariably uses general-structure sparse
matrix techniques.

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.

LP has a variety of uses, in such areas as petroleum, finance,
forestry, transportation, and the military.


Q2. "Where is there a good code to solve LP problems?"
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

A: Nowadays, with good commercial software (i.e., code that you
pay for), models with a few thousand constraints and several
thousand variables can be tackled on a 386 PC. Workstations can
often handle models with variables in the tens of thousands, or even
greater, and mainframes can go larger still. Public domain (free)
codes can be relied on to solve models of somewhat smaller
dimension. The choice of code can make more difference than the
choice of computer hardware. It's hard to be specific about model
sizes and speed, a priori, due to the wide variation in things like
model structure and variation in factorizing the basis matrices; just
because a given code has solved a model of a certain dimension, it
may not be able to solve *all* models of the same size, or in the same
amount of time.

There is a public domain code, written in C, called lp_solve that its
author (Michel Berkelaar, email at michel@es.ele.tue.nl ) says has
solved models with up to 30,000 variables and 50,000 constraints.
The author requests that people retrieve it from
ftp://ftp.es.ele.tue.nl/pub/lp_solve (numerical address at last check:
131.155.20.126). 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. 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
very reasonable first try, since it does solve non-trivial-sized
models, probably better than any other free code that you can get
source code for.

For academic users only, on a limited variety of platforms, there is
available a free version of LOQO, which is a linear/quadratic
program solver. Binary executables have been installed at
ftp://elib.zib-berlin.de/pub/opt-net/software/loqo. There are
versions for workstations by IBM, Silicon Graphics, HP, and Sun.
The package includes a subroutine library (libloqo.a), an executable
(loqo), the source for the main part of loqo (loqo.c), and associated
documentation (loqo.dvi and *.eps). The algorithm used is a
one-phase primal-dual-symmetric interior-point method. If you
wish to purchase a commercial version, please contact Bob
Vanderbei (rvdb@Princeton.EDU) for details.

Among the SLATEC library routines is a sparse implementation of
the Simplex method, in Fortran, available at
ftp://netlib2.cs.utk.edu/slatec/src/splp.f. Its documentation states
that it can solve LP models of "at most a few thousand constraints and
variables".

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.

 o For DOS/PC users, there is an LP and Linear Goal
   Programming binary called tslin, at ftp://garbo.uwasa.fi/pc/ts
   (the current file name is tslin34.zip, using ZIP compression),
   or else I suggest contacting Prof. Salmi at ts@uwasa.fi . For
   North American users, the garbo server is mirrored on FTP
   site wuarchive.wustl.edu, in directory mirrors/garbo.uwasa.fi.
 o Also on the garbo server is a file called lp261.zip, 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).
 o There is an ACM TOMS routine for LP, #552, available at
   ftp://netlib2.cs.utk.edu/toms/552. 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.
 o 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 it will not be useful for large models. But
   certainly, if your LP models are dense (and, perforce, small),
   such a code may be suitable, and even preferable over a more
   "sophisticated" sparse code; no snobbism is implied by any of
   these comments!

For Macintosh users there is a package called LinPro that is available
at ftp://ra.nrl.navy.mil/MacSciTech/programming/. 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.

The following suggestions may represent a low-cost way of solving
LP's if you already have certain software available to you.

 o Some spreadsheet programs have an embedded LP solver, or
   offer one as an installable option.
 o A package called QSB (Quantitative Systems for Business,
   from Prentice-Hall publishers) has an LP module among its
   routines.
 o If you have access to a commercial math library, such as SAS
   (919-677-8000), IMSL (800-222-4675 or 713-242-6776 or
   support@houston.vni.com) or NAG (708-971-2337), you
   may be able to use an LP routine from there.
 o Mathematical systems MATLAB (The Math Works, Inc.,
   (508) 653-1415, see comment in the NLP FAQ) and MAPLE
   (reference?) also have LP solvers. An interface from
   MATLAB to lp_solve is available from Jeff Kantor
   (Jeffrey.Kantor@nd.edu) in
   ftp://control.cheg.nd.edu/pub/Kantor/matlab/lp_solve. A
   MATLAB toolkit for solving LP models using Interior-Point
   methods, called LIPSOL is available at
   ftp://ftp.math.umbc.edu/pub/zhang/lipsol - check the
   documentation in this directory (currently in file
   release.beta-2.1) for more information; the current version is
   in subdirectory beta-2. There is an FTP site with
   user-contributed .m files to do Simplex located at
   ftp://ftp.mathworks.com/pub/contrib/optim/simplex1.
   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 (koiran@ens-lyon.fr),
   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 software.)

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.

At the end of this section is a *very* condensed version of a survey
of LP software published in the June 1992 issue of "OR/MS Today",
a joint publication of ORSA (Operations Research Society of
America) and TIMS (The Institute of Management Science). For
further information I would suggest you read the full article. It's
likely that you can find a copy, either through a library, or by
contacting a member of these two organizations (most universities
have probably several members among the faculty and student body).
This magazine also carries advertisements for many of these
products, which may give you additional information to help make a
decision.

In the table below, I give the name of the software and the phone
number listed in the June 1992 survey. Many of these companies have
toll-free (800) numbers, but for the benefit of people outside the US
I have listed an ordinary phone number where I know of it. To keep
the table short enough to fit here, I decided not to include postal
addresses. I have included, where I know of one, an email address
(information not given in the June 1992 survey), and other
information obtained from non-proprietary sources. For some
companies there may exist European or Asian contact points, but this
is beyond the scope of this document. Consult the full survey for
more information on contacting vendors.

The first part of the table consists of software I deem to be LP
solvers. The second part is software that in some sense is a front end
to the solvers (modeling software). In some cases it becomes a hazy
distinction, but I hope this arrangement of information turns out to
be useful to the reader.

Under "H/W" is the minimum hardware said to be needed to run the
code; generally I conceive of a hierarchy where PC's (and
Macintoshes) are the least powerful, then workstations (WS) like
Suns and RS-6000's, on up to supercomputers, so by the symbol "^" I
mean "and up", namely that most commonly-encountered platforms
are supported beyond the given minimum level. The code PC2 means
PC-286 and above, and PC3 means PC-386 and above.

Even more so than usual, I emphasize that you must use this
information at your own risk. I provide it as a convenience to those
readers who have difficulty in locating the OR/MS Today survey. I
take no responsibility for errors either in the original article or by
my act of copying it manually, though I will gladly correct any
mistakes that are pointed out to me.

Key to Features:  S=Simplex    I=Interior-Point or Barrier
                  Q=Quadratic  G=General-Nonlinear
                  M=MIP        N=Network
                  V=Visualization
Solver
Code Name    Feat. H/W       Phone        Email address
---------    ----- --------- ------------ -------------
AT&T KORBX   IQ    WS ^      908-949-8966
Best Answer  S     Mac-Plus  510-943-7667
CPLEX        SIMN  PC3 ^     702-831-7744 info@cplex.com
Excel        SMG   PC/Mac    206-882-8080
FortLP       SM    PC ^      708-971-2337
HS/LP        SM    PC3/VAX   201-627-1424
IBM OSL      SIMNQ PC/WS/IBM 914-433-4740 randym@vnet.ibm.com
INCEPTA      SMV   PC3       416-896-0515
LAMPS        SM    PC3 ^     413-584-1605 al@amsoft.demon.co.uk
LINDO        SMQ   PC ^      312-871-2524 lindo@delphi.com
LOQO         IQ    PC ^      609-258-0876 rvdb@princeton.edu
LP88         S     PC        703-360-7600
LPS-867      SM    PC/RS6000 609-737-6800
MathPro      SMV   PC2/WS    202-887-0296
MILP88       SM    PC        703-360-7600
MILP LO      SV    PC      (+361)149-7531
MINOS        SQG   PC ^      415-962-8719 mike@sol-michael.stanford.edu
MINTO        M     WS        404-894-6287
MPS-III      SMNQ  PC3 ^     703-412-3201
MPSX (see IBM OSL)
MSLP-PC      S     PC        604-361-9778
OMP          SM    PC/VAX/WS 919-847-9997
PC-PROG      SMQ   PC        919-847-9997 Ge.vanGeldorp@lr.tudelft.nl
SAS/OR       SMN   PC ^      919-677-8000
SCICONIC     SM    PC3 ^  (+44)908-585858
STORM        SMN   PC        216-464-1209
TurboSimplex S     PC/Mac    703-351-5272
What If      SMG   PC        800-447-2226
XA           SM    PC ^      818-441-1565 sunsetsoft@aol.com
XPRESS-MP    SM    PC3/Mac ^ 202-887-0296 rcd@dashbh.demon.co.uk

Modeling
Code Name          H/W        Phone        Email address
---------          --------- ------------ -------------
AIMMS              PC3    (+31)023-350935 info@paragon.nl
AMPL               PC3 ^     508-777-9069 ampl@research.att.com
DATAFORM           PC3 ^     703-558-8701
GAMS               PC2 ^     415-583-8840 gams@gams.com
LINGO              PC ^      312-871-2524 lindo@delphi.com
MIMI/LP            WS        908-464-8300
MPL Sys.           PC        703-522-7900
OMNI               PC3 ^     202-627-1424
VMP                PC3/WS    301-622-0694
What's Best!       PC/Mac/WS 800-441-2378 lindo@delphi.com
XPRESS-MP          PC3/Mac ^ 202-887-0296 rcd@dashbh.demon.co.uk

The author of the OR/MS Today survey, Ramesh Sharda, has updated
and expanded it in 1993 into a larger report called "Linear and
Discrete Optimization and Modeling Software: A Resource
Handbook". For information, contact Lionheart Publishing Inc., 2555
Cumberland Parkway, Suite 299, Atlanta, GA 30339. Phone:
(404)-431-0867. This book is fairly expensive, and geared toward
users whose needs for LP software are considerable.

Another useful book is the "Optimization Software Guide," by Jorge
More' and Stephen Wright, from SIAM Books. Call
1-800-447-7426 to order ($24.50, less ten percent if you are a SIAM
member). It contains references to 75 available software packages
(not all of them just LP), and goes into more detail than is possible
in this FAQ. A Web version is available, at least the parts that give
info on actual software packages, in URL
http://www.mcs.anl.gov/home/otc/Guide/software.html.


Q3. "Oh, and we also want to solve it as an integer program.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

A: Integer LP models are ones where the answers must not take
fractional values. It may not be obvious that this is a VERY much
harder problem than ordinary LP, but it is nonetheless true. The
buzzword is "NP-Completeness", the definition of which is beyond
the scope of this document but means in essence that, in the worst
case, the amount of time to solve a family of related problems goes
up exponentially as the size of the problem grows, for all algorithms
that solve such problems to a proven answer.

Integer models may be ones where only some of the variables are to
be integer and others may be real-valued (termed "Mixed Integer
LP" or MILP, or "Mixed Integer Programming" or MIP); or they
may be ones where all the variables must be integral (termed "Integer
LP" or ILP). The class of ILP is often further subdivided into
problems where the only legal values are {0,1} ("Binary" or
"Zero-One" ILP), and general integer problems. For the sake of
generality, the Integer LP problem will be referred to here as MIP,
since the other classes can be viewed as special cases of MIP. MIP, in
turn, is a particular member of the class of Discrete Optimization
problems.

People are sometimes surprised to learn that MIP problems are
solved using floating point arithmetic. Although various algorithms
for MIP have been studied, most if not all available general purpose
large-scale MIP codes use a method called "Branch and Bound" to
try to find an optimal solution. Briefly stated, B&B solves MIP by
solving a sequence of related LP models. (As a point of interest, the
Simplex Method currently retains an advantage over the newer
Interior-Point methods for solving these sequences of LP's.) Good
codes for MIP distinguish themselves more by solving shorter
sequences of LP's, than by solving the individual LP's faster. Even
more so than with regular LP, a costly commercial code may prove
its value to you if your MIP model is difficult.

You should be prepared to solve *far* smaller MIP models than the
corresponding LP model, given a certain amount of time you wish to
allow (unless you and your model happen to be very lucky). There
exist models that are considered challenging, with a few dozen
variables. Conversely, some models with tens of thousands of
variables solve readily. The best explanations of "why" usually seem
to happen after the fact. 8v) But a MIP model with hundreds of
variables should always be approached, initially at least, with a
certain amount of humility.

A major exception to this somewhat gloomy outlook is that there are
certain models whose LP solution always turns out to be integer,
assuming the input data is integer to start with. The theory of
unimodular matrices is fundamental here. It turns out that such
problems are best solved by specialized routines that take major
shortcuts in the Simplex Method, and as a result are relatively quick-
running compared to ordinary LP. See the section on Network
models for further information.

The public domain code lp_solve, mentioned earlier, accepts MIP
models, as do a large number of the commercial LP codes in the June
1992 OR/MS Today survey (see section above). There is, in the April
1994 issue of OR/MS Today, a survey of MIP codes, which largely
overlaps the content of the earlier survey on LP: "Survey: Mixed
Integer Programming" by Matthew Saltzman, pp 42-51..

Peter Barth has announced opbdp, an implementation in C++ of an
implicit enumeration algorithm for solving linear 0-1 optimization
problems. The algorithm compares well with commercial linear
programming-based branch-and-bound on a variety of standard 0-1
integer programming benchmarks. He says that exploiting the logical
structure of a problem, using opbdp, yields good performance on
problems where exploiting the polyhedral structure seems to be
inefficient and vice versa. The package is available via anonymous
ftp: ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp or www:
http://www.mpi-sb.mpg.de:/guide/staff/barth/barth.html A
Technical Report is included as Postscript-File "mpii952002.ps"
describing the techniques used in opbdp.

I have seen mention made of algorithm 333 in the Collected
Algorithms from CACM, though I'd be surprised if it was robust
enough to solve large models. I am not aware of this algorithm being
available online anywhere.

In [Syslo] is code for 28 algorithms, most of which pertain to some
aspect of Discrete Optimization.

There is a code called Omega that analyzes systems of linear
equations in integer variables. It does not solve optimization
problems, except in the case that a model reduces completely, but its
features could be useful in analyzing and reducing MIP models. It's
available at ftp.cs.umd.edu:pub/omega (documentation is provided
there), or contact Bill Pugh at pugh@cs.umd.edu.

Mustafa Akgul (akgul@bilkent.edu.tr) at Bilkent University
maintains an archive in ftp://ftp.bilkent.edu.tr/pub/IEOR/Opt. There
is a copy of lp_solve (though I would recommend using the official
source listed in the previous section), and there is mip386.zip, which
is a zip-compressed code for PC's. He also has a couple of network
codes and various other codes he has picked up. All this is in the
further subdirectories LP, PC, and Network. In addition to the ftp
site, there is gopher (gopher.bilkent.edu.tr), Web
(www.bilkent.edu.tr), and archive-server@bilkent.edu.tr.

Bob Craig of AT&T (kat3@uscbu.ih.att.com) has software written in
C, which implements Balas' enumerative algorithm for solving 0-1
ILP, that he is willing to make available to those who request it.

The better commercial MIP codes have numerous parameters and
options to give the user control over the solution strategy. Most have
the capability of stopping before an optimum is proved, printing the
best answer obtained so far. For many MIP models, stopping early is
a practical necessity. Fortunately, a solution that has been proved by
the algorithm to be within, say, 1% of optimality often turns out to
be the true optimum, and the bulk of the computation time is spent
proving the optimality. For many modeling situations, a
near-optimal solution is acceptable anyway.

Once one accepts that large MIP models are not typically solved to a
proved optimal solution, that opens up a broad area of approximate
methods, probabilistic methods and heuristics, as well as
modifications to B&B. See [Balas] which contains a useful heuristic
for 0-1 MIP models. See also the brief discussion of Genetic
Algorithms and Simulated Annealing in the Nonlinear Programming
FAQ.

Whatever the solution method you choose, when trying to solve a
difficult MIP model, it is usually crucial to understand the workings
of the physical system (or whatever) you are modeling, and try to
find some insight that will assist your chosen algorithm to work
better. A related observation is that the way you formulate your
model can be as important as the actual choice of solver. You should
consider getting some assistance if this is your first time trying to
solve a large (>100 integer variable) problem.


Q4. "I wrote an optimization code. Where are some test models?"
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

A: If you want to try out your code on some real-world LP models,
there is a very nice collection of small-to-medium-size ones, with a
few that are rather large, at ftp://netlib2.cs.utk.edu/lp/data,
popularly known as the Netlib collection (although Netlib consists of
much more than just LP). These files (after you uncompress them) are
in a format called MPS, which is described in another section of this
document. Note that, when you receive a model, it may be
compressed both with the Unix utility (use `uncompress` if the file
name ends in .Z) AND with an LP-specific program (grab either
emps.f or emps.c at the same time you download the model, then
compile/run the program to reverse the compression).

Also on netlib is a collection of infeasible LP models, located in
ftp://netlib2.cs.utk.edu/lp/infeas.

There is a collection of MIP models, housed at Rice University in
ftp://softlib.cs.rice.edu/pub/miplib. Send an email message
containing "send catalog" to softlib@rice.edu , to get started, if you
can't access the files by other means. There's also a Travelling
Salesman Problem (TSP) collection in
ftp://softlib.cs.rice.edu/pub/tsplib.

There is a collection of network-flow codes and models at
ftp://dimacs.rutgers.edu/pub/netflow. Another network generator is
called NETGEN and is available at
ftp://netlib2.cs.utk.edu/lp/generators.

The commercial modeling language GAMS comes with about 150
test models, which you might be able to test your code with. AIMMS
also comes with some test models.

There is a collection called MP-TESTDATA available at
Konrad-Zuse-Zentrum fuer Informations-technik Berlin (ZIB) in
ftp://elib.zib-berlin.de/pub/mp-testdata. This directory contains
various subdirectories, each of which has a file named "index"
containing further information. Indexed at this writing are: assign,
cluster, lp, ip, matching, maxflow, mincost, set-parti, steiner-tree,
tsp, vehicle-rout, and generators.

John Beasley maintains the OR-Lib, at
ftp://mscmga.ms.ic.ac.uk/pub/, which contains various optimization
test problems. There is an index in
ftp://mscmga.ms.ic.ac.uk/pub/info.txt. WWW access now available
at http://mscmga.ms.ic.ac.uk/. Have a look in the Journal of the
Operational Research Society, Volume 41, Number 11, Pages
1069-72. If you can't access these resources, send e-mail to
umtsk99@vaxa.cc.imperial.ac.uk to get started. Information about
test problems can be obtained by emailing o.rlibrary@ic.ac.uk with
the email message being the file name for the problem areas you are
interested in, or just the word "info".


Q5. "What is MPS format?"
++++++++++++++++++++++++++

A: MPS format was named after an early IBM LP product and has
emerged as a de facto standard ASCII medium among most of the
commercial LP codes. Essentially all commercial LP codes accept
this format, but if you are using public domain software and have
MPS files, you may need to write your own reader routine for this.
It's not too hard. See also the comment regarding the lp_solve code,
in another section of this document, for the availability of an MPS
reader.

The main things to know about MPS format are that it is column
oriented (as opposed to entering the model as equations), and
everything (variables, rows, etc.) gets a name. MPS format is
described in more detail in [Murtagh]. A brief description of MPS
format is available at ftp://softlib.cs.rice.edu/pub/miplib

MPS is an old format, so it is set up as though you were using punch
cards, and is not free format. Fields start in column 1, 5, 15, 25, 40
and 50. Sections of an MPS file are marked by so-called header
cards, which are distinguished by their starting in column 1.
Although it is typical to use upper-case throughout the file (like I
said, MPS has long historical roots), many MPS-readers will accept
mixed-case for anything except the header cards, and some allow
mixed-case anywhere. The names that you choose for the individual
entities (constraints or variables) are not important to the solver;
you should pick names that are meaningful to you, or will be easy for a
post-processing code to read.

Here is a little sample model written in MPS format (explained in
more detail below):

NAME          TESTPROB
ROWS
 N  COST
 L  LIM1
 G  LIM2
 E  MYEQN
COLUMNS
    XONE      COST                 1   LIM1                 1
    XONE      LIM2                 1
    YTWO      COST                 4   LIM1                 1
    YTWO      MYEQN               -1
    ZTHREE    COST                 9   LIM2                 1
    ZTHREE    MYEQN                1
RHS
    RHS1      LIM1                 5   LIM2                10
    RHS1      MYEQN                7
BOUNDS
 UP BND1      XONE                 4
 LO BND1      YTWO                -1
 UP BND1      YTWO                 1
ENDATA

For comparison, here is the same model written out in an
equation-oriented format:

Optimize
 COST:    XONE + 4 YTWO + 9 ZTHREE
Subject To
 LIM1:    XONE + YTWO < = 5
 LIM2:    XONE + ZTHREE > = 10
 MYEQN:   - YTWO + ZTHREE  = 7
Bounds
 0 < = XONE < = 4
-1 < = YTWO < = 1
End

Strangely, there is nothing in MPS format that specifies the direction
of optimization. And there really is no standard "default" direction;
some LP codes will maximize if you don't specify otherwise, others
will minimize, and still others put safety first and have no default
and require you to specify it somewhere in a control program or by a
calling parameter. If you have a model formulated for minimization
and the code you are using insists on maximization (or vice versa), it
may be easy to convert: just multiply all the coefficients in your
objective function by (-1). The optimal value of the objective
function will then be the negative of the true value, but the values of
the variables themselves will be correct.

The NAME card can have anything you want, starting in column 15.
The ROWS section defines the names of all the constraints; entries in
column 2 or 3 are E for equality rows, L for less-than ( <= ) rows, G
for greater-than ( >= ) rows, and N for non-constraining rows (the
first of which would be interpreted as the objective function). The
order of the rows named in this section is unimportant.

The largest part of the file is in the COLUMNS section, which is the
place where the entries of the A-matrix are put. All entries for a
given column must be placed consecutively, although within a
column the order of the entries (rows) is irrelevant. Rows not
mentioned for a column are implied to have a coefficient of zero.

The RHS section allows one or more right-hand-side vectors to be
defined; most people don't bother having more than one. In the above
example, the name of the RHS vector is RHS1, and has non-zero
values in all 3 of the constraint rows of the problem. Rows not
mentioned in an RHS vector would be assumed to have a
right-hand-side of zero.

The optional BOUNDS section lets you put lower and upper bounds
on individual variables (no * wild cards, unfortunately), instead of
having to define extra rows in the matrix. All the bounds that have a
given name in column 5 are taken together as a set. Variables not
mentioned in a given BOUNDS set are taken to be non-negative
(lower bound zero, no upper bound). A bound of type UP means an
upper bound is applied to the variable. A bound of type LO means a
lower bound is applied. A bound type of FX ("fixed") means that the
variable has upper and lower bounds equal to a single value. A bound
type of FR ("free") means the variable has neither lower nor upper
bounds.

There is another optional section called RANGES that I won't go
into here. The final card must be ENDATA, and yes, it is spelled
funny.


Q6. "Just a quick question..."
+++++++++++++++++++++++++++++++

 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
   *exists*.
 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 (TSP)?
 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?

Q6.1: What is a modeling language?
-----------------------------------

A: This is any code that creates input for an LP (or MIP, or NLP)
code, using a more flexible input than MPS format. There are no free
ones. Modeling languages can be roughly broken into two classes,
column oriented ones, and equation oriented ones. The former class is
older, and includes such commercial products as OMNI (Haverley
Systems) and DATAFORM (Ketron); they tend to be called "matrix
generators" sometimes. Members of the latter class are GAMS
(Scientific Press), LINGO (LINDO Systems), AIMMS (Paragon
Decision Technology) and AMPL (information is in
netlib/opt/ampl.info.Z on the netlib server, or send email to
ampl@research.att.com - see also the WWW home page for AMPL
at ftp://netlib.att.com/netlib/att/cs/home/ampl/ampl.html). These
products have links to various solvers, commercial and otherwise.

Broadening the question slightly to cover front-ends in general, it's
worth noting that people frequently use spreadsheet programs as an
interface to some LP solvers.

Q6.2: How do I diagnose an infeasible LP model?
------------------------------------------------

A: A model is infeasible if the constraints are inconsistent, i.e., if
no feasible solution can be constructed. It's often difficult to track
down a cause. The cure may even be ambiguous: is it that some demand
was set too high, or a supply set too low? A useful technique is Goal
Programming, one variant of which is to include two explicit slack
variables (positive and negative), with huge cost coefficients, in each
constraint. The revised model is guaranteed to have a solution, and
you can look at which rows have slacks that are included in the
"optimal" solution. By the way, I recommend a Goal Programming
philosophy even if you aren't having trouble with feasibility; "come
on, you could probably violate this constraint for a price." 8v)
Another approach is Fourier-Motzkin Elimination (article by
Danztig and Eaves in the Journal of Combinatorial Theory (A) 14,
288-297 (1973). A software system called ANALYZE was
developed by Harvey Greenberg to provide computer-assisted
analysis, including rule-based intelligence; for further information
about this code, and a bibliography of more than 400 references on
the subject of model analysis, contact Greenberg at
HGREENBERG@cudnvr.denver.colorado.edu. A system based on
the MINOS solver, called MINOS(IIS), available from John
Chinneck (chinneck@sce.carleton.ca), can also be used to identify a
so-called Irreducible Infeasible Subset; the IIS feature is now
available in CPLEX (command "display iis") and LINDO (command
"debug"). As a final comment, commercial codes sometimes have
other built-in features to help track infeasibilities.

Q6.3: I want to know the specific constraints that contradict each
other.
-----------------------------------------------------------------------

A: This may not be a well posed problem. If by this you mean you
want to find the minimal set of constraints that should be removed to
restore feasibility, this can be modeled as an Integer LP (which
means, it's potentially a harder problem than the underlying LP
itself). Start with a Goal Programming approach as outlined above,
and introduce some 0-1 variables to turn the slacks off or on. Then
minimize on the sum of these 0-1 variables. An article covering
another approach to this question is by Chinneck and Dravnieks in
the Spring 1991 ORSA Journal on Computing (vol 3, number 2).

Q6.4: I just want to know whether or not a feasible solution *exists*.
-----------------------------------------------------------------------

A: From the standpoint of computational complexity, finding out if a
model has a feasible solution is essentially as hard as finding the
optimal LP solution, within a factor of 2 on average, in terms of
effort in the Simplex Method; plug your problem into a normal LP
solver with any objective function you like, such as c=0. There are no
shortcuts in general, unless you know something useful about your
model's structure (e.g., if you are solving some form of a
transportation problem, you may be able to assure feasibility by
checking that the sources add up to at least as great a number as the
sum of the destinations).

Q6.5: I have an LP, except it's got several objective functions.
-----------------------------------------------------------------

A: Fundamental to the class of Multiple Criteria models is that there
may no longer be the concept of a unique solution. I am unaware of
any public domain code to approach such problems. I have seen a
reference to MATLAB's Optimization Toolbox.

ADBASE is a package that computes all efficient (i.e.,
nondominated) extreme points of a multiple objective linear
program. It is available without charge for research and instructional
purposes. If someone has a genuine need for such a code, they should
send a request to: Ralph E. Steuer, Faculty of Management Science,
Brooks Hall, University of Georgia, Athens, GA 30602-6255.

Other approaches that have worked are:

 o Goal Programming (treat the objectives as constraints with
   costed slacks), or, almost equivalently, form a composite
   function from the given objective functions;
 o Pareto preference analysis (essentially brute force
   examination of all vertices);
 o Put your objective functions in priority order, optimize on
   one objective, then change it to a constraint fixed at the
   optimal value (perhaps subject to a small tolerance), and
   repeat with the next function.

There is a section on this whole topic in [Nemhauser]. [Schrage] has a
chapter devoted to the subject. [Hwang] has also been recommended
by a reader on Usenet. As a final piece of advice, if you can cast your
model in terms of physical realities, or dollars and cents, sometimes
the multiple objectives disappear! 8v)

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?
--------------------------------------------------------------------

A: Possibly. See section 6.2 in [Nemhauser] for a discussion of
Dantzig-Wolfe decomposition. I am told that the commercial code
OSL has features to assist in doing this. With any other code, you'll
have to create your own framework and then call the LP solver to
solve the subproblems. The folklore is that generally such schemes
take a long time to converge so that they're slower than just solving
the model as a whole, although research continues. For now my
advice, unless you are using OSL or your model is so huge that a
good solver can't fit it in memory, is to not bother decomposing it.
It's probably more cost effective to upgrade your solver, if the
algorithm is limiting you, than to invest your time; but I suppose
that's an underlying theme in a lot of my advice. 8v)

Q6.7: I am looking for an algorithm to compute the convex hull of a
finite number of points in n-dimensional space.
-------------------------------------------------------------------

A: There is a program called qhull, available at
ftp://geom.umn.edu/pub/software/qhull.tar.Z. When you uncompress
it and untar it, it will create a directory called qhull which has source
code plus a README file. It uses the "Beneath Beyond" method,
described in [Edelsbrunner]. A code in C called cdd is available at
ftp://ftp.efpl.ch/incoming/dma and is written by Komei Fukuda;
download the file named cdd-***.tar.Z, where *** is the version
number (choose the most recent version, which at last check was
055). It solves the problem stated above, as well as that of
enumerating all vertices. A code in C called rs by David Avis
implements the reverse search method. There is a directory in
ftp://elib.zib-berlin.de/pub/mathprog/polyth that contains pointers to
some tools for such problems. Other algorithms for such problems
are described in [Swart], [Seidel], and [Avis]. Such topics are said to
be discussed in [Schrijver] (page 224), [Chvatal] (chapter 18),
[Balinski], and [Mattheis] as well. Part of the method described in
[Avis], to enumerate vertices, is implemented in a Mathematica
package called VertexEnum.m at
ftp://cs.sunysb.edu/pub/Combinatorica, in file VE041.Z.

Q6.8: Are there any parallel LP codes?
---------------------------------------

A: The vendors for OSL, CPLEX and XPRESS-MP each have
announced parallel implementations of Branch and Bound solvers for
MIP. Jeffrey Horn (horn@cs.wisc.edu) has compiled a bibliography
of papers relating to research on parallel B&B. There is an survey
article by Gendron and Crainic in the journal Operations Research,
Vol. 42 (1994), No. 6, pp. 1042-1066.

I'm not aware of any implementations (beyond the "toy" level) of
general sparse Simplex or interior-point solvers on parallel
machines. If your particular model is a good candidate for
decomposition (see topic, above) then parallelism could be very
useful, but you'll have to implement it yourself. Here's what I say to
people who write parallel LP solvers as class projects:

You are probably working with the tableau form of the Simplex
method. This method works well for small models, but it is
inefficient for most real-world models because such models are
usually <1% dense. Sparse matrix methods dominate here. It may
well be true that you can get good parallel speedups with your code,
but I'd wager that by the time you get to problems with 1000 rows,
any parallel-dense LP code will be slower than a single- processor
sparse code. And, worse yet, I think it's generally accepted that no
one currently knows how to do a good (i.e., scalable) parallel sparse
LP code. I wouldn't be harping on this point, except that most
people's interest in parallelism is because of the promise of
scalability, in which case large-scale considerations are important.
Writing even a single-processor large-scale LP code is a multi-year
project, realistically. The point is, don't get too enthralled by
speedups in your code, unless there's something to what you are
doing that I haven't guessed.

Q6.9: What software is there for Network models?
-------------------------------------------------

A: Special cases of this problem are the Transportation Problem, the
Assignment Problem, and the Shortest Path Problem. Some
commercial LP solvers include a network solver. See [Kennington],
which contains some source code for Netflo, a code available at
ftp://dimacs.rutgers.edu/pub/netflow/mincost/solver-1, but I don't
know the copyright situation (I always thought you had to buy the
book to get the code). Other network solvers are on this same
DIMACS server in ftp://dimacs.rutgers.edu/pub/netflow. Another
text containing Fortran code is [Bertsekas]; an on-line location for
source code that may be related to this is
ftp://LIDS.MIT.EDU/pub/bertsekas/RELAX for minimum cost flow
problems. Simiarly, [Burkard] and [Martello] contain Fortran code
for the Assignment Problem. There is an ACM TOMS routine, #548,
located at ftp://netlib2.cs.utk.edu/toms/548, that solves the
Assignment problem using the Hungarian Method. An article in the
ORSA Journal on Computing in 1991 by Kennington and Wang
investigated the performance of some algorithms.

The following software for Network models is available by sending
mail to "ftp-request@theory.stanford.edu". To obtain the desired
software, put the following as the SUBJECT:

    "send csmin.tar"    to get the cost scaling min-cost flow/
                        transportation problem code (CS).  (current
                        version 1.2)
    "send splib.tar"    to get the library of shortest paths codes and
                        problem generators.
    "send csas.tar"     to get the assignment problem codes (CSA).
    (A maximum flow code was to be available in the Fall of 1994.)

Technical reports describing the above implementation are also
available. The SUBJECT line should contain the following.

    "send stan-cs-92-1439.ps"    to get the CS implementation report.
    "send stan-cs-93-1480.ps"    to get the SPLIB report.
    "send stan-cs-93-1481.ps"    to get the CSA implementation report.

Q6.10: What software is there for the Traveling Salesman Problem (TSP)?
-----------------------------------------------------------------------

A: TSP is a famously hard problem that has attracted many of the
best minds in the field. Solving for a proved optimum is
combinatorial in nature; methods have been explored both to give
proved optimal solutions, and to give approximate but "good"
solutions. To my knowledge, there aren't any commercial products to
solve this problem, nor are there any public domain codes available
by anonymous FTP. For a bibliography, check the Integer
Programming section of [Nemhauser], particularly the references
with the names Groetschel and/or Padberg in them. A good reference
is [Lawler]. There are some heuristics for getting a "good" solution
in the article by Lin and Kernighan in Operations Research, Vol 21
(1973), pp 498-516. [Syslo] contains some algorithms and Pascal
code. Numerical Recipes [Press] contains code that uses Simulated
Annealing. [Bentley] is said to contain a description of how to write
a TSP code. Code for a solver can be obtained via instructions in
[Volgenant]. Bob Craig of AT&T (kat3@uscbu.ih.att.com) has
software written in C, for both exact solution and heuristics, that he
is willing to make available to those who request it. Likewise, Chad
Hurwitz (churritz@crash.cts.com), offers a code called tsp_solve for
heuristic and optimal solution, to those who email him.

Q6.11: What software is there for the Knapsack Problem?
--------------------------------------------------------

A: As with the TSP, I don't know of any commercial solvers for this
specific problem. Any good MIP solver should be able to be used,
although any given instance of this problem could be difficult.
Specialized algorithms are said to be available in [Syslo] and
[Martello]. Bob Craig of AT&T (kat3@uscbu.ih.att.com) has
software written in C, for both exact solution and heuristics, that he
is willing to make available to those who request it.

Q6.12: What software is there for Stochastic Programming?
----------------------------------------------------------

A: [Thanks to Derek Holmes, dholmes@engin.umich.edu, for this
text.] Your success solving a stochastic program depends greatly on
the characteristics of your problem. The two broad classes of
stochastic programming problems are recourse problems and chance-
constrained (or probabilistically constrained) problems.

Recourse Problems are staged problems wherein one alteranates
decisions with realizations of stochastic data. The objective is to
minimize total expected costs of all decisions. The main sources of
code (not necessarily public domain) depend on how the data is
distributed and how many stages (decision points) are in the problem.
For discretely distributed multistage problems, a good package called
MSLiP is available from Gus Gassman (gassmann@ac.dal.ca, written
up in Math. Prog. 47,407-423) Also, for not huge discretely
distributed problems, a deterministic equivalent can be formed which
can be solved with a standard solver. STOPGEN, available via
anonymous FTP from this author is a program which forms
deterministic equiv. MPS files from stopro problems in standard
format (Birge, et. al., COAL newsletter 17). The most recent
program for continuously distributed data is BRAIN, by K.
Frauendorfer (frauendorfer@sgcl1.unisg.ch, written up in detail in
the author's monograph ``Stochastic Two-Stage Programming'',
Lecture Notes in Economics & Math. Systems #392
(Springer-Verlag).

CCP problems are not usually staged, and have a constraint of the
form Pr( Ax <= b ) >= alpha. The solvability of CCP problems
depends on the distribution of the data (A &/v b). I don't know of any
public domain codes for CCP probs., but you can get an idea of how
to approach the problem by reading Chapter 5 by Prof. A. Prekopa
(prekopa@cancer.rutgers.edu) Y. Ermoliev, and R. J-B. Wets, eds.,
Numerical Techniques for Stochastic Optimization (Series in Comp.
Math. 10, Springer-Verlag, 1988).

Both Springer Verlag texts mentioned above are good introductory
references to Stochastic Programming. This list of codes is far from
comprehensive, but should serve as a good starting point.

Q6.13: I need to do post-optimal analysis.
-------------------------------------------

A: Many commercial LP codes have features to do this. Also called
Ranging or Sensitivity Analysis, it gives information about how the
coefficients in the problem could change without affecting the nature
of the solution. Most LP textbooks, such as [Nemhauser], describe
this. Unfortunately, all this theory applies only to LP.

For a MIP model with both integer and continuous variables, you
could get a limited amount of information by fixing the integer
variables at their optimal values, re-solving the model as an LP, and
doing standard post-optimal analyses on the remaining continuous
variables; but this tells you nothing about the integer variables,
which presumably are the ones of interest. Another MIP approach would
be to choose the coefficients of your model that are of the most
interest, and generate "scenarios" using values within a stated range
created by a random number generator. Perhaps five or ten scenarios
would be sufficient; you would solve each of them, and by some means
compare, contrast, or average the answers that are obtained. Noting
patterns in the solutions, for instance, may give you an idea of what
solutions might be most stable. A third approach would be to
consider a goal-programming formulation; perhaps your desire to
see post-optimal analysis is an indication that some important aspect
is missing from your model.

Q6.14: Do LP codes require a starting vertex?
----------------------------------------------

A: No. You just have to give an LP code the constraints and the
objective function, and it will construct the vertices for you. Most
codes go through a so-called two phase method, wherein the code
first looks for a feasible solution, and then works on getting an
optimal solution. The first phase can begin anywhere, such as with all
the variables at zero (though commercial codes typically have a
so-called "crash" algorithm to pick a better starting point). So, no,
you don't have to give a code a starting point. On the other hand, it is
not uncommon to do so, because it can speed up the solution time
tremendously. Commercial codes usually allow you to do this (they
call it a "basis", though that's a loose usage of a specific linear
algebra concept); free codes generally don't. You'd normally want to
bother with a starting basis only when solving families of related and
difficult LP's (i.e., in some sort of production mode).


Q7. "What references are there in this field?"
+++++++++++++++++++++++++++++++++++++++++++++++

A: What follows here is an idiosyncratic list, a few books that I like
or have been recommended on the net. I have *not* reviewed them
all.

Regarding the common question of the choice of textbook for a
college LP course, it's difficult to give a blanket answer because of
the variety of topics that can be emphasized: brief overview of
algorithms, deeper study of algorithms, theorems and proofs,
complexity theory, efficient linear algebra, modeling techniques,
solution analysis, and so on. An small and unscientific poll of
ORCS-L mailing list readers in 1993 uncovered a consensus that
[Chvatal] was in most ways pretty good, at least for an
algorithmically oriented class. For a class in modeling, a book about
a commercial code would be useful (LINDO, AMPL, GAMS were
suggested), especially if the students are going to use such a code;
and I have always had a fondness for [Williams]. I have marked with an
arrow ("->") books that received positive mention in this poll (I
included my own votes too 8v) ). The lack of an arrow does not imply
anything negative about a textbook, only that no one responded to the
survey to say they'd used it for a class and liked it.

General reference
------------------

 o Nemhauser, Rinnooy Kan, & Todd, eds, Optimization,
   North-Holland, 1989. (Very broad-reaching, with large
   bibliography. Good reference; it's the place I tend to look
   first. Expensive, and tough reading for beginners.)

Books containing source code
-----------------------------

 o Best and Ritter, Linear Programming: active set analysis and
   computer programs, Prentice-Hall, 1985.
 o Bertsekas, D.P., Linear Network Optimization: Algorithms
   and Codes, MIT Press, 1991.
 o Bunday and Garside, Linear Programming in Pascal, Edward
   Arnold Publishers, 1987.
 o Bunday, Linear Programming in Basic (presumably the same
   publisher).
 o Burkard and Derigs, Springer Verlag Lecture Notes in Math
   Systems #184 (the Assignment Problem and others).
 o Kennington & Helgason, Algorithms for Network
   Programming, Wiley, 1980. (A special case of LP; contains
   Fortran source code.)
 o Lau, H.T., A Numerical Library in C for Scientists and
   Engineers, CRC Press, 1994. (Contains a section on
   optimization.)
 o Martello and Toth, Knapsack Problems: Algorithms and
   Computer Implementations, Wiley, 1990. (Contains Fortran
   code, comes with a disk - also covers Assignment Problem.)
 o Press, Flannery, Teukolsky & Vetterling, Numerical Recipes,
   Cambridge, 1986. (Comment: use their LP code with care.)
 o Syslo, Deo & Kowalik, Discrete Optimization Algorithms
   with Pascal Programs, Prentice-Hall (1983). (Contains code
   for 28 algorithms such as Revised Simplex, MIP, networks.)

LP textbooks
-------------

 o -> Bazaraa, Jarvis and Sherali. Linear Programming and
   Network Flows. (Grad level.)
 o -> Chvatal, Linear Programming, Freeman, 1983. (Undergrad
   or grad.)
 o -> Daellenbach and Bell, A User's Guide to LP. (Good for
   engineers, but may be out of print.)
 o -> Ecker & Kupferschmid, Introduction to Operations
   Research.
 o Ignizio, J.P. & Cavalier, T.M., Linear Programming, Prentice
   Hall, 1994. (Covers usual LP topics, plus interior point,
   multi-objective and heuristic techniques.)
 o Luenberger, Introduction to Linear and Nonlinear
   Programming, Addison Wesley, 1984. (Updated version of an
   old standby.)
 o -> Murtagh, B., Advanced Linear Programming,
   McGraw-Hill, 1981. (Good one after you've read an
   introductory text.)
 o Murty, K., Linear and Combinatorial Programming.
 o Nazareth, J.L., Computer Solution of Linear Programs,
   Oxford University Press, New York and Oxford, 1987.
 o Nering, E.D. & Tucker, A.W., Linear Programs and Related
   Problems, Academic Press, 1993.
 o -> Schrijver, A., Theory of Linear and Integer Programming,
   Wiley, 1986. (Advanced)
 o -> Taha, H., Operations Research: An Introduction, 1987.
 o -> Thie, P.R., An Introduction to Linear Programming and
   Game Theory, Wiley, 1988.
 o -> Williams, H.P., Model Building in Mathematical
   Programming, Wiley 1993, 3rd edition. (Little on algorithms,
   but excellent for learning what makes a good model.)

Interior-Point LP (popularly but imprecisely called "Karmarkar")
-----------------------------------------------------------------

 o Arbel, Ami, Exploring Interior-Point Linear Programming,
   MIT Press, 1993. Includes small-scale IBM PC software
   (binary only).
 o -> Fang and Puthenpura, Linear Optimization and
   Extensions. (Grad level textbook, also contains some Simplex
   and Ellipsoid. I heard mixed opinions on this one.)
 o Lustig, Marsten & Shanno, "Interior Point Methods for
   Linear Programming: Computational State of the Art",
   ORSA Journal on Computing, Vol. 6, No. 1, Winter 1994, pp.
   1-14. Followed by commentary articles, and a rejoinder by
   the authors.

Documentation for commercial codes (may be suitable as a classroom
text)
------------------------------------------------------------------

 o Bisschop & Entriken, AIMMS: The Modeling System,
   Paragon Decision Technology, 1993.
 o -> Brooke, Kendrick & Meeraus, GAMS: A Users' Guide,
   The Scientific Press, 1988.
 o -> Fourer, Gay & Kernighan, AMPL: A Modeling Language
   for Mathematical Programming, The Scientific Press / Boyd
   & Fraser, 1992. (Comes with DOS "student" version
   including MINOS and CPLEX.)
 o -> Greenberg, H.J., Modeling by Object-Driven Linear
   Elemental Relations: A User's Guide for MODLER, Kluwer
   Academic Publishers, 1993.
 o -> Schrage, L., LINDO: An Optimization Modeling System,
   The Scientific Press, 1991.

Other publications
-------------------

 o Ahuja, Magnanti & Orlin, Network Flows, Prentice Hall,
   1993.
 o Avis & Fukuda, "A Pivoting Algorithm for Convex Hulls and
   Vertex Enumeration of Arrangements and Polyhedra",
   Discrete and Computational Geometry, 8 (1992), 295--313.
 o Balas, E. and Martin, C., "Pivot And Complement: A
   Heuristic For 0-1 Programming Problems", Management
   Science, 1980, Vol 26, pp 86-96.
 o Balinski, M.L., "An Algorithm for Finding all Vertices of
   Convex Polyhedral Sets", SIAM J. 9, 1, 1961.
 o Bentley, J.L., "Writing Efficient Programs," Prentice Hall,
   1982.
 o Bondy & Murty, Graph Theory with Applications.
 o Edelsbrunner, Algorithms in Combinatorial Geometry,
   Springer Verlag, 1987.
 o Forsythe, Malcolm & Moler, Computer Methods for
   Mathematical Computations, Prentice-Hall.
 o -> Gill, Murray and Wright, Numerical Linear Algebra and
   Optimization, Addison-Wesley, 1991.
 o Greenberg, H.J., A Computer-Assisted Analysis System for
   Mathematical Programming Models and Solutions: A User's
   Guide for ANALYZE, Kluwer Academic Publishers, 1993.
 o Hwang & Yoon, Multiple Attribute Decision Making :
   Methods and Applications, Springer-Verlag, Lecture Notes
   #186.
 o Lawler, Lenstra, et al, The Traveling Salesman Problem,
   Wiley, 1985.
 o Mattheis and Rubin, "A Survey and Comparison of Methods
   for Finding All Vertices of Convex Polyhedral Sets",
   Mathematics of Operations Research, vol. 5 no. 2 1980, pp.
   167-185.
 o More' & Wright, Optimization Software Guide, SIAM
   Books, 1993.
 o Murty, Network Programming, Prentice Hall, 1992.
 o Papadimitriou & Steiglitz, Combinatorial Optimization.
   (Also contains a discussion of complexity of Simplex
   method.)
 o Reeves, C.R., ed., Modern Heuristic Techniques for
   Combinatorial Problems, Halsted Press (Wiley), 1993.
   (Contains chapters on tabu search, simulated annealing,
   genetic algorithms, neural nets, and Lagrangian relaxation.)
 o Seidel, "Constructing Higher-Dimensional Convex Hulls at
   Logarithmic Cost per Face", 1986, 18th ACM STOC,
   404--413.
 o Smale, Stephen, "On the Average Number of Steps in the
   Simplex Method of Linear Programming", Math
   Programming 27 (1983), 241-262.
 o Swart, "Finding the Convex Hull Facet by Facet", Journal of
   Algorithms, 6 (1985), 17--48.
 o Volgenant, A., Symmetric TSPs, European Journal of
   Operations Research, 49 (1990) 153-154.

On-Line Sources of Papers and Bibliographies
---------------------------------------------

 o Michael Trick's Operations Research Page at
   http://mat.gsia.cmu.edu/
 o WORMS (World-Wide-Web for Operations Research and
   Management Science) at
   http://www.maths.mu.oz.au/~worms/
 o Computational Mathematics Archive (London and South East
   Centre for High Performance Computing)
   http://www.lpac.qmw.ac.uk/SEL-HPC/Articles/GeneratedHtml/math.opt.html
 o Bibliography of books and survey papers on combinatorial
   optimization compiled by Brian Borchers
   (borchers@nmt.edu),
   ftp://archives.math.utk.edu/teaching.materials/bibliography/comb.opt.
 o Bibliography of books and papers on Interior-Point methods
   (taking 4 megabytes storage with over 1300 entries!?!) in
   ftp://netlib2.cs.utk.edu/bib/intbib.bib, compiled by Dr.
   Eberhard Kranich (puett@math.uni-wuppertal.de).
 o An interior point archive has been set up at Argonne, to
   maintain a list of links to papers that can be downloaded. Use
   http://www.mcs.anl.gov/home/otc/InteriorPoint/index.html as
   the URL. Related to this Web page is a mailing list. For
   information on using it, send mail to
   majordomo@mcs.anl.gov with one line containing one of:
    o subscribe interior-point-methods
    o who interior-point-methods
    o info interior-point-methods
    o help
 o Information related to Semidefinite Programming is at
   ftp://orion.uwaterloo.ca/pub/henry/teaching/co769g/readme.html


Q8. "How do I access the Netlib server?"
+++++++++++++++++++++++++++++++++++++++++

A: If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
"anonymous" as the Name, and your email address as the Password.
Do a "cd (dir)" where (dir) is whatever directory was mentioned, and
look around, then do a "get (filename)" on anything that seems
interesting. There often will be a "README" file, which you would
want to look at first. Another FTP site is netlib.att.com although you
will first need to do "cd netlib" before you can cd to the (dir) you
are interested in. Alternatively, you can reach an e-mail server via
"netlib@ornl.gov", to which you can send a message saying "send
index from (dir)"; follow the instructions you receive. This is a list of
sites mirroring the netlib repository:

 o Norway netlib@nac.no
 o England netlib@ukc.ac.uk
 o Germany anonymous@elib.zib-berlin.de
 o Taiwan netlib@nchc.edu.tw
 o Australia netlib@draci.cs.uow.edu.au

For those who have WWW (Mosaic, etc.) access, one can access
Netlib via the URL http://www.netlib.org. Also, there is, for X
window users, a utility called xnetlib that is available at
ftp://netlib2.cs.utk.edu/xnetlib (look at the "readme" file first).


Q9. "Who maintains this FAQ list?"
+++++++++++++++++++++++++++++++++++

A>:  John W. Gregory     jwg@cray.com or ashbury@skypoint.com
     Applications Dept.  Cray Research, Inc., Eagan, MN 55121  612-683-3673

This article is Copyright 1995 by John W. Gregory. It may be freely
redistributed in its entirety provided that this copyright notice is
not removed. It may not be sold for profit or incorporated in
commercial documents without the written permission of the copyright
holder.  Permission is expressly granted for this document to be made
available for file transfer from installations offering unrestricted
anonymous file transfer on the Internet.

The material in this document does not reflect any official position
taken by Cray Research, Inc. While all information in this article is
believed to be correct at the time of writing, it is provided "as is"
with no warranty implied.

If you wish to cite this FAQ formally (hey, someone actually asked
me this), you may use:

  Gregory, John W. (jwg@cray.com) "Linear Programming FAQ",
  (1995) Usenet sci.answers.  Available via anonymous FTP
  from rtfm.mit.edu in
  /pub/usenet/sci.answers/linear-programming-faq

There's a mail server on that machine, so if you don't have FTP
privileges, you can send an e-mail message to
mail-server@rtfm.mit.edu containing:

    send usenet/sci.answers/linear-programming-faq

as the body of the message to receive the latest version (it is posted
on the first working day of each month). This FAQ is cross-posted to
news.answers and sci.op-research. If you have access to a World
Wide Web server (Mosaic, Lynx, etc.), you can use
ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq.
ftp://rtfm.mit.edu/pub/usenet/news.answers/linear-programming-faq.

ftp://rtfm.mit.edu/pub/usenet/sci.op-research/linear-programming-faq.

In compiling this information, I have drawn on my own knowledge
of the field, plus information from contributors to Usenet groups and
the ORCS-L mailing list. I give my thanks to all those who have
offered advice and support. I've tried to keep my own biases
(primarily, toward the high end of computing) from dominating what
I write here, and other viewpoints that I've missed are welcome.
Suggestions, corrections, topics you'd like to see covered, and
additional material, are all solicited. Send email to jwg@cray.com


END linear-programming-faq