Linear Programming - Frequently Asked Questions List 
Linear Programming - Frequently Asked Questions List
Posted monthly to Usenet newsgroup
sci.op-research
World Wide Web version:
http://www.skypoint.com/~ashbury/linear-programming-faq.html
Plain-text version:
ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq
Date of this version: April 2, 1996
"Rigorous solutions to assumed problems are easier to sell than
assumed solutions to rigorous problems."
-- Author unknown
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 an ftp-able 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. 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 very reasonable first try, since it does solve non-trivial-sized models, probably better than any other 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.
If you simply want to try solving a particular model, consider the Optimization Technology Center at http://www.mcs.anl.gov/home/otc/otc.html. The centerpiece of this ambitious project is NEOS, the Network-Enhanced Optimization System, consisting of a library of optimization software, a facility to use this library over the network at http://www.mcs.anl.gov/home/otc/Server/lp/lp.html, and a guide to more information about the software packages. Linear and nonlinear models are covered. Capabilities and access modes are still being enhanced - this is an ongoing process.
Jacek Gondzio (gondzio@divsun.unige.ch) has made source for his interior point LP solver HOPDM available at http://ecolu-info.unige.ch/~logilab/software/hopdm.html. 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: ftp://netlib.att.com/netlib/opt/hopdm.shar.Z
Amal de Silva is making available his interior point code for sparse LP. The solvers are based on the Sparsepak routines by Alan George and Joseph Liu, and de Silva considers his code quite efficient. Contact him at amal@cit.gu.edu.au.
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.
For Macintosh users there is a free package called LinPro that is available at ftp://ftp.ari.net/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. 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 (73700.776@compuserve.com) writes:
The following suggestions may represent a low-cost way of solving LP's if you already have certain software available to you.
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 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), since merged into INFORMS. For further information I would suggest you read the full article (an updated version of this survey is in the October 1995 issue). 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, 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
Product Name Feat. H/W Phone Email address or URL
------------ ----- --------- ------------ --------------------
AT&T KORBX IQ WS ^ 908-949-8966 http://www.att.com/ssg/products/korbx.html
Best Answer S Mac-Plus 510-943-7667
CPLEX SIMN PC3^/Mac 702-831-7744 info@cplex.com
http://www.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
http://www.research.ibm.com/osl/
INCEPTA SMV PC3 416-896-0515
LAMPS SM PC3 ^ 413-584-1605 al@amsoft.demon.co.uk
LINDO SMQ PC^/Mac 312-871-2524 info@lindo.com
http://www.win.net/~lindo/
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 SMNGQ 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^/Mac 818-441-1565 sunsetsoft@aol.com
XPRESS-MP SIMQ PC3/Mac ^ 202-887-0296 info@dash.co.uk
+44 1604 858993 http://www.dash.co.uk/
Modeling
Product Name H/W Phone Email address or URL
------------ --------- ------------ ---------------------
AIMMS PC3 (+31)023-350935 info@paragon.nl
AMPL PC3 ^ 508-777-9069 info@ampl.com
http://www.ampl.com/ampl
DATAFORM PC3 ^ 703-412-3201
GAMS PC2 ^ 415-583-8840 gams@gams.com
http://www.gams.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 info@lindo.com
http://www.win.net/~lindo/
XPRESS-MP SIMQ PC3/Mac ^ 202-887-0296 info@dash.co.uk
+44 1604 858993 http://www.dash.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/SoftwareGuide/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/opbdp.tar.Z
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@ihgp.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, called MIPLIB, 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 a Travelling Salesman Problem library (TSPLIB) in ftp://softlib.cs.rice.edu/pub/tsplib. (Alternate address: ftp://elib.zib-berlin.de/pub/mp-testdata/tsp.) A Web version is at http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
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..."
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.
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:
A code in C called cdd is available at ftp://ifor13.ethz.ch/pub/fukuda/cdd 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 056). It solves the problem stated above, as well as that of enumerating all vertices. There is also a C++ version at this site (version 073).
A code in C called rs, by David Avis, is available at ftp://mutt.cs.mcgill.ca/pub/C/README and implements the reverse search method.
Ken Clarkson has written a program called Hull which is an ANSI C program that computes the convex hull of a point set in general dimension. The input is a list of points, and the output is a list of facets of the convex hull of the points, each facet presented as a list of its vertices. It can be downloaded from ftp://netlib.att.com/netlib/voronoi/hull.shar.Z.
There is a directory in ftp://elib.zib-berlin.de/pub/mathprog/polyth that contains pointers to some tools for such problems.
Nina Amenta has a list of computational geometry software at http://www.geom.umn.edu/locate/cglist.
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.
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.
If your particular model is a good candidate for decomposition (see Decomposition, above) then that form of parallelism could also 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.
A package called PPRN is available at ftp://ftp-eio.upc.es/pub/onl/codes/pprn and solves single/multicommodity network flow problems with linear/nonlinear objective function and with/without linear side constraints. Please read the file named INDEX for more details, and contact Jordi Castro at jcastrop@eio.upc.es if you have any questions.
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.
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.
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.
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, or are recent. 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. A 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; of course, some new candidate texts have been published in the meantime. 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 the book by [Williams].
Q8. "How do I access the Netlib server?"
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 1996 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", (1996) Usenet sci.answers. Available via anonymous FTP from rtfm.mit.edu in /pub/usenet/sci.answers/linear-programming-faqThere'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
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