home *** CD-ROM | disk | FTP | other *** search
- Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!nntprelay.mathworks.com!newsfeed.internetmci.com!128.174.5.49!vixen.cso.uiuc.edu!newsfeed.acns.nwu.edu!news.acns.nwu.edu!4er
- From: 4er@iems.nwu.edu (Robert Fourer)
- Newsgroups: sci.op-research,sci.answers,news.answers
- Subject: Linear Programming FAQ
- Followup-To: sci.op-research
- Date: 1 Nov 1997 22:55:22 GMT
- Organization: Northwestern University, Evanston, IL, US
- Lines: 1711
- Approved: news-answers-request@MIT.Edu
- Distribution: world
- Expires: 12/03/97
- Message-ID: <63gc0q$8lu@news.acns.nwu.edu>
- Reply-To: 4er@iems.nwu.edu (Robert Fourer)
- NNTP-Posting-Host: scherzo.iems.nwu.edu
- Summary: A List of Frequently Asked Questions about Linear Programming
- Keywords: FAQ, LP, Linear Programming
- Originator: 4er@scherzo.iems.nwu.edu
- Xref: senator-bedfellow.mit.edu sci.op-research:8533 sci.answers:7322 news.answers:115956
-
- Posted-By: auto-faq 2.4
- Archive-name: linear-programming-faq
- Last-modified: November 1, 1997
-
- [ ]
-
- Linear Programming
- Frequently Asked Questions
-
- Optimization Technology Center of
- Northwestern University and Argonne National Laboratory
- [ ] Posted monthly to Usenet newsgroup sci.op-research
-
- World Wide Web version:
- http://www.mcs.anl.gov/home/otc/Guide/faq/linear-programming-faq.html
- Plain-text version:
- ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq
-
- 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 almost-independent matrix
- blocks that are linked by a few constraints. Can I take advantage
- of this?"
- o Q6.7: "I am looking for an algorithm to compute the convex hull of
- a finite number of points in n-dimensional space."
- o Q6.8: "Are there any parallel LP codes?"
- o Q6.9: "What software is there for Network models?"
- o Q6.10: "What software is there for the Traveling Salesman Problem
- (TSP)?"
- o Q6.11: "What software is there for the Knapsack Problem?"
- o Q6.12: "What software is there for Stochastic Programming?"
- o Q6.13: "I need to do post-optimal analysis."
- o Q6.14: "Do LP codes require a starting vertex?"
- 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
- so-called Standard Form):
-
- minimize cx
- subject to Ax = b
- x >= 0
-
- where x is the vector of variables to be solved for, A is a matrix of known
- coefficients, and c and b are vectors of known coefficients. The expression
- "cx" is called the objective function, and the equations "Ax=b" are called
- the constraints. All these entities must have consistent dimensions, of
- course, and you can add "transpose" symbols to taste. The matrix A is
- generally not square, hence you don't solve an LP by just inverting A.
- Usually A has more columns than rows, and Ax=b is therefore quite likely to
- be under-determined, leaving great latitude in the choice of x with which to
- minimize cx.
-
- The word "Programming" is used here in the sense of "planning"; the
- necessary relationship to computer programming was incidental to the choice
- of name. Hence the phrase "LP program" to refer to a piece of software is
- not a redundancy, although I tend to use the term "code" instead of
- "program" to avoid the possible ambiguity.
-
- Although all linear programs can be put into the Standard Form, in practice
- it may not be necessary to do so. For example, although the Standard Form
- requires all variables to be non-negative, most good LP software allows
- general bounds l <= x <= u, where l and u are vectors of known lower and
- upper bounds. Individual elements of these bounds vectors can even be
- infinity and/or minus-infinity. This allows a variable to be without an
- explicit upper or lower bound, although of course the constraints in the
- A-matrix will need to put implied limits on the variable or else the problem
- may have no finite solution. Similarly, good software allows b1 <= Ax <= b2
- for arbitrary b1, b2; the user need not hide inequality constraints by the
- inclusion of explicit "slack" variables, nor write Ax >= b1 and Ax <= b2 as
- two separate constraints. Also, LP software can handle maximization problems
- just as easily as minimization (in effect, the vector c is just multiplied
- by -1).
-
- The importance of linear programming derives in part from its many
- applications (see further below) and in part from the existence of good
- general-purpose techniques for finding optimal solutions. These techniques
- take as input only an LP in the above Standard Form, and determine a
- solution without reference to any information concerning the LP's origins or
- special structure. They are fast and reliable over a substantial range of
- problem sizes and applications.
-
- Two families of solution techniques are in wide use today. Both visit a
- progressively improving series of trial solutions, until a solution is
- reached that satisfies the conditions for an optimum. Simplex methods,
- introduced by Dantzig about 50 years ago, visit "basic" solutions computed
- by fixing enough of the variables at their bounds to reduce the constraints
- Ax = b to a square system, which can be solved for unique values of the
- remaining variables. Basic solutions represent extreme boundary points of
- the feasible region defined by Ax = b, x >= 0, and the simplex method can be
- viewed as moving from one such point to another along the edges of the
- boundary. Barrier or interior-point methods, by contrast, visit points
- within the interior of the feasible region. These methods derive from
- techniques for nonlinear programming that were developed and popularized in
- the 1960s by Fiacco and McCormick, but their application to linear
- programming dates back only to Karmarkar's innovative analysis in 1984.
-
- The related problem of integer programming (or integer linear programming,
- strictly speaking) requires some or all of the variables to take integer
- (whole number) values. Integer programs (IPs) often have the advantage of
- being more realistic than LPs, but the disadvantage of being much harder to
- solve. The most widely used general-purpose techniques for solving IPs use
- the solutions to a series of LPs to manage the search for integer solutions
- and to prove optimality. Thus most IP software is built upon LP software,
- and this FAQ applies to problems of both kinds.
-
- Linear and integer programming have proved valuable for modeling many and
- diverse types of problems in planning, routing, scheduling, assignment, and
- design. Industries that make use of LP and its extensions include
- transportation, energy, telecommunications, and manufacturing of many kinds.
- A sampling of applications can be found in many LP textbooks, in books on LP
- software systems, and among the application cases in the journal Interfaces.
-
- [ ]
-
- Q2. "Where is there good software to solve LP problems?"
-
- A: Thanks to the advances in computing of the past decade, linear programs
- in a few thousand variables and constraints are nowadays viewed as "small".
- Problems having tens or hundreds of thousands of continuous variables are
- regularly solved; tractable integer programs are necessarily smaller, but
- are still commonly in the hundreds or thousands of variables and
- constraints. The computers of choice for linear and integer programming
- applications are Pentium-based PCs and the several varieties of Unix
- workstations.
-
- There is more to linear programming than optimal solutions and
- number-crunching, however. This can be appreciated by observing that modern
- LP software comes in two related but very different kinds of packages:
-
- * Algorithmic codes are devoted to finding optimal solutions to specific
- linear programs. A code takes as input a compact listing of the LP
- constraint coefficients (the A, b, c and related values in the standard
- form) and produces as output a similarly compact listing of optimal
- solution values and related information.
-
- * Modeling systems are designed to help people formulate LPs and analyze
- their solutions. An LP modeling system takes as input a description of
- a linear program in a form that people find reasonably natural and
- convenient, and allows the solution output to be viewed in similar
- terms; conversion to the forms requried by algorithmic codes is done
- automatically. The collection of statement forms for the input is often
- called a modeling language.
-
- Most modeling systems support a variety of algorithmic codes, while the more
- popular codes can be used with many different modeling systems. Because
- packages of the two kinds are often bundled for convenience of marketing or
- operation, the distinction between them is sometimes obscured, but it is
- important to keep in mind when attempting to sort through the many
- alternatives available.
-
- Large-scale LP algorithmic codes rely on general-structure sparse matrix
- techniques and numerous other refinements developed through years of
- experience. The fastest and most reliable codes thus represent considerable
- development effort, and tend to be expensive except in very limited
- demonstration or "student" versions. Those codes that are free -- to all, or
- at least for research and teaching -- tend to be somewhat less robust,
- though they are still useful for many problems. The ability of a code to
- solve any particular class of problems cannot easily be predicted from
- problem size alone; some experimentation is usually necessary to establish
- difficulty.
-
- Large-scale LP modeling systems are commercial products virtually without
- exception, and tend to be as expensive as the commercial algorithmic codes
- (again with the exception of small demo versions). They vary so greatly in
- design and capability that a description in words is adequate only to make a
- preliminary decision among them; your ultimate choice is best guided by
- using each candidate to formulate a model of interest.
-
- Listed below are summary descriptions of available free codes, and a
- tabulation of many commercial codes and modeling systems for linear (and
- integer) programming. A list of free demos of commercial software appears at
- the end of this section.
-
- Another useful source of information is the Optimization Software Guide by
- Jorge More' and Stephen Wright, available from SIAM Books. It contains
- references to about 75 available software packages (not all of them just
- LP), and goes into more detail than is possible in this FAQ; see in
- particular the sections on "linear programming" and on "modeling languages
- and optimization systems." An updated Web version of this book is available
- on the NEOS Guide. Another good soruce of feature summaries and contact
- information is the Linear Programming Software Survey compiled by OR/MS
- Today (which also has the largest selection of advertisements for
- optimization software). Much information can also be obtained through the
- web sites of optimization software developers, many of which are identified
- in the writeup and tables below.
-
- To provide some idea of the relative performance of LP codes, a Web page of
- pointers to benchmarks for optimization software is being compiled by Hans
- Mittelmann of Arizona State University. It currently includes tests of
- several public-domain simplex and interior-point implementations. When
- evaluating any performance comparison, however, whether performed by a
- customer, vendor, or disinterested third party, keep in mind that all
- high-quality codes provide options that offer superior performance on
- certain difficult kinds of LP or IP problems. Benchmark studies of the
- "default settings" of codes will fail to reflect the power of the optional
- settings that are available.
-
- "Free" codes
-
- Some of these programs require registration or payment for some (especially
- commercial) uses. Conditions of use are also subject to change. It is a good
- practice to check a code's "readme" file or introductory documentation for
- restrictions before committing to use it.
-
- Based on the simplex method:
-
- There is an ftp-able code, written in C, called lp_solve that its author
- (Michel Berkelaar, email at 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 reasonable first try.
-
- LP-Optimizer is a simplex-based code for linear and integer programs,
- written by Markus Weidenauer (nc-weidenma@netcologne.de). Free Borland
- Pascal 7.0 source is available for downloading, as are executables for DOS
- and OS/2.
-
- SoPlex is an object-oriented implementation of the primal and dual simplex
- algorithms, developed by Roland Wunderling. Source code is available free
- for research uses at noncommercial and academic institutions.
-
- Among the SLATEC library routines is a Fortran sparse implementation of the
- simplex method, SPLP, at 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 interior-point methods:
-
- The Optimization Technology Center at Argonne and Northwestern has developed
- the interior-point code PCx. This code can be downloaded directly from the
- PCx home page; it is freely available, except that you must contact Argonne
- if you want to include it in a product for resale. A Windows 95/NT version
- of PCx was announced in April 1997, and is available under the same
- conditions as the original. (If you want to solve an LP without downloading
- a code to your own machine, you can execute PCx remotely through the NEOS
- Server.)
-
- A Fortran 77 interior-point 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://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.bell-labs.com/netlib/opt/hopdm.shar.Z
-
- Other software of interest:
-
- ABACUS is a C++ class library that "provides a framework for the
- implementation of branch-and-bound algorithms using linear programming
- relaxations that can be complemented with the dynamic generation of cutting
- planes or columns" (branch-and-cut and/or branch-and-price). It relies on
- CPLEX or SoPlex to solver linear programs. Further information is available
- from Stefan Thienel, thienel@informatik.uni-koeln.de.
-
- A web-based service by a group at Berkeley called Interactive Linear
- Programming appears to be useful for solving small models that can be
- entered by hand. Along similar lines, the NEOS Guide offers a Java-based
- Simplex Tool, which demonstrates the workings of the simplex method on small
- user-entered problems and is especially useful for educational purposes.
- Anima-LP by Chris Jones (cvj@u.washington.edu) graphs and solves
- two-dimensional linear programs interactively on any Java-compatible
- browser; there is also a Macintosh version.
-
- The Systems Analysis Laboratory at Seoul National University offers Linear
- Programming software (both Simplex and Barrier) at
- 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 anti-cycling 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 public-domain codes that are severely
- limited by the algorithm they use (tableau Simplex); they may be OK for
- models with (on the order of) 100 variables and constraints, but it's
- unlikely they will be satisfactory for larger models. In the words of Matt
- Saltzman (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 ill-conditioned or degenerate can bring
- most of these tableau codes to their knees. Other disadvantages for
- larger problems relate to sparsity, pricing, and maintaining the
- complete nonbasic portion of the tableau. But for small, dense problems
- these difficulties may not be serious enough to prevent tableau codes
- from being useful, or even preferable to more "sophisticated" sparse
- codes. In any event, use them with care.
-
- * For DOS/PC users, there is an LP and Linear Goal Programming binary
- called tslin, at ftp://garbo.uwasa.fi/pc/ts (the current file name is
- tslin34.zip, using ZIP compression), or else I suggest contacting Prof.
- Salmi at ts@uwasa.fi . For North American users, the garbo server is
- mirrored on FTP site wuarchive.wustl.edu, in directory
- mirrors/garbo.uwasa.fi.
- * 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 2-dimensional
- array for the A-matrix; if so, it is surely using the tableau Simplex
- Method rather than sparse methods, and Saltzman's comments will apply.
-
- For Macintosh users there is a free package called LinPro that is available
- at 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 R-Tek 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 0-931988-06-3). However, I revised it
- considerably when I converted it to Pascal. I then added Sensitivity
- Analysis based on the book "The Operations Research Problem Solver"
- (ISBN 0-87891-548-6). I have tested the program on over 30 textbook
- problems, but never used it for real life applications. If someone
- finds a problem with the program, I would be pleased to correct it. I
- would also appreciate knowing how the program was used.
-
- The following suggestions may represent low-cost ways of solving LPs if you
- already have certain software available to you.
-
- * All of the most popular spreadsheet programs offer an LP solver as a
- feature or add-in.
- * A package called QSB (Quantitative Systems for Business, from
- Prentice-Hall publishers) has an LP module among its routines.
- * If you have access to a commercial math library, such as SAS
- (919-677-8000), IMSL (800-222-4675 or 713-784-3131 or
- support@houston.vni.com) or NAG (708-971-2337), you may be able to use
- an LP routine from there.
- * Mathematical systems MATLAB (The Math Works, Inc., (508) 653-1415, see
- comment in the NLP FAQ) and MAPLE (Waterloo Maple Software, 450 Phillip
- Street, Waterloo, Ontario, Canada N2L 5J2 Phone: (519) 747-2373 Fax:
- (519) 747-5284) also have LP solvers. An interface from MATLAB to
- lp_solve is available from Jeff Kantor (Jeffrey.Kantor@nd.edu) in
- ftp://control.cheg.nd.edu/pub/Kantor/matlab/lp_solve. A MATLAB toolkit
- for solving LP models using Interior-Point methods, called LIPSOL is
- available at ftp://ftp.math.umbc.edu/pub/zhang/lipsol - check the
- documentation in this directory (README.1ST) for more information; the
- current version is in subdirectory v0.3. There is an FTP site with
- user-contributed .m files to do Simplex located at
- ftp://ftp.mathworks.com/pub/contrib/optim/simplex1. There's a Usenet
- newsgroup on MATLAB: comp.soft-sys.matlab. If speed matters to you,
- then according to a Usenet posting by Pascal Koiran
- (koiran@ens-lyon.fr), on randomly generated LP models, MATLAB was an
- order of magnitude faster than MAPLE on a 200x20 problem but an order
- of magnitude slower than lp_solve on a 50x100 problem. (I don't intend
- to get into benchmarking in this document, but I mention these results
- just to explain why I choose to focus mostly on special purpose LP
- software.)
-
- Commercial codes and modeling systems
-
- If your models prove to be too difficult for free or add-on software to
- handle, then you may have to consider acquiring a commercial LP code. Dozens
- of such codes are on the market. There are many considerations in selecting
- an LP code. Speed is important, but LP is complex enough that different
- codes go faster on different models; you won't find a "Consumer Reports"
- article to say with certainty which code is THE fastest. I usually suggest
- getting benchmark results for your particular type of model if speed is
- paramount to you. Benchmarking can also help determine whether a given code
- has sufficient numerical stability for your kind of models.
-
- Other questions you should answer: Can you use a stand-alone code, or do you
- need a code that can be used as a callable library, or do you require source
- code? Do you want the flexibility of a code that runs on many platforms
- and/or operating systems, or do you want code that's tuned to your
- particular hardware architecture (in which case your hardware vendor may
- have suggestions)? Is the choice of algorithm (Simplex, Interior-Point)
- important to you? Do you need an interface to a spreadsheet code? Is the
- purchase price an overriding concern? If you are at a university, is the
- software offered at an academic discount? How much hotline support do you
- think you'll need? There is usually a large difference in LP codes, in
- performance (speed, numerical stability, adaptability to computer
- architectures) and in features, as you climb the price scale.
-
- In the following table is a condensed version of a survey of LP software
- that appeared in the June 1992 issue of OR/MS Today (a publication of
- INFORMS) and that has subsequently been updated in the October 1995 and
- April 1997 issues. Consult the full survey for more detailed information, or
- click on the product names to browse their developers' web pages.
-
- The table is in two parts, the first consisting of packages that are
- primarily algorithmic codes, and the second containing modeling systems.
- Product names are linked to product or developer web sites where known.
-
- Under "Platform" is an indication of common environments in which the code
- runs, with the choices being PC-DOS and/or versions of Microsoft Windows
- (PC), Macintosh OS (M), and Unix on various computer types (U). For other
- possibilities, check the full survey or contact the vendor.
-
- Even more so than usual, I emphasize that you must use this information at
- your own risk. I cannot guarantee that every entry is completely correct and
- up-to-date, but I will gladly correct any mistakes that are pointed out to
- me.
-
- Key to Features: S=Simplex I=Interior-Point or Barrier
- Q=Quadratic G=General-Nonlinear
- M=MIP N=Network
- V=Visualization
-
- Solver
- Product Features Platform Phone E-mail address
- CPLEX SIMNQ PC M U 702-831-7744 info@cplex.com
- C-WHIZ SM PC U 703-412-3201 ketronms@erols.com
- FortMP SIMQ PC U 630-971-2337 naginfo@nag.com
- +44 hossein@unicom.co.uk
- 1895-256484
-
- HI-PLEX S PC U +44 i.maros@ic.ac.uk
- 171-594-8334
- HS/LP SM PC 201-627-1424 info@haverly.com
- ILOG
- Planner M PC U 415-390-9000 info@ilog.com
-
- LAMPS SM PC U +44 info@amsoft.demon.co.uk
- 181-870-8882
- LINDO SMQ PC 312-988-7422 info@lindo.com
- LOQO GI PC U 609-258-0876 rvdb@princeton.edu
- LPS-867 SM PC U 609-737-6800 info@main.aae.com
- LS-XLSOL SM PC 702-831-0300 info@frontsys.com
- MINOS SQG PC 415-962-8719 sales@sbsi-sol-optimize.com
- MINTO M U 404-894-6287 martin.savelsbergh@isye.gatech.edu
- MPSIII SMN PC U 703-412-3201 ketronms@erols.com
- OSL SIMNQ PC U 914-433-4740 osl@vnet.ibm.com
- SAS/OR SMNGQ PC M U 919-677-8000 saseph@unx.sas.com
-
- SCICONIC SM PC U +44 msukwt03.gztltm@eds.com
- 1908-284188
- SOPT SIMGQ PC U 732-264-4700 saitech@monmouth.com
- +81
- 3-3530-2644
- XA SM PC M U 818-441-1565 sunsetsw@ix.netcom.com
- XPRESS-MP SIMQ PC M 202-887-0296 info@dash.co.uk
- +44
- 1604-858993
-
- Modeling
- Product Platform Phone E-mail address
- AIMMS PC +31 23-5350935 info@paragon.nl
- AMPL PC U 702-322-7600 info@ampl.com
- ANALYZE PC 303-796-7830 hgreenbe@carbon.cudenver.edu
- DecisionPRO PC 919-859-4101 vginfo@vanguardsw.com
- DATAFORM PC U 703-412-3201 ketronms@erols.com
- GAMS PC U 202-342-0180 sales@gams.com
- LINGO PC U 800-441-2378 info@lindo.com
- MathPro PC U 202-887-0296 mathpro@erols.com
- MIMI PC U 908-464-8300 info@chesapeake.com
- MODLER PC U 303-796-7830 hgreenbe@carbon.cudenver.edu
- MPL PC 703-522-7900 info@maximal-usa.com
- OMNI PC U 201-627-1424 info@haverly.com
- VMP PC U 301-622-4319 j-welch@sundown-vmp.com
- What's Best! PC M U 800-441-2378 info@lindo.com
- Visual XPRESS PC 202-887-0296 info@dash.co.uk
- +44 1604-858993
-
- Free demos of commercial codes
-
- An increasing number of commercial LP software developers are making demo or
- academic versions available for downloading through web sites or as add-ons
- to book packages. Typically these versions are limited in the size of
- problem they accept or the length of time that they will operate, or are
- made available only for "academic use" (mainly research or teaching at
- universities). Nevertheless, they have most or all of the features of the
- full versions. Most run under several variations of Microsoft Windows on
- PCs, and/or certain Unix workstations; check the relevant web pages for
- details.
-
- Downloadable free demos include:
-
- * AIMMS with XA and CONOPT
- * ANALYZE, MODLER and RANDMOD
- * LINDO and What's Best!
- * LOQO with a built-in AMPL interface
- * MPL with CPLEX
- * Visual XPRESS with XPRESS-MP
-
- Books that are packaged with demo software include:
-
- * A. Brooke, D. Kendrick and A. Meeraus, GAMS: A Users' Guide, Wadsworth
- Publishing Co/Duxbury Press, ISBN 0-894-26215-7.
- * R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Language for
- Mathematical Programming, Wadsworth Publishing Co/Duxbury Press, ISBN
- 0-534-50983-5.
- * H.J. Greenberg, Modeling by Object-Driven Linear Elemental Relations: A
- User's Guide for MODLER, Kluwer Academic Publishers, ISBN
- 0-792-39323-6.
- * L. Schrage, Optimization Modeling with LINDO, LINDO Systems, order
- directly from developer.
-
- Many developers are also willing to arrange for you to "borrow" copies of
- their full-featured versions for purposes of evaluation. Details vary,
- 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. Zero-one (or 0-1 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 zero-one 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 "NP-complete" problems, all of which are very hard
- to solve (at least as far as anyone has been able to tell). Since any
- NP-complete 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 general-purpose large-scale MIP
- codes use a procedure called "branch-and-bound" 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 branch-and-bound 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 zero-one 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 high-quality 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 0-1 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 best-known and most widely
- used models of this kind are the so-called 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
- general-purpose 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 42-51. 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 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 also available via anonymous ftp at
-
- ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp/opbdp.tar.Z
-
- along with a Postscript-format 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
- 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 Lucent Technologies (kat3@ihgp-ebb.ih.lucent.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.
-
- [ ]
-
- 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 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/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.
-
- 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 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. Topics briefly covered:
-
- Q6.1: "What is a modeling language?"
-
- A: There is more to linear programming (or integer programming) than optimal
- solutions and number-crunching. 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
- general-purpose 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 computer-assisted analysis, including rule-based 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 so-called 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 built-in
- features to help track infeasibilities.
-
- Q6.3: "I want to know the specific constraints that contradict each other."
-
- A: This may not be a well posed problem. If by this you mean you want to
- find the minimal set of constraints that should be removed to restore
- feasibility, this can be modeled as an Integer LP (which means, it's
- potentially a harder problem than the underlying LP itself). Start with a
- Goal Programming approach as outlined above, and introduce some 0-1
- variables to turn the slacks off or on. Then minimize on the sum of these
- 0-1 variables.
- 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
- 30602-6255.
- * 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 almost-independent matrix blocks that are
- linked by a few constraints. Can I take advantage of this?"
-
- A: Possibly. See section 6.2 in [Nemhauser] for a discussion of
- Dantzig-Wolfe decomposition. I am told that the commercial code OSL has
- features to assist in doing this. With any other code, you'll have to create
- your own framework and then call the LP solver to solve the subproblems. The
- folklore is that generally such schemes take a long time to converge so that
- they're slower than just solving the model as a whole, although research
- continues. For now my advice, unless you are using OSL or your model is so
- huge that a good solver can't fit it in memory, is to not bother decomposing
- it. It's probably more cost effective to upgrade your solver, if the
- algorithm is limiting you, than to invest your time; but I suppose that's an
- underlying theme in a lot of my advice. 8v)
-
- Q6.7: "I am looking for an algorithm to compute the convex hull of a finite
- number of points in n-dimensional space."
-
- A: There is a program called qhull, available at
- ftp://geom.umn.edu/pub/software/qhull.tar.Z. When you uncompress it and
- untar it, it will create a directory called qhull which has source code plus
- a README file. It uses the "Beneath Beyond" method, described in
- [Edelsbrunner].
-
- A code in C called cdd is available at ftp://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.bell-labs.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.
-
- Q6.8: "Are there any parallel LP codes?"
-
- A: The vendors for OSL, CPLEX and XPRESS-MP each have announced parallel
- implementations of Branch and Bound solvers for MIP. 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.
- 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.
-
- 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 minimum-cost 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 (one-way) or
- undirected (two-way). 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 well-known 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 least-cost 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 general-purpose 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 Java-enabled 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)
-
- * RELAX-IV for minimum-cost network flows (by Dimitri Bertsekas,
- bertsekas@lids.mit.edu and Paul Tseng, tseng@math.washington.edu); also
- a C++ version of the RELAX-IV 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, minimum-cost flow, and maximum flow/minimum cut, by
- Andrew Goldberg (avg@research.nj.nec.com).
-
- * Optimization routines for networks and graphs in the listing of
- public-domain 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 498-516. [Syslo]
- contains some algorithms and Pascal code. Numerical Recipes [Press] contains
- code that uses Simulated Annealing. [Bentley] is said to contain a
- description of how to write a TSP code. Code for a solver can be obtained
- via instructions in [Volgenant]. Bob Craig of Lucent Technologies
- (kat3@ihgp-ebb.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@ihgp-ebb.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,407-423) Also, for not
- huge discretely distributed problems, a deterministic equivalent can be
- formed which can be solved with a standard solver. STOPGEN, available via
- anonymous FTP from this author is a program which forms deterministic equiv.
- MPS files from stopro problems in standard format (Birge, et. al., COAL
- newsletter 17). The most recent program for continuously distributed data is
- BRAIN, by K. Frauendorfer (frauendorfer@sgcl1.unisg.ch, written up in detail
- in the author's monograph ``Stochastic Two-Stage Programming'', Lecture
- Notes in Economics & Math. Systems #392 (Springer-Verlag).
-
- CCP problems are not usually staged, and have a constraint of the form Pr(
- Ax <= b ) >= alpha. The solvability of CCP problems depends on the
- distribution of the data (A &/v b). I don't know of any public domain codes
- for CCP probs., but you can get an idea of how to approach the problem by
- reading Chapter 5 by Prof. A. Prekopa (prekopa@cancer.rutgers.edu) Y.
- Ermoliev, and R. J-B. Wets, eds., Numerical Techniques for Stochastic
- Optimization (Series in Comp. Math. 10, Springer-Verlag, 1988).
-
- Both Springer Verlag texts mentioned above are good introductory references
- to Stochastic Programming. This list of codes is far from comprehensive, but
- should serve as a good starting point.
-
- Q6.13: "I need to do post-optimal analysis."
-
- A: Many commercial LP codes have features to do this. Also called Ranging or
- Sensitivity Analysis, it gives information about how the coefficients in the
- problem could change without affecting the nature of the solution. Most LP
- textbooks, such as [Nemhauser], describe this. Unfortunately, all this
- theory applies only to LP.
-
- For a MIP model with both integer and continuous variables, you could get a
- limited amount of information by fixing the integer variables at their
- optimal values, re-solving the model as an LP, and doing standard
- post-optimal analyses on the remaining continuous variables; but this tells
- you nothing about the integer variables, which presumably are the ones of
- interest. Another MIP approach would be to choose the coefficients of your
- model that are of the most interest, and generate "scenarios" using values
- within a stated range created by a random number generator. Perhaps five or
- ten scenarios would be sufficient; you would solve each of them, and by some
- means compare, contrast, or average the answers that are obtained. Noting
- patterns in the solutions, for instance, may give you an idea of what
- solutions might be most stable. A third approach would be to consider a
- goal-programming formulation; perhaps your desire to see post-optimal
- analysis is an indication that some important aspect is missing from your
- model.
-
- Q6.14: "Do LP codes require a starting vertex?"
-
- A: No. You just have to give an LP code the constraints and the objective
- function, and it will construct the vertices for you. Most codes go through
- a so-called two phase method, wherein the code first looks for a feasible
- solution, and then works on getting an optimal solution. The first phase can
- begin anywhere, such as with all the variables at zero (though commercial
- codes typically have a so-called "crash" algorithm to pick a better starting
- point). So, no, you don't have to give a code a starting point. On the other
- hand, it is not uncommon to do so, because it can speed up the solution time
- tremendously. Commercial codes usually allow you to do this (they call it a
- "basis", though that's a loose usage of a specific linear algebra concept);
- free codes generally don't. You'd normally want to bother with a starting
- basis only when solving families of related and difficult LP's (i.e., in
- some sort of production mode).
-
- 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 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].
-
- General reference
-
- * Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989.
- (Very broad-reaching, with large bibliography. Good reference; it's the
- place I tend to look first. Expensive, and tough reading for
- beginners.)
- * Harvey Greenberg has compiled an on-line Mathematical Programming
- Glossary.
-
- Books containing source code
-
- * Best and Ritter, Linear Programming: active set analysis and computer
- programs, Prentice-Hall, 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, Prentice-Hall (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 1-886529-19-1).
- Graduate-level 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, multi-objective and
- heuristic techniques.
- * Luenberger, Introduction to Linear and Nonlinear Programming, Addison
- Wesley, 1984. Updated version of an old standby.
- * Murtagh, B., Advanced Linear Programming, McGraw-Hill, 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, McGraw-Hill,
- 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 0-7923-9804-1). Balanced
- coverage of simplex and interior-point methods. Source code available
- on-line 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.
-
- Interior-Point LP methods (descendants of "Karmarkar's algorithm")
-
- * Arbel, Ami, Exploring Interior-Point Linear Programming, MIT Press,
- 1993. Includes small-scale 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. 1-14. 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., Primal-Dual Interior-Point Methods. SIAM
- Publications, 1997. Covers theoretical, practical and computational
- aspects of the most important and useful class of interior-point
- algorithms. The web page for this book contains current information on
- interior-point 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 Object-Driven 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 0-19-853856-1). Each chapter is a
- self-contained 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, Prentice-Hall.
- * Gill, Murray and Wright, Numerical Linear Algebra and Optimization,
- Addison-Wesley, 1991.
- * Greenberg, H.J., A Computer-Assisted 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, Springer-Verlag, 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, Springer-Verlag 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), 295--313.
- * Balas, E. and Martin, C., "Pivot And Complement: A Heuristic For 0-1
- Programming Problems", Management Science, 1980, Vol 26, pp 86-96.
- * Balinski, M.L., "An Algorithm for Finding all Vertices of Convex
- Polyhedral Sets", SIAM J. 9, 1, 1961.
- * Carpaneto, Dell'amico & Toth, "A Branch-and-bound 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. 167-185.
- * Seidel, "Constructing Higher-Dimensional Convex Hulls at Logarithmic
- Cost per Face", 1986, 18th ACM STOC, 404--413.
- * Smale, Stephen, "On the Average Number of Steps in the Simplex Method
- of Linear Programming", Math Programming 27 (1983), 241-262.
- * Swart, "Finding the Convex Hull Facet by Facet", Journal of Algorithms,
- 6 (1985), 17--48.
- * Volgenant, A., Symmetric TSPs, European Journal of Operations Research,
- 49 (1990) 153-154.
-
- On-Line Sources of Papers and Bibliographies
-
- * Michael Trick's Operations Research Page at http://mat.gsia.cmu.edu/
- * Optimization Technology Center: home of NEOS, Network-Enabled
- Optimization System.
- * WORMS (World-Wide-Web 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/SEL-HPC/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/comb.opt.
- * Bibliography of books and papers on Interior-Point 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.uni-wuppertal.de).
- * Interior-Point Methods Online (another service of NEOS) contains most
- new reports in the area of interior-point 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 interior-point-methods-request@mcs.anl.gov containing
- the single word subscribe.
- * Information related to Semidefinite Programming is at
- ftp://orion.uwaterloo.ca/pub/henry/teaching/co769g/readme.html
- * 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://www-math.cudenver.edu/~hgreenbe/imps.html
-
- On-Line 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 Java-enabled 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 e-mail.
-
- * MILP by Dmitry V. Golovashkin. Small-scale mixed-integer programs in a
- simple algebraic format are solved through a web form interface.
-
- * Network-Enabled Optimization System (NEOS) Server. Offers access to
- about a dozen solvers for linear and nonlinear programming, network and
- stochastic linear programming, unconstrained and bound-constrained
- 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 e-mail, by submitting
- URLs through a Web page, or via a high-speed socket-based Unix
- interface. Linear and nonlinear programs in the AMPL modeling language
- can also be sent to some of the solvers, by e-mail 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.bell-labs.com although you will first need to do "cd netlib"
- before you can cd to the (dir) you are interested in. Alternatively, you can
- reach an e-mail server via "netlib@ornl.gov", to which you can send a
- message saying "send index from (dir)"; follow the instructions you receive.
- This is a list of sites mirroring the netlib repository:
-
- * Norway netlib@nac.no
- * England netlib@ukc.ac.uk
- * Germany anonymous@elib.zib-berlin.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/linear-programming-faq.html, Usenet sci.answers, anonymous FTP
- /pub/usenet/sci.answers/ linear-programming-faq 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 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.
-
- Suggestions, corrections, topics you'd like to see covered, and additional
- material are all solicited. Send email to 4er@iems.nwu.edu.
-
- [ ]
-
- END linear-programming-faq
-