PostedBy: autofaq 2.4
Archivename: linearprogrammingfaq Lastmodified: November 1, 1997 See reader questions & answers on this topic!  Help others by sharing your knowledge [ ] Linear Programming Frequently Asked Questions Optimization Technology Center of Northwestern University and Argonne National Laboratory [ ] Posted monthly to Usenet newsgroup sci.opresearch World Wide Web version: http://www.mcs.anl.gov/home/otc/Guide/faq/linearprogrammingfaq.html Plaintext version: ftp://rtfm.mit.edu/pub/usenet/sci.answers/ Date of this version: November 1, 1997 * Q1. "What is Linear Programming?" * Q2. "Where is there good software to solve LP problems?" o "Free" codes o Commercial codes and modeling systems o Free demos of commercial codes * Q3. "Oh, and we also want to solve it as an integer program." * Q4. "I wrote an optimization code. Where are some test models?" * Q5. "What is MPS format?" * Q6. Topics briefly covered: o Q6.1: "What is a modeling language?" o Q6.2: "How do I diagnose an infeasible LP model?" o Q6.3: "I want to know the specific constraints that contradict each other." o Q6.4: "I just want to know whether or not a feasible solution *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 almostindependent 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 ndimensional 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 postoptimal analysis." o Q6.14: "Do LP codes require a starting vertex?" o Q6.15: "How can I combat cycling in the Simplex algorithm?" * Q7. "What references and Web links are there in this field?" * Q8. "How do I access the Netlib server?" * Q9. "Who maintains this FAQ list?" See also the following pages pertaining to mathematical programming and optimization modeling: * The related Nonlinear Programming FAQ. * The NEOS Guide to optimization models and software. * The Decision Tree for Optimization Software by H.D. Mittelmann and P. Spellucci. * Jiefeng Xu's List of Interesting Optimization Codes in the Public Domain. * Software for Optimization: A Buyer's Guide by Robert Fourer. * Harvey Greenberg's Mathematical Programming Glossary. [ ] Q1. "What is Linear Programming?" A: (For rigorous definitions and theory, which are beyond the scope of this document, the interested reader is referred to the many LP textbooks in print, a few of which are listed in the references section.) A Linear Program (LP) is a problem that can be expressed as follows (the socalled 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 underdetermined, leaving great latitude in the choice of x with which to minimize cx. The word "Programming" is used here in the sense of "planning"; the necessary relationship to computer programming was incidental to the choice of name. Hence the phrase "LP program" to refer to a piece of software is not a redundancy, although I tend to use the term "code" instead of "program" to avoid the possible ambiguity. Although all linear programs can be put into the Standard Form, in practice it may not be necessary to do so. For example, although the Standard Form requires all variables to be nonnegative, 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 minusinfinity. This allows a variable to be without an explicit upper or lower bound, although of course the constraints in the Amatrix will need to put implied limits on the variable or else the problem may have no finite solution. Similarly, good software allows b1 <= Ax <= b2 for arbitrary b1, b2; the user need not hide inequality constraints by the inclusion of explicit "slack" variables, nor write Ax >= b1 and Ax <= b2 as two separate constraints. Also, LP software can handle maximization problems just as easily as minimization (in effect, the vector c is just multiplied by 1). The importance of linear programming derives in part from its many applications (see further below) and in part from the existence of good generalpurpose techniques for finding optimal solutions. These techniques take as input only an LP in the above Standard Form, and determine a solution without reference to any information concerning the LP's origins or special structure. They are fast and reliable over a substantial range of problem sizes and applications. Two families of solution techniques are in wide use today. Both visit a progressively improving series of trial solutions, until a solution is reached that satisfies the conditions for an optimum. Simplex methods, introduced by Dantzig about 50 years ago, visit "basic" solutions computed by fixing enough of the variables at their bounds to reduce the constraints Ax = b to a square system, which can be solved for unique values of the remaining variables. Basic solutions represent extreme boundary points of the feasible region defined by Ax = b, x >= 0, and the simplex method can be viewed as moving from one such point to another along the edges of the boundary. Barrier or interiorpoint methods, by contrast, visit points within the interior of the feasible region. These methods derive from techniques for nonlinear programming that were developed and popularized in the 1960s by Fiacco and McCormick, but their application to linear programming dates back only to Karmarkar's innovative analysis in 1984. The related problem of integer programming (or integer linear programming, strictly speaking) requires some or all of the variables to take integer (whole number) values. Integer programs (IPs) often have the advantage of being more realistic than LPs, but the disadvantage of being much harder to solve. The most widely used generalpurpose techniques for solving IPs use the solutions to a series of LPs to manage the search for integer solutions and to prove optimality. Thus most IP software is built upon LP software, and this FAQ applies to problems of both kinds. Linear and integer programming have proved valuable for modeling many and diverse types of problems in planning, routing, scheduling, assignment, and design. Industries that make use of LP and its extensions include transportation, energy, telecommunications, and manufacturing of many kinds. A sampling of applications can be found in many LP textbooks, in books on LP software systems, and among the application cases in the journal Interfaces. [ ] Q2. "Where is there good software to solve LP problems?" A: Thanks to the advances in computing of the past decade, linear programs in a few thousand variables and constraints are nowadays viewed as "small". Problems having tens or hundreds of thousands of continuous variables are regularly solved; tractable integer programs are necessarily smaller, but are still commonly in the hundreds or thousands of variables and constraints. The computers of choice for linear and integer programming applications are Pentiumbased PCs and the several varieties of Unix workstations. There is more to linear programming than optimal solutions and numbercrunching, however. This can be appreciated by observing that modern LP software comes in two related but very different kinds of packages: * Algorithmic codes are devoted to finding optimal solutions to specific linear programs. A code takes as input a compact listing of the LP constraint coefficients (the A, b, c and related values in the standard form) and produces as output a similarly compact listing of optimal solution values and related information. * Modeling systems are designed to help people formulate LPs and analyze their solutions. An LP modeling system takes as input a description of a linear program in a form that people find reasonably natural and convenient, and allows the solution output to be viewed in similar terms; conversion to the forms requried by algorithmic codes is done automatically. The collection of statement forms for the input is often called a modeling language. Most modeling systems support a variety of algorithmic codes, while the more popular codes can be used with many different modeling systems. Because packages of the two kinds are often bundled for convenience of marketing or operation, the distinction between them is sometimes obscured, but it is important to keep in mind when attempting to sort through the many alternatives available. Largescale LP algorithmic codes rely on generalstructure sparse matrix techniques and numerous other refinements developed through years of experience. The fastest and most reliable codes thus represent considerable development effort, and tend to be expensive except in very limited demonstration or "student" versions. Those codes that are free  to all, or at least for research and teaching  tend to be somewhat less robust, though they are still useful for many problems. The ability of a code to solve any particular class of problems cannot easily be predicted from problem size alone; some experimentation is usually necessary to establish difficulty. Largescale LP modeling systems are commercial products virtually without exception, and tend to be as expensive as the commercial algorithmic codes (again with the exception of small demo versions). They vary so greatly in design and capability that a description in words is adequate only to make a preliminary decision among them; your ultimate choice is best guided by using each candidate to formulate a model of interest. Listed below are summary descriptions of available free codes, and a tabulation of many commercial codes and modeling systems for linear (and integer) programming. A list of free demos of commercial software appears at the end of this section. Another useful source of information is the Optimization Software Guide by Jorge More' and Stephen Wright, available from SIAM Books. It contains references to about 75 available software packages (not all of them just LP), and goes into more detail than is possible in this FAQ; see in particular the sections on "linear programming" and on "modeling languages and optimization systems." An updated Web version of this book is available on the NEOS Guide. Another good soruce of feature summaries and contact information is the Linear Programming Software Survey compiled by OR/MS Today (which also has the largest selection of advertisements for optimization software). Much information can also be obtained through the web sites of optimization software developers, many of which are identified in the writeup and tables below. To provide some idea of the relative performance of LP codes, a Web page of pointers to benchmarks for optimization software is being compiled by Hans Mittelmann of Arizona State University. It currently includes tests of several publicdomain simplex and interiorpoint implementations. When evaluating any performance comparison, however, whether performed by a customer, vendor, or disinterested third party, keep in mind that all highquality codes provide options that offer superior performance on certain difficult kinds of LP or IP problems. Benchmark studies of the "default settings" of codes will fail to reflect the power of the optional settings that are available. "Free" codes Some of these programs require registration or payment for some (especially commercial) uses. Conditions of use are also subject to change. It is a good practice to check a code's "readme" file or introductory documentation for restrictions before committing to use it. Based on the simplex method: There is an ftpable 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 MPSformat 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 wouldbe commercial users. As an editorial opinion, I must state that difficult models will give lp_solve trouble; it's not as good as a commercial code. But for someone who isn't sure what kind of LP code is needed, it represents a reasonable first try. LPOptimizer is a simplexbased code for linear and integer programs, written by Markus Weidenauer (ncweidenma@netcologne.de). Free Borland Pascal 7.0 source is available for downloading, as are executables for DOS and OS/2. SoPlex is an objectoriented implementation of the primal and dual simplex algorithms, developed by Roland Wunderling. Source code is available free for research uses at noncommercial and academic institutions. Among the SLATEC library routines is a Fortran sparse implementation of the simplex method, SPLP, at 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". Based on interiorpoint methods: The Optimization Technology Center at Argonne and Northwestern has developed the interiorpoint code PCx. This code can be downloaded directly from the PCx home page; it is freely available, except that you must contact Argonne if you want to include it in a product for resale. A Windows 95/NT version of PCx was announced in April 1997, and is available under the same conditions as the original. (If you want to solve an LP without downloading a code to your own machine, you can execute PCx remotely through the NEOS Server.) A Fortran 77 interiorpoint code, BPMPD, has been developed by Csaba Meszaros (meszaros@sztaki.hu) at the Computer and Automation Research Institute of the Hungarian Academy of Sciences. It is available as source code, as a Windows95/NT executable (which is also extended to solve convex quadratic problems), and in a DLL version for Windows. Jacek Gondzio (gondzio@divsun.unige.ch) has made source for his interior point LP solver HOPDM available at http://ecoluinfo.unige.ch/~logilab/software/hopdm.html. Additionally, several papers devoted to HOPDM code are available at this site. It uses a higher order primaldual predictorcorrector 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.belllabs.com/netlib/opt/hopdm.shar.Z Other software of interest: ABACUS is a C++ class library that "provides a framework for the implementation of branchandbound algorithms using linear programming relaxations that can be complemented with the dynamic generation of cutting planes or columns" (branchandcut and/or branchandprice). It relies on CPLEX or SoPlex to solver linear programs. Further information is available from Stefan Thienel, thienel@informatik.unikoeln.de. A webbased service by a group at Berkeley called Interactive Linear Programming appears to be useful for solving small models that can be entered by hand. Along similar lines, the NEOS Guide offers a Javabased Simplex Tool, which demonstrates the workings of the simplex method on small userentered problems and is especially useful for educational purposes. AnimaLP by Chris Jones (cvj@u.washington.edu) graphs and solves twodimensional linear programs interactively on any Javacompatible browser; there is also a Macintosh version. The Systems Analysis Laboratory at Seoul National University offers Linear Programming software (both Simplex and Barrier) at http://orly1.snu.ac.kr/Software.html Will Naylor (naylor@mti.sgi.com) has a collection of software he calls WNLIB. Routines of interest include  simplex method for linear programming: contains anticycling and numerical stability hacks. No optimization for sparse matrix.  transportation problem/assignment problem routine: optimization for sparse matrix. Read the INSTALL.txt file for further information. WNLIB also contains routines pertaining to nonlinear optimization. The next several suggestions are for publicdomain codes that are severely limited by the algorithm they use (tableau Simplex); they may be OK for models with (on the order of) 100 variables and constraints, but it's unlikely they will be satisfactory for larger models. In the words of Matt Saltzman (mjs@clemson.edu): The main problems with these codes have to do with scaling, use of explicit inverses and lack of reinversion, and handling of degeneracy. Even small problems that are illconditioned or degenerate can bring most of these tableau codes to their knees. Other disadvantages for larger problems relate to sparsity, pricing, and maintaining the complete nonbasic portion of the tableau. But for small, dense problems these difficulties may not be serious enough to prevent tableau codes from being useful, or even preferable to more "sophisticated" sparse codes. In any event, use them with care. * For DOS/PC users, there is an LP and Linear Goal Programming binary called tslin, at ftp://garbo.uwasa.fi/pc/ (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. * 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). * 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. * 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 2dimensional array for the Amatrix; if so, it is surely using the tableau Simplex Method rather than sparse methods, and Saltzman's comments will apply. For Macintosh users there is a free package called LinPro that is available at 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: * My shareware program, the RTek Scratchpad (rtksp106.zip $15), is intended for teachers and students. It basically handles problems that students in an Introduction to Finite Mathematics course might encounter, including typical small textbook LP problems. Its primary advantages are that it uses readable math notation, handles fractions, and allows you to step through the problem to its solution. It is now available on the net for ftp download at ftp://ftp.coast.net/SimTel/win3/calc/ or one of its mirror sites. Stephen F. Gale (sfgale@freenet.calgary.ab.ca) writes: * Available at http://www.freenet.calgary.ab.ca/~sfgale/simplex.html is a fairly simple Simplex Solver written for Turbo Pascal 3.0. The original algorithm is from the book "Some Common BASIC Programs" by Lon Poole and Mary Borchers (ISBN 0931988063). However, I revised it considerably when I converted it to Pascal. I then added Sensitivity Analysis based on the book "The Operations Research Problem Solver" (ISBN 0878915486). I have tested the program on over 30 textbook problems, but never used it for real life applications. If someone finds a problem with the program, I would be pleased to correct it. I would also appreciate knowing how the program was used. The following suggestions may represent lowcost ways of solving LPs if you already have certain software available to you. * All of the most popular spreadsheet programs offer an LP solver as a feature or addin. * A package called QSB (Quantitative Systems for Business, from PrenticeHall publishers) has an LP module among its routines. * If you have access to a commercial math library, such as SAS (9196778000), IMSL (8002224675 or 7137843131 or support@houston.vni.com) or NAG (7089712337), you may be able to use an LP routine from there. * Mathematical systems MATLAB (The Math Works, Inc., (508) 6531415, see comment in the NLP FAQ) and MAPLE (Waterloo Maple Software, 450 Phillip Street, Waterloo, Ontario, Canada N2L 5J2 Phone: (519) 7472373 Fax: (519) 7475284) 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/. A MATLAB toolkit for solving LP models using InteriorPoint methods, called LIPSOL is available at ftp://ftp.math.umbc.edu/pub/zhang/  check the documentation in this directory (README.1ST) for more information; the current version is in subdirectory v0.3. There is an FTP site with usercontributed .m files to do Simplex located at ftp://ftp.mathworks.com/pub/contrib/optim/simplex1. There's a Usenet newsgroup on MATLAB: comp.softsys.matlab. If speed matters to you, then according to a Usenet posting by Pascal Koiran (koiran@enslyon.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.) Commercial codes and modeling systems If your models prove to be too difficult for free or addon 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 standalone 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, InteriorPoint) important to you? Do you need an interface to a spreadsheet code? Is the purchase price an overriding concern? If you are at a university, is the software offered at an academic discount? How much hotline support do you think you'll need? There is usually a large difference in LP codes, in performance (speed, numerical stability, adaptability to computer architectures) and in features, as you climb the price scale. In the following table is a condensed version of a survey of LP software that appeared in the June 1992 issue of OR/MS Today (a publication of INFORMS) and that has subsequently been updated in the October 1995 and April 1997 issues. Consult the full survey for more detailed information, or click on the product names to browse their developers' web pages. The table is in two parts, the first consisting of packages that are primarily algorithmic codes, and the second containing modeling systems. Product names are linked to product or developer web sites where known. Under "Platform" is an indication of common environments in which the code runs, with the choices being PCDOS and/or versions of Microsoft Windows (PC), Macintosh OS (M), and Unix on various computer types (U). For other possibilities, check the full survey or contact the vendor. Even more so than usual, I emphasize that you must use this information at your own risk. I cannot guarantee that every entry is completely correct and uptodate, but I will gladly correct any mistakes that are pointed out to me. Key to Features: S=Simplex I=InteriorPoint or Barrier Q=Quadratic G=GeneralNonlinear M=MIP N=Network V=Visualization Solver Product Features Platform Phone Email address CPLEX SIMNQ PC M U 7028317744 info@cplex.com CWHIZ SM PC U 7034123201 ketronms@erols.com FortMP SIMQ PC U 6309712337 naginfo@nag.com +44 hossein@unicom.co.uk 1895256484 HIPLEX S PC U +44 i.maros@ic.ac.uk 1715948334 HS/LP SM PC 2016271424 info@haverly.com ILOG Planner M PC U 4153909000 info@ilog.com LAMPS SM PC U +44 info@amsoft.demon.co.uk 1818708882 LINDO SMQ PC 3129887422 info@lindo.com LOQO GI PC U 6092580876 rvdb@princeton.edu LPS867 SM PC U 6097376800 info@main.aae.com LSXLSOL SM PC 7028310300 info@frontsys.com MINOS SQG PC 4159628719 sales@sbsisoloptimize.com MINTO M U 4048946287 martin.savelsbergh@isye.gatech.edu MPSIII SMN PC U 7034123201 ketronms@erols.com OSL SIMNQ PC U 9144334740 osl@vnet.ibm.com SAS/OR SMNGQ PC M U 9196778000 saseph@unx.sas.com SCICONIC SM PC U +44 msukwt03.gztltm@eds.com 1908284188 SOPT SIMGQ PC U 7322644700 saitech@monmouth.com +81 335302644 XA SM PC M U 8184411565 sunsetsw@ix.netcom.com XPRESSMP SIMQ PC M 2028870296 info@dash.co.uk +44 1604858993 Modeling Product Platform Phone Email address AIMMS PC +31 235350935 info@paragon.nl AMPL PC U 7023227600 info@ampl.com ANALYZE PC 3037967830 hgreenbe@carbon.cudenver.edu DecisionPRO PC 9198594101 vginfo@vanguardsw.com DATAFORM PC U 7034123201 ketronms@erols.com GAMS PC U 2023420180 sales@gams.com LINGO PC U 8004412378 info@lindo.com MathPro PC U 2028870296 mathpro@erols.com MIMI PC U 9084648300 info@chesapeake.com MODLER PC U 3037967830 hgreenbe@carbon.cudenver.edu MPL PC 7035227900 info@maximalusa.com OMNI PC U 2016271424 info@haverly.com VMP PC U 3016224319 jwelch@sundownvmp.com What's Best! PC M U 8004412378 info@lindo.com Visual XPRESS PC 2028870296 info@dash.co.uk +44 1604858993 Free demos of commercial codes An increasing number of commercial LP software developers are making demo or academic versions available for downloading through web sites or as addons to book packages. Typically these versions are limited in the size of problem they accept or the length of time that they will operate, or are made available only for "academic use" (mainly research or teaching at universities). Nevertheless, they have most or all of the features of the full versions. Most run under several variations of Microsoft Windows on PCs, and/or certain Unix workstations; check the relevant web pages for details. Downloadable free demos include: * AIMMS with XA and CONOPT * ANALYZE, MODLER and RANDMOD * LINDO and What's Best! * LOQO with a builtin AMPL interface * MPL with CPLEX * Visual XPRESS with XPRESSMP Books that are packaged with demo software include: * A. Brooke, D. Kendrick and A. Meeraus, GAMS: A Users' Guide, Wadsworth Publishing Co/Duxbury Press, ISBN 0894262157. * R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Wadsworth Publishing Co/Duxbury Press, ISBN 0534509835. * H.J. Greenberg, Modeling by ObjectDriven Linear Elemental Relations: A User's Guide for MODLER, Kluwer Academic Publishers, ISBN 0792393236. * L. Schrage, Optimization Modeling with LINDO, LINDO Systems, order directly from developer. Many developers are also willing to arrange for you to "borrow" copies of their fullfeatured versions for purposes of evaluation. Details vary, however, so you'll have to check with each vendor whose product you're interested in. [ ] Q3. "Oh, and we also want to solve it as an integer program." A: Integer LP models are ones whose variables are constrained to take integer or whole number (as opposed to fractional) values. It may not be obvious that integer programming is a very much harder problem than ordinary linear programming, but that is nonetheless the case, in both theory and practice. Integer models are known by a variety of names and abbreviations, according to the generality of the restrictions on their variables. Mixed integer (MILP or MIP) problems require only some of the variables to take integer values, whereas pure integer (ILP or IP) problems require all variables to be integer. Zeroone (or 01 or binary) MIPs or IPs restrict their integer variables to the values zero and one. (The latter are more common than you might expect, because many kinds of combinatorial and logical restrictions can be modeled through the use of zeroone variables.) For the sake of generality, the following disucssion uses the term MIP to refer to any kind of integer LP problem; the other kinds can be viewed as special cases. MIP, in turn, is a particular member of the class of combinatorial or discrete optimization problems. In fact the problem of determining whether a MIP has an objective value less than a given target is a member of the class of "NPcomplete" problems, all of which are very hard to solve (at least as far as anyone has been able to tell). Since any NPcomplete problem is reducible to any other, virtually any combinatorial problem of interest can be attacked in principle by solving some equivalent MIP. This approach sometimes works well in practice, though it is by no means infallible. People are sometimes surprised to learn that MIP problems are solved using floating point arithmetic. Most available generalpurpose largescale MIP codes use a procedure called "branchandbound" to search for an optimal integer solution by solving a sequence of related LP "relaxations" that allow some fractional values. Good codes for MIP distinguish themselves primarily by solving shorter sequences of LPs, and secondarily by solving the individual LPs faster. (The similarities between successive LPs in the "search tree" can be exploited to speed things up considerably.) Even more so than with regular LP, a costly commercial code may prove its value if your MIP model is difficult. Another solution approach known generally as constraint logic programming (CLP) has drawn increasing interest of late. Having their roots in studies of logical inference in artificial intelligence, CLP codes typically do not proceed by solving any LPs. As a result, compared to branchandbound they search "harder" but faster through the tree of potential solutions. Their greatest advantage, however, lies in their ability to tailor the search to many constraint forms that can be converted only with difficulty to the form of an integer program; their greatest success tends to be with "highly combinatorial" optimization problems such as scheduling, sequencing, and assignment, where the construction of an equivalent IP would require the definition of large numbers of zeroone variables. More information and a list of available codes can be found in the Constraints FAQ (also posted to the newsgroup comp.constraints). Whatever your solution technique, you should be prepared to devote far more computer time and memory to solving a MIP problem than to solving the corresponding LP relaxation. (Or equivalently, you should be prepared to solve much smaller MIP problems than LP problems using a given amount of computer resources.) To further complicate matters, the difficulty of any particular MIP problem is hard to predict (in advance, at least!). Problems in no more than a hundred variables can be challenging, while others in tens of thousands of variables solve readily. The best explanations of why a particular MIP is difficult often rely on some insight into the system you are modeling, and even then tend to appear only after a lot of computational tests have been run. A related observation is that the way you formulate your model can be as important as the actual choice of solver. Thus a MIP problem with hundreds of variables (or more) should be approached with a certain degree of caution and patience. A willingness to experiment with alternative formulations and with a MIP code's many search options often pays off in greatly improved performance. In the hardest cases, you may wish to abandon the goal of a provable optimum; by terminating a MIP code prematurely, you can often obtain a highquality solution along with a provable upper bound on its distance from optimality. A solution whole objective value is within some fraction of 1% of optimal may be all that is required for your purposes. (Indeed, it may be an optimal solution. In contrast to methods for ordinary LP, procedures for MIP may not be able to prove a solution to be optimal until long after they have found it.) 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 01 MIP models. See also the brief discussion of Genetic Algorithms and Simulated Annealing in the Nonlinear Programming FAQ. 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. In general these models have a "unimodular" constraint matrix of some sort, but by far the bestknown and most widely used models of this kind are the socalled pure network flow models. It turns out that such problems are best solved by specialized routines, usually based on the simplex method, that are much faster than any generalpurpose LP methods. See the section on Network models for further information. Commercial MIP codes are listed with the commercial LP codes and modeling systems above. The April 1994 issue of OR/MS Today contains a survey of MIP codes, which largely overlaps the content of the earlier survey on LP: "Survey: Mixed Integer Programming" by Matthew Saltzman, pp 4251. The following are notes on some publicly available codes for MIP problems. * The public domain code lp_solve, mentioned earlier, accepts MIP models. * Peter Barth has announced opbdp, an implementation in C++ of an implicit enumeration algorithm for solving linear 01 optimization problems. The algorithm compares well with commercial linear programmingbased branchandbound on a variety of standard 01 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 also available via anonymous ftp at ftp://ftp.mpisb.mpg.de/pub/guide/staff/barth/opbdp/opbdp.tar.Z along with a Postscriptformat technical report (in file mpii952002.ps) describing the techniques used. * 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 zipcompressed 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 archiveserver@bilkent.edu.tr. * Bob Craig of Lucent Technologies (kat3@ihgpebb.ih.lucent.com) has software written in C, which implements Balas' enumerative algorithm for solving 01 ILP, that he is willing to make available to those who request it. [ ] Q4. "I wrote an optimization code. Where are some test models?" A: If you want to try out your code on some realworld LP models, there is a very nice collection of smalltomediumsize 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 LPspecific 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 http://www.caam.rice.edu/~bixby/miplib/miplib.html. FTP users can use ftp://ftp.caam.rice.edu/pub/people/bixby/miplib. Or, 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/. (Alternate address: ftp://elib.zibberlin.de/pub/mptestdata/tsp.) A Web version is at http://www.iwr.uniheidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html. For network flow problems, there are some generators and instances collected at DIMACS. The NETGEN and GNETGEN generator can be downloaded from netlib. Generators and instances for multicommodity network flow problems are maintained by the Operations Research group in the Department of Computer Science at the University of Pisa. The commercial modeling language GAMS comes with about 160 test models, which you might be able to test your code with. AIMMS also comes with some test models. There is a collection called MPTESTDATA available at KonradZuseZentrum fuer Informationstechnik Berlin (ZIB) in ftp://elib.zibberlin.de/pub/mptestdata. 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, setparti, steinertree, tsp, vehiclerout, and generators. John Beasley maintains the ORLib, 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/. 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 106972. If you can't access these resources, send email 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/ 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 socalled header cards, which are distinguished by their starting in column 1. Although it is typical to use uppercase throughout the file (like I said, MPS has long historical roots), many MPSreaders will accept mixedcase for anything except the header cards, and some allow mixedcase 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 postprocessing 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 equationoriented 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 lessthan ( <= ) rows, G for greaterthan ( >= ) rows, and N for nonconstraining 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 Amatrix 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 righthandside 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 nonzero values in all 3 of the constraint rows of the problem. Rows not mentioned in an RHS vector would be assumed to have a righthandside 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 nonnegative (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. Topics briefly covered: Q6.1: "What is a modeling language?" A: There is more to linear programming (or integer programming) than optimal solutions and numbercrunching. This can be appreciated by observing that modern LP software comes in two related but very different kinds of packages: * Algorithmic codes are devoted to finding optimal solutions to specific linear programs. A code takes as input a compact listing of the LP constraint coefficients (the A, b, c and related values in the standard form) and produces as output a similarly compact listing of optimal solution values and related information. * Modeling systems are designed to help people formulate LPs and analyze their solutions. An LP modeling system takes as input a description of a linear program in a form that people find reasonably natural and convenient, and allows the solution output to be viewed in similar terms; conversion to the forms requried by algorithmic codes is done automatically. The collection of statement forms for the input is often called a modeling language. Most modeling systems support a variety of algorithmic codes, while the more popular codes can be used with many different modeling systems. Because packages of the two kinds are often bundled for convenience of marketing or operation, the distinction between them is sometimes obscured, but it is important to keep in mind when sorting through the many possibilities. See under Commercial Codes and Modeling Systems elsewhere in this FAQ for a list of modeling systems available. There are no free ones of note, but many do offer free demo versions. Common alternatives to modeling languages and systems include spreadsheet front ends to optimization, and custom optimization applications written in generalpurpose programming languages. You can find a discussion of the pros and cons of these approaches in What Modeling Tool Should I Use? on the Frontline Systems web site. Q6.2: "How do I diagnose an infeasible LP model?" A: A linear program 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 (or elastic 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 feasible solution (at a possibly unbearable cost); constraints that have large slack values in the "optimal" solution are prime suspects as causes of infeasibility in the original LP. (Many modelers recommend a an elastic programming philosophy even if you aren't having trouble achieving feasibility; the idea is that almost any constraint can be violated, for a great enough price.) Another approach is to apply auxiliary algorithms that identify constraints or groups of constraints that can be considered to "cause" the infeasibility in an LP. A software system called ANALYZE was developed by Harvey Greenberg to provide computerassisted analysis, including rulebased intelligence; he has also compiled a bibliography of more than 400 references on the subject of model analysis. 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 socalled Irreducible Infeasible Subset; the IIS feature is now available in CPLEX (command "display iis"), OSL, and LINDO (command "debug"). As a final comment, commercial codes sometimes have other builtin 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 01 variables to turn the slacks off or on. Then minimize on the sum of these 01 variables. John Chinneck (chinneck@sce.carleton.ca) has modified his MINOS(IIS) extension to find the Irreducible Infeasible Subset as explained in 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 an LP model has a feasible solution is essentially as hard as actually 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. For MIP models, it's also difficult  if there exists no feasible solution, then you must go through the entire Branch and Bound procedure (or whatever algorithm you use) to prove this. 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: If you have several objectives, then you may find that they cannot all be optimized by any one solution. Instead, you will need to look for a solution or solutions that achieve an acceptable tradeoff between objectives. Deciding what tradeoffs are "acceptable" is a topic of investigation in its own right. You may want to consult MCDM WorldScan, the newsletter of the International Society on Multiple Criteria Decision Making. There are a few free software packages specifically for multiple objective linear programming, including: * ADBASE 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 306026255. * PROTASS is also available. Currently its web page is in Polish, but you can write to protass@free.polbox.pl. * NIMBUS is an interactive multiobjective optimization system that has a Web interface. Other approaches that have worked are: * Goal Programming (treat the objectives as constraints with costed slacks), or, almost equivalently, form a composite function from the given objective functions; * Pareto preference analysis (essentially brute force examination of all vertices); * 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 almostindependent 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 DantzigWolfe 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 ndimensional space." A: There is a program called qhull, available at ftp://geom.umn.edu/pub/software/. 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://ifor13.ethz.ch/pub/fukuda/ 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.belllabs.com/netlib/voronoi/hull.shar.Z. There is a directory in ftp://elib.zibberlin.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/, in file VE041.Z. Q6.8: "Are there any parallel LP codes?" A: The vendors for OSL, CPLEX and XPRESSMP each have announced parallel implementations of Branch and Bound solvers for MIP. CPLEX has also announced parallel implementations of its barrier and dual simplex algorithms on the Silicon Graphics Power Challenge, and OSL likewise has a parallel implementation of its barrier method for its SP2 system. 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. 10421066. 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 realworld 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 paralleldense 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 largescale considerations are important. Writing even a singleprocessor largescale LP code is a multiyear 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: In the context of linear programming, the term "network" is most often associated with the minimumcost network flow problem. A network for this problem is viewed as a collection of nodes (or circles or locations) and arcs (or lines or routes) connecting selected pairs of nodes. Arcs carry a physical or conceptual flow of some kind, and may be directed (oneway) or undirected (twoway). Some nodes may be sources (permitting flow to enter the network) or sinks (permitting flow to leave). The network linear programming problem is to minimize the (linear) total cost of flows along all arcs of a network, subject to conservation of flow at each node, and upper and/or lower bounds on the flow along each arc. This is a special case of the general linear programming problem. The transportation problem is an even more special case in which the network is bipartite: all arcs run from nodes in one subset to the nodes in a disjoint subset. A variety of other wellknown network problems, including shortest path problems, maximum flow problems, and certain assignment problems, can also be modeled and solved as network linear programs. Details are presented in many books on linear programming and operations research. Network linear programs can be solved 10 to 100 times faster than general linear programs of the same size, by use of specialized optimization algorithms. Some commercial LP solvers include a version of the network simplex method for this purpose. That method has the nice property that, if it is given integer flow data, it will return optimal flows that are integral. Integer network LPs can thus be solved efficiently without resort to complex integer programming software. Unfortunately, many different network problems of practical interest do not have a formulation as a network LP. These include network LPs with additional linear "side constraints" (such as multicommodity flow problems) as well as problems of network routing and design that have completely different kinds of constraints. In principle, nearly all of these network problems can be modeled as integer programs. Some "easy" cases can be solved much more efficiently by specialized network algorithms, however, while other "hard" ones are so difficult that they require specialized methods that may or may not involve some integer programming. Contrary to many people's intuition, the statement of a hard problem may be only marginally more complicated than the statement of some easy problem. A canonical example of a hard network problem is the "traveling salesman" problem of finding a shortest tour through a network that visits each node once. A canonical easy problem not obviously equivalent to a linear program is the "minimum spanning tree" problem to find a leastcost collection of arcs that connect all the nodes. But if instead you want to connect only some given subset of nodes (the "Steiner tree" problem) then you are faced with a hard problem. These and many other network problems are described in some of the references below. Software for network optimization is thus in a much more fragmented state than is generalpurpose software for linear programming. The following are some of the implementations that are available for downloading. Most are freely available for many purposes, but check their web pages or "readme" files for details. * ASSCT, an implementation of the Hungarian Method for the Assignment problem (#548 from Collected Algorithms of the ACM). * GIDEN, an interactive graphical environment for a variety of network problems and algorithms, available as a Java application or as an applet that can be executed through any Javaenabled Web browser. Further information is available by writing to giden@iems.nwu.edu. * MCF, a C implementation of the network simplex method (from Andreas Loebel, loebel@zib.de). * Netflo, the Fortran network simplex code from [Kennington], and several codes for maximum matching and maximum flow problems (from DIMACS, help@dimacs.rutgers.edu) * PPRN, for single or multicommodity network flow problems having a linear or nonlinear objective function, optionally with linear side constraints, by Jordi Castro (jcastro@etse.urv.es) * RELAXIV for minimumcost network flows (by Dimitri Bertsekas, bertsekas@lids.mit.edu and Paul Tseng, tseng@math.washington.edu); also a C++ version of the RELAXIV algorithm (at the Department of Computer Science, University of Pisa, frangio@di.unipi.it) The following indexes may also be useful: * Network optimization codes in Fortran 77 and in C, compiled by Ernesto Martins (eqvm@mat.uc.pt) * The network optimization library, including codes for assignment, shortest path, minimumcost flow, and maximum flow/minimum cut, by Andrew Goldberg (avg@research.nj.nec.com). * Optimization routines for networks and graphs in the listing of publicdomain optimization codes maintained by Jiefeng Xu (Jiefeng.Xu@Colorado.edu). * Network optimization listings from the NEOS Guide. Fortran code for the Assignment Problem and others can also be copied from[Burkard] and from [Martello]. 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. Public domain code for the Asymmetric TSP is available in TOMS routine #750 available at ftp://netlib2.cs.utk.edu/toms/750; it is documented in [Carpaneto]. 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]. Another good one is [Reinelt]. There are some heuristics for getting a "good" solution in the article by Lin and Kernighan in Operations Research, Vol 21 (1973), pp 498516. [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 Lucent Technologies (kat3@ihgpebb.ih.lucent.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@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 Lucent Technologies (kat3@ihgpebb.ih.lucent.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,407423) 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 TwoStage Programming'', Lecture Notes in Economics & Math. Systems #392 (SpringerVerlag). 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. JB. Wets, eds., Numerical Techniques for Stochastic Optimization (Series in Comp. Math. 10, SpringerVerlag, 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 postoptimal 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, resolving the model as an LP, and doing standard postoptimal 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 goalprogramming formulation; perhaps your desire to see postoptimal 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 socalled 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 socalled "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). Q6.15: "How can I combat cycling in the Simplex algorithm?" A: Cycling is the condition that occurs when the Simplex method gets "stuck" and finds itself repeating the same vertices over and over. While this specific behavior is rather rare in practice, it is quite common for the algorithm to reach a point where it temporarily stops making forward progress in terms of improvement in the objective function; this is termed "stalling", or more loosely known as "degeneracy" since it is caused by one or more basic variables taking on the value of a lower or upper bound. In most cases, the algorithm will work through this nest of coincident vertices, then resume making tangible progress. However, in extreme cases the degeneracy is so bad that to all intents and purposes it can be considered cycling. The simplest answer to the problem of degeneracy/cycling is often to "get a better optimizer", i.e. one with stronger pricing algorithms, and a better selection of features. However, obviously that is not always an option (money!), and even the best LP codes can run into degeneracy on certain models. Besides, they say it's a poor workman who blames his tools. So, when one cannot change the optimizer, it's expedient to change the model. Not drastically, of course, but a little "noise" can usually help to break the ties that occur during the Simplex method. A procedure that can work nicely is to add, to the values in the RHS, random values roughly six orders of magnitude smaller. Depending on your model's formulation, such a perturbation may not even seriously affect the quality of the solution values. However, if you want to switch back to the original formulation, the final solution basis for the perturbed model should be a useful starting point for a "cleanup" optimization phase. (Depending on the code you are using, this may take some ingenuity to do, however.) Another helpful tactic: if your optimization code has more than one solution algorithm, you can alternate among them. When one algorithm gets stuck, begin again with another algorithm, using the most recent basis as a starting point. For instance, alternating between a primal and a dual method can move the solution away from a nasty point of degeneracy. Using partial pricing can be a useful tactic against true cycling, as it tends to reorder the columns. And of course Interior Point algorithms are much less affected by (though not totally immune to) degeneracy. Unfortunately, the optimizers richest in alternate algorithms and features also tend to be least prone to problems with degeneracy in the first place. [ ] Q7. "What references and web links 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 ORCSL 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]. General reference * Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, NorthHolland, 1989. (Very broadreaching, with large bibliography. Good reference; it's the place I tend to look first. Expensive, and tough reading for beginners.) * Harvey Greenberg has compiled an online Mathematical Programming Glossary. Books containing source code * Best and Ritter, Linear Programming: active set analysis and computer programs, PrenticeHall, 1985. * Bertsekas, D.P., Linear Network Optimization: Algorithms and Codes, MIT Press, 1991. * Bunday and Garside, Linear Programming in Pascal, Edward Arnold Publishers, 1987. * Bunday, Linear Programming in Basic (presumably the same publisher). * Burkard and Derigs, Springer Verlag Lecture Notes in Math Systems #184 (the Assignment Problem and others). * Kennington & Helgason, Algorithms for Network Programming, Wiley, 1980. (A special case of LP; contains Fortran source code.) * Lau, H.T., A Numerical Library in C for Scientists and Engineers , 1994, CRC Press. (Contains a section on optimization.) * Martello and Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990. (Contains Fortran code, comes with a disk  also covers Assignment Problem.) * Press, Flannery, Teukolsky & Vetterling, Numerical Recipes, Cambridge, 1986. (Comment: use their LP code with care.) * Syslo, Deo & Kowalik, Discrete Optimization Algorithms with Pascal Programs, PrenticeHall (1983). (Contains code for 28 algorithms such as Revised Simplex, MIP, networks.) LP textbooks * Bazaraa, Jarvis and Sherali. Linear Programming and Network Flows. Grad level. * Bertsimas, Dimitris and Tsitsiklis, John, Introduction to Linear Optimization. Athena Scientific, 1997 (ISBN 1886529191). Graduatelevel text on linear programming, network flows, and discrete optimization. * Chvatal, Linear Programming, Freeman, 1983. Undergrad or grad. * Daellenbach and Bell, A User's Guide to LP. Good for engineers, but may be out of print. * Ecker & Kupferschmid, Introduction to Operations Research. * Ignizio, J.P. & Cavalier, T.M., Linear Programming, Prentice Hall, 1994. Covers usual LP topics, plus interior point, multiobjective and heuristic techniques. * Luenberger, Introduction to Linear and Nonlinear Programming, Addison Wesley, 1984. Updated version of an old standby. * Murtagh, B., Advanced Linear Programming, McGrawHill, 1981. Good one after you've read an introductory text. * Murty, K., Linear and Combinatorial Programming. * Nash, S., and Sofer, A., Linear and Nonlinear Programming, McGrawHill, 1996. * Nazareth, J.L., Computer Solution of Linear Programs, Oxford University Press, New York and Oxford, 1987. * Nering, E.D. & Tucker, A.W., Linear Programs and Related Problems, Academic Press, 1993. * Saigal, R., Linear Programming: A Modern Integrated Analysis, Kluwer Academic Publishers, 1995. * Schrijver, A., Theory of Linear and Integer Programming, Wiley, 1986. Advanced. * Taha, H., Operations Research: An Introduction, 1987. * Thie, P.R., An Introduction to Linear Programming and Game Theory, Wiley, 1988. * Vanderbei, Robert J., Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1996 (ISBN 0792398041). Balanced coverage of simplex and interiorpoint methods. Source code available online for all algorithms presented. * Williams, H.P., Model Building in Mathematical Programming, Wiley 1993, 3rd edition. Little on algorithms, but excellent for learning what makes a good model. InteriorPoint LP methods (descendants of "Karmarkar's algorithm") * Arbel, Ami, Exploring InteriorPoint Linear Programming, MIT Press, 1993. Includes smallscale IBM PC software (binary only). * Fang and Puthenpura, Linear Optimization and Extensions. (Grad level textbook, also contains some Simplex and Ellipsoid. I heard mixed opinions on this one.) * 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. 114. Followed by commentary articles, and a rejoinder by the authors. * Roos, Terlaky and Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley, Chichester, 1997 * Wright, Stephen J., PrimalDual InteriorPoint Methods. SIAM Publications, 1997. Covers theoretical, practical and computational aspects of the most important and useful class of interiorpoint algorithms. The web page for this book contains current information on interiorpoint codes for linear programming, including links to their web sites. Presentations of commercially marketed systems (usable as texts for some classes) * Bisschop & Entriken, AIMMS: The Modeling System, Paragon Decision Technology, 1993. * Brooke, Kendrick & Meeraus, GAMS: A Users' Guide, The Scientific Press/Duxbury Press, 1988. * Fourer, Gay & Kernighan, AMPL: A Modeling Language for Mathematical Programming, The Scientific Press/Duxbury Press, 1992. (Comes with DOS "student" version including MINOS and CPLEX.) * Greenberg, H.J., Modeling by ObjectDriven Linear Elemental Relations: A User's Guide for MODLER, Kluwer Academic Publishers, 1993. * Schrage, L., LINDO: An Optimization Modeling System, The Scientific Press/Duxbury Press, 1991. Additional books * Ahuja, Magnanti & Orlin, Network Flows, Prentice Hall, 1993. * Beasley, J.E., ed., Advances in Linear and Integer Programming. Oxford University Press, 1996 (ISBN 0198538561). Each chapter is a selfcontained essay on one aspect of the subject. * Bondy & Murty, Graph Theory with Applications. * Edelsbrunner, Algorithms in Combinatorial Geometry, Springer Verlag, 1987. * Forsythe, Malcolm & Moler, Computer Methods for Mathematical Computations, PrenticeHall. * Gill, Murray and Wright, Numerical Linear Algebra and Optimization, AddisonWesley, 1991. * Greenberg, H.J., A ComputerAssisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE, Kluwer Academic Publishers, 1993. * Hwang & Yoon, Multiple Attribute Decision Making : Methods and Applications, SpringerVerlag, Lecture Notes #186. * Lawler, Lenstra, et al, The Traveling Salesman Problem, Wiley, 1985. * More' & Wright, Optimization Software Guide, SIAM Publications, 1993. See also the NEOS Guide to Optimization Software. * Murty, Network Programming, Prentice Hall, 1992. * Papadimitriou & Steiglitz, Combinatorial Optimization. (Also contains a discussion of complexity of Simplex method.) * 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.) * Reinelt, G., The Travelling Salesman: Computational Solutions for TSP Applications, SpringerVerlag Lecture Notes in Computer Science #840, 1994. Other publications * Avis & Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra", Discrete and Computational Geometry, 8 (1992), 295313. * Balas, E. and Martin, C., "Pivot And Complement: A Heuristic For 01 Programming Problems", Management Science, 1980, Vol 26, pp 8696. * Balinski, M.L., "An Algorithm for Finding all Vertices of Convex Polyhedral Sets", SIAM J. 9, 1, 1961. * Carpaneto, Dell'amico & Toth, "A Branchandbound Algorithm for Large Scale Asymmetric Travelling Salesman Problems", ACM Transactions on Mathematical Software (TOMS), December 1995. * 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. 167185. * Seidel, "Constructing HigherDimensional Convex Hulls at Logarithmic Cost per Face", 1986, 18th ACM STOC, 404413. * Smale, Stephen, "On the Average Number of Steps in the Simplex Method of Linear Programming", Math Programming 27 (1983), 241262. * Swart, "Finding the Convex Hull Facet by Facet", Journal of Algorithms, 6 (1985), 1748. * Volgenant, A., Symmetric TSPs, European Journal of Operations Research, 49 (1990) 153154. OnLine Sources of Papers and Bibliographies * Michael Trick's Operations Research Page at http://mat.gsia.cmu.edu/ * Optimization Technology Center: home of NEOS, NetworkEnabled Optimization System. * WORMS (WorldWideWeb for Operations Research and Management Science) at http://www.maths.mu.oz.au/~worms/ * List of interesting optimization codes in public domain at http://ucsu.colorado.edu/~xu/software.html. Includes many of the codes listed here, plus others of interest for specific problem classes. * Computational Mathematics Archive (London and South East Centre for High Performance Computing) http://www.lpac.ac.uk/SELHPC/Articles/GeneratedHtml/math.opt.html * Bibliography of books and survey papers on combinatorial optimization compiled by Brian Borchers (borchers@nmt.edu), ftp://archives.math.utk.edu/teaching.materials/bibliography/. * Bibliography of books and papers on InteriorPoint methods (taking more than 400 kilobytes storage with over 1300 entries!?!) in ftp://netlib2.cs.utk.edu/bib/intbib.bib, compiled by Dr. Eberhard Kranich (puett@math.uniwuppertal.de). * InteriorPoint Methods Online (another service of NEOS) contains most new reports in the area of interiorpoint methods that have appeared since December 1994 (over 200 reports as of March 1997). Abstracts for all reports are available, as are links to postscript source for most reports . A mailing list is used to notify interested parties whenever a new report arrives. You can join the list through a web page, or you can send mail to interiorpointmethodsrequest@mcs.anl.gov containing the single word subscribe. * Information related to Semidefinite Programming is at ftp://orion.uwaterloo.ca/pub/henry/teaching/co769g/ * An extensive bibliography for stochastic programming has been compiled by Maarten van der Vlerk at http://mally.eco.rug.nl/biblio/stoprog.html. * INFORMS home page is at http://www.informs.org/. * IMPS Consortium is at http://wwwmath.cudenver.edu/~hgreenbe/imps.html OnLine Sources of Optimization Services The following web sites offer, in some sense, to run your optimization problem and return a result. Check their home pages for details, which vary considerably. (Some are intended for nonlinear programming, but are included here for completeness.) * DecisionNet. Provides access to "a distributed collection of decision technologies," including linear programming, "that are made available for execution over the World Wide Web. These technologies are developed and maintained locally by their providers. DecisionNet contains technology metainformation necessary to guide consumers in search, selection, and execution of these technologies." Facilities for submitting problems in popular modeling language formats are currently being tested. * GIDEN. An interactive graphical environment for a variety of network optimization problems and algorithms. It is written in Java, so you can try it out through any Javaenabled Web browser. * IBM Optimization Subroutine Library (OSL). Linear and quadratic programs in MPS format may be submitted by anonymous ftp. * Internet Enabled HQP Optimization Service. Nonlinear problems in SIF format may be submitted by email. * MILP by Dmitry V. Golovashkin. Smallscale mixedinteger programs in a simple algebraic format are solved through a web form interface. * NetworkEnabled Optimization System (NEOS) Server. Offers access to about a dozen solvers for linear and nonlinear programming, network and stochastic linear programming, unconstrained and boundconstrained optimization of nonlinear functions, and nonlinear complementarity. Linear programs in MPS format and nonlinear problems in the form of a C or Fortran program may be submitted by sending email, by submitting URLs through a Web page, or via a highspeed socketbased Unix interface. Linear and nonlinear programs in the AMPL modeling language can also be sent to some of the solvers, by email or URL. * NIMBUS. A multiobjective optimization system that accepts algebraic problem specifications through a series of Web forms. * Numerica. Global nonlinear optimization problems may be submitted in Numerica's algebraic modeling language, through a web form interface. [ ] 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.belllabs.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 email 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: * Norway netlib@nac.no * England netlib@ukc.ac.uk * Germany anonymous@elib.zibberlin.de * Taiwan netlib@nchc.edu.tw * 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: This list was established by John W. Gregory (ashbury@skypoint.com), and is currently being maintained by Robert Fourer (4er@iems.nwu.edu) and the Optimization Technology Center. This article is Copyright 1997 by Robert Fourer and 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 any organization. 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 for this), you may use: Fourer, Robert (4er@iems.nwu.edu) and Gregory, John W. (ashbury@skypoint.com), "Linear Programming FAQ" (1997). World Wide Web http://www.mcs.anl.gov/home/otc/ faq/linearprogrammingfaq.html, Usenet sci.answers, anonymous FTP /pub/usenet/sci.answers/ linearprogrammingfaq from rtfm.mit.edu. There's a mail server on rtfm.mit.edu, so if you don't have FTP privileges, you can send an email message to mailserver@rtfm.mit.edu containing: send usenet/sci.answers/linearprogrammingfaq 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 crossposted to news.answers and sci.opresearch. Suggestions, corrections, topics you'd like to see covered, and additional material are all solicited. Send email to 4er@iems.nwu.edu. [ ] END linearprogrammingfaq User Contributions:Comment about this article, ask questions, or add new information about this topic:
[ Usenet FAQs  Web FAQs  Documents  RFC Index ]
Send corrections/additions to the FAQ Maintainer: 4er@iems.nwu.edu (Robert Fourer)
Last Update March 27 2014 @ 02:11 PM
