home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / linear-programming-faq < prev    next >
Encoding:
Internet Message Format  |  1997-11-02  |  90.8 KB

  1. 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
  2. From: 4er@iems.nwu.edu (Robert Fourer)
  3. Newsgroups: sci.op-research,sci.answers,news.answers
  4. Subject: Linear Programming FAQ
  5. Followup-To: sci.op-research
  6. Date: 1 Nov 1997 22:55:22 GMT
  7. Organization: Northwestern University, Evanston, IL, US
  8. Lines: 1711
  9. Approved: news-answers-request@MIT.Edu
  10. Distribution: world
  11. Expires: 12/03/97
  12. Message-ID: <63gc0q$8lu@news.acns.nwu.edu>
  13. Reply-To: 4er@iems.nwu.edu (Robert Fourer)
  14. NNTP-Posting-Host: scherzo.iems.nwu.edu
  15. Summary: A List of Frequently Asked Questions about Linear Programming
  16. Keywords: FAQ, LP, Linear Programming
  17. Originator: 4er@scherzo.iems.nwu.edu
  18. Xref: senator-bedfellow.mit.edu sci.op-research:8533 sci.answers:7322 news.answers:115956
  19.  
  20. Posted-By: auto-faq 2.4
  21. Archive-name: linear-programming-faq
  22. Last-modified: November 1, 1997
  23.  
  24. [ ]
  25.  
  26.         Linear Programming
  27.         Frequently Asked Questions
  28.  
  29. Optimization Technology Center of
  30. Northwestern University and Argonne National Laboratory
  31. [ ] Posted monthly to Usenet newsgroup sci.op-research
  32.  
  33. World Wide Web version:
  34. http://www.mcs.anl.gov/home/otc/Guide/faq/linear-programming-faq.html
  35. Plain-text version:
  36. ftp://rtfm.mit.edu/pub/usenet/sci.answers/linear-programming-faq
  37.  
  38. Date of this version: November 1, 1997
  39.  
  40.    * Q1. "What is Linear Programming?"
  41.    * Q2. "Where is there good software to solve LP problems?"
  42.         o "Free" codes
  43.         o Commercial codes and modeling systems
  44.         o Free demos of commercial codes
  45.    * Q3. "Oh, and we also want to solve it as an integer program."
  46.    * Q4. "I wrote an optimization code. Where are some test models?"
  47.    * Q5. "What is MPS format?"
  48.    * Q6. Topics briefly covered:
  49.         o Q6.1: "What is a modeling language?"
  50.         o Q6.2: "How do I diagnose an infeasible LP model?"
  51.         o Q6.3: "I want to know the specific constraints that contradict
  52.           each other."
  53.         o Q6.4: "I just want to know whether or not a feasible solution
  54.           *exists*."
  55.         o Q6.5: "I have an LP, except it's got several objective functions."
  56.         o Q6.6: "I have an LP that has large almost-independent matrix
  57.           blocks that are linked by a few constraints. Can I take advantage
  58.           of this?"
  59.         o Q6.7: "I am looking for an algorithm to compute the convex hull of
  60.           a finite number of points in n-dimensional space."
  61.         o Q6.8: "Are there any parallel LP codes?"
  62.         o Q6.9: "What software is there for Network models?"
  63.         o Q6.10: "What software is there for the Traveling Salesman Problem
  64.           (TSP)?"
  65.         o Q6.11: "What software is there for the Knapsack Problem?"
  66.         o Q6.12: "What software is there for Stochastic Programming?"
  67.         o Q6.13: "I need to do post-optimal analysis."
  68.         o Q6.14: "Do LP codes require a starting vertex?"
  69.         o Q6.15: "How can I combat cycling in the Simplex algorithm?"
  70.    * Q7. "What references and Web links are there in this field?"
  71.    * Q8. "How do I access the Netlib server?"
  72.    * Q9. "Who maintains this FAQ list?"
  73.  
  74. See also the following pages
  75. pertaining to mathematical programming and optimization modeling:
  76.  
  77.    * The related Nonlinear Programming FAQ.
  78.    * The NEOS Guide to optimization models and software.
  79.    * The Decision Tree for Optimization Software by H.D. Mittelmann and P.
  80.      Spellucci.
  81.    * Jiefeng Xu's List of Interesting Optimization Codes in the Public
  82.      Domain.
  83.    * Software for Optimization: A Buyer's Guide by Robert Fourer.
  84.    * Harvey Greenberg's Mathematical Programming Glossary.
  85.  
  86. [ ]
  87.  
  88. Q1. "What is Linear Programming?"
  89.  
  90. A: (For rigorous definitions and theory, which are beyond the scope of this
  91. document, the interested reader is referred to the many LP textbooks in
  92. print, a few of which are listed in the references section.)
  93.  
  94. A Linear Program (LP) is a problem that can be expressed as follows (the
  95. so-called Standard Form):
  96.  
  97.     minimize   cx
  98.     subject to Ax  = b
  99.                 x >= 0
  100.  
  101. where x is the vector of variables to be solved for, A is a matrix of known
  102. coefficients, and c and b are vectors of known coefficients. The expression
  103. "cx" is called the objective function, and the equations "Ax=b" are called
  104. the constraints. All these entities must have consistent dimensions, of
  105. course, and you can add "transpose" symbols to taste. The matrix A is
  106. generally not square, hence you don't solve an LP by just inverting A.
  107. Usually A has more columns than rows, and Ax=b is therefore quite likely to
  108. be under-determined, leaving great latitude in the choice of x with which to
  109. minimize cx.
  110.  
  111. The word "Programming" is used here in the sense of "planning"; the
  112. necessary relationship to computer programming was incidental to the choice
  113. of name. Hence the phrase "LP program" to refer to a piece of software is
  114. not a redundancy, although I tend to use the term "code" instead of
  115. "program" to avoid the possible ambiguity.
  116.  
  117. Although all linear programs can be put into the Standard Form, in practice
  118. it may not be necessary to do so. For example, although the Standard Form
  119. requires all variables to be non-negative, most good LP software allows
  120. general bounds l <= x <= u, where l and u are vectors of known lower and
  121. upper bounds. Individual elements of these bounds vectors can even be
  122. infinity and/or minus-infinity. This allows a variable to be without an
  123. explicit upper or lower bound, although of course the constraints in the
  124. A-matrix will need to put implied limits on the variable or else the problem
  125. may have no finite solution. Similarly, good software allows b1 <= Ax <= b2
  126. for arbitrary b1, b2; the user need not hide inequality constraints by the
  127. inclusion of explicit "slack" variables, nor write Ax >= b1 and Ax <= b2 as
  128. two separate constraints. Also, LP software can handle maximization problems
  129. just as easily as minimization (in effect, the vector c is just multiplied
  130. by -1).
  131.  
  132. The importance of linear programming derives in part from its many
  133. applications (see further below) and in part from the existence of good
  134. general-purpose techniques for finding optimal solutions. These techniques
  135. take as input only an LP in the above Standard Form, and determine a
  136. solution without reference to any information concerning the LP's origins or
  137. special structure. They are fast and reliable over a substantial range of
  138. problem sizes and applications.
  139.  
  140. Two families of solution techniques are in wide use today. Both visit a
  141. progressively improving series of trial solutions, until a solution is
  142. reached that satisfies the conditions for an optimum. Simplex methods,
  143. introduced by Dantzig about 50 years ago, visit "basic" solutions computed
  144. by fixing enough of the variables at their bounds to reduce the constraints
  145. Ax = b to a square system, which can be solved for unique values of the
  146. remaining variables. Basic solutions represent extreme boundary points of
  147. the feasible region defined by Ax = b, x >= 0, and the simplex method can be
  148. viewed as moving from one such point to another along the edges of the
  149. boundary. Barrier or interior-point methods, by contrast, visit points
  150. within the interior of the feasible region. These methods derive from
  151. techniques for nonlinear programming that were developed and popularized in
  152. the 1960s by Fiacco and McCormick, but their application to linear
  153. programming dates back only to Karmarkar's innovative analysis in 1984.
  154.  
  155. The related problem of integer programming (or integer linear programming,
  156. strictly speaking) requires some or all of the variables to take integer
  157. (whole number) values. Integer programs (IPs) often have the advantage of
  158. being more realistic than LPs, but the disadvantage of being much harder to
  159. solve. The most widely used general-purpose techniques for solving IPs use
  160. the solutions to a series of LPs to manage the search for integer solutions
  161. and to prove optimality. Thus most IP software is built upon LP software,
  162. and this FAQ applies to problems of both kinds.
  163.  
  164. Linear and integer programming have proved valuable for modeling many and
  165. diverse types of problems in planning, routing, scheduling, assignment, and
  166. design. Industries that make use of LP and its extensions include
  167. transportation, energy, telecommunications, and manufacturing of many kinds.
  168. A sampling of applications can be found in many LP textbooks, in books on LP
  169. software systems, and among the application cases in the journal Interfaces.
  170.  
  171. [ ]
  172.  
  173. Q2. "Where is there good software to solve LP problems?"
  174.  
  175. A: Thanks to the advances in computing of the past decade, linear programs
  176. in a few thousand variables and constraints are nowadays viewed as "small".
  177. Problems having tens or hundreds of thousands of continuous variables are
  178. regularly solved; tractable integer programs are necessarily smaller, but
  179. are still commonly in the hundreds or thousands of variables and
  180. constraints. The computers of choice for linear and integer programming
  181. applications are Pentium-based PCs and the several varieties of Unix
  182. workstations.
  183.  
  184. There is more to linear programming than optimal solutions and
  185. number-crunching, however. This can be appreciated by observing that modern
  186. LP software comes in two related but very different kinds of packages:
  187.  
  188.    * Algorithmic codes are devoted to finding optimal solutions to specific
  189.      linear programs. A code takes as input a compact listing of the LP
  190.      constraint coefficients (the A, b, c and related values in the standard
  191.      form) and produces as output a similarly compact listing of optimal
  192.      solution values and related information.
  193.  
  194.    * Modeling systems are designed to help people formulate LPs and analyze
  195.      their solutions. An LP modeling system takes as input a description of
  196.      a linear program in a form that people find reasonably natural and
  197.      convenient, and allows the solution output to be viewed in similar
  198.      terms; conversion to the forms requried by algorithmic codes is done
  199.      automatically. The collection of statement forms for the input is often
  200.      called a modeling language.
  201.  
  202. Most modeling systems support a variety of algorithmic codes, while the more
  203. popular codes can be used with many different modeling systems. Because
  204. packages of the two kinds are often bundled for convenience of marketing or
  205. operation, the distinction between them is sometimes obscured, but it is
  206. important to keep in mind when attempting to sort through the many
  207. alternatives available.
  208.  
  209. Large-scale LP algorithmic codes rely on general-structure sparse matrix
  210. techniques and numerous other refinements developed through years of
  211. experience. The fastest and most reliable codes thus represent considerable
  212. development effort, and tend to be expensive except in very limited
  213. demonstration or "student" versions. Those codes that are free -- to all, or
  214. at least for research and teaching -- tend to be somewhat less robust,
  215. though they are still useful for many problems. The ability of a code to
  216. solve any particular class of problems cannot easily be predicted from
  217. problem size alone; some experimentation is usually necessary to establish
  218. difficulty.
  219.  
  220. Large-scale LP modeling systems are commercial products virtually without
  221. exception, and tend to be as expensive as the commercial algorithmic codes
  222. (again with the exception of small demo versions). They vary so greatly in
  223. design and capability that a description in words is adequate only to make a
  224. preliminary decision among them; your ultimate choice is best guided by
  225. using each candidate to formulate a model of interest.
  226.  
  227. Listed below are summary descriptions of available free codes, and a
  228. tabulation of many commercial codes and modeling systems for linear (and
  229. integer) programming. A list of free demos of commercial software appears at
  230. the end of this section.
  231.  
  232. Another useful source of information is the Optimization Software Guide by
  233. Jorge More' and Stephen Wright, available from SIAM Books. It contains
  234. references to about 75 available software packages (not all of them just
  235. LP), and goes into more detail than is possible in this FAQ; see in
  236. particular the sections on "linear programming" and on "modeling languages
  237. and optimization systems." An updated Web version of this book is available
  238. on the NEOS Guide. Another good soruce of feature summaries and contact
  239. information is the Linear Programming Software Survey compiled by OR/MS
  240. Today (which also has the largest selection of advertisements for
  241. optimization software). Much information can also be obtained through the
  242. web sites of optimization software developers, many of which are identified
  243. in the writeup and tables below.
  244.  
  245. To provide some idea of the relative performance of LP codes, a Web page of
  246. pointers to benchmarks for optimization software is being compiled by Hans
  247. Mittelmann of Arizona State University. It currently includes tests of
  248. several public-domain simplex and interior-point implementations. When
  249. evaluating any performance comparison, however, whether performed by a
  250. customer, vendor, or disinterested third party, keep in mind that all
  251. high-quality codes provide options that offer superior performance on
  252. certain difficult kinds of LP or IP problems. Benchmark studies of the
  253. "default settings" of codes will fail to reflect the power of the optional
  254. settings that are available.
  255.  
  256. "Free" codes
  257.  
  258. Some of these programs require registration or payment for some (especially
  259. commercial) uses. Conditions of use are also subject to change. It is a good
  260. practice to check a code's "readme" file or introductory documentation for
  261. restrictions before committing to use it.
  262.  
  263. Based on the simplex method:
  264.  
  265. There is an ftp-able code, written in C, called lp_solve that its author
  266. (Michel Berkelaar, email at michel@es.ele.tue.nl) says has solved models
  267. with up to 30,000 variables and 50,000 constraints. The author requests that
  268. people retrieve it from ftp://ftp.es.ele.tue.nl/pub/lp_solve (numerical
  269. address at last check: 131.155.20.126). There is an older version to be
  270. found in the Usenet archives, but it contains bugs that have been fixed in
  271. the meantime, and hence is unsupported. The author also made available a
  272. program that converts data files from MPS-format into lp_solve's own input
  273. format; it's in the same directory, in file mps2eq_0.2.tar.Z. The
  274. documentation states that it is not public domain, and the author wants to
  275. discuss it with would-be commercial users. As an editorial opinion, I must
  276. state that difficult models will give lp_solve trouble; it's not as good as
  277. a commercial code. But for someone who isn't sure what kind of LP code is
  278. needed, it represents a reasonable first try.
  279.  
  280. LP-Optimizer is a simplex-based code for linear and integer programs,
  281. written by Markus Weidenauer (nc-weidenma@netcologne.de). Free Borland
  282. Pascal 7.0 source is available for downloading, as are executables for DOS
  283. and OS/2.
  284.  
  285. SoPlex is an object-oriented implementation of the primal and dual simplex
  286. algorithms, developed by Roland Wunderling. Source code is available free
  287. for research uses at noncommercial and academic institutions.
  288.  
  289. Among the SLATEC library routines is a Fortran sparse implementation of the
  290. simplex method, SPLP, at ftp://netlib2.cs.utk.edu/slatec/src/splp.f. Its
  291. documentation states that it can solve LP models of "at most a few thousand
  292. constraints and variables".
  293.  
  294. Based on interior-point methods:
  295.  
  296. The Optimization Technology Center at Argonne and Northwestern has developed
  297. the interior-point code PCx. This code can be downloaded directly from the
  298. PCx home page; it is freely available, except that you must contact Argonne
  299. if you want to include it in a product for resale. A Windows 95/NT version
  300. of PCx was announced in April 1997, and is available under the same
  301. conditions as the original. (If you want to solve an LP without downloading
  302. a code to your own machine, you can execute PCx remotely through the NEOS
  303. Server.)
  304.  
  305. A Fortran 77 interior-point code, BPMPD, has been developed by Csaba
  306. Meszaros (meszaros@sztaki.hu) at the Computer and Automation Research
  307. Institute of the Hungarian Academy of Sciences. It is available as source
  308. code, as a Windows95/NT executable (which is also extended to solve convex
  309. quadratic problems), and in a DLL version for Windows.
  310.  
  311. Jacek Gondzio (gondzio@divsun.unige.ch) has made source for his interior
  312. point LP solver HOPDM available at
  313. http://ecolu-info.unige.ch/~logilab/software/hopdm.html. Additionally,
  314. several papers devoted to HOPDM code are available at this site. It uses a
  315. higher order primal-dual predictor-corrector logarithmic barrier algorithm,
  316. and according to David Gay, it "seems to work well in limited testing. For
  317. example, it happily solves all of the examples in netlib's lp/data
  318. directory." Prof. Gondzio notes that problem size is limited only by
  319. available memory, and on a virtual memory system it has been used to solve
  320. models with hundreds of thousand of constraints and variables. An older
  321. version of the source code is kept in netlib's opt directory:
  322. ftp://netlib.bell-labs.com/netlib/opt/hopdm.shar.Z
  323.  
  324. Other software of interest:
  325.  
  326. ABACUS is a C++ class library that "provides a framework for the
  327. implementation of branch-and-bound algorithms using linear programming
  328. relaxations that can be complemented with the dynamic generation of cutting
  329. planes or columns" (branch-and-cut and/or branch-and-price). It relies on
  330. CPLEX or SoPlex to solver linear programs. Further information is available
  331. from Stefan Thienel, thienel@informatik.uni-koeln.de.
  332.  
  333. A web-based service by a group at Berkeley called Interactive Linear
  334. Programming appears to be useful for solving small models that can be
  335. entered by hand. Along similar lines, the NEOS Guide offers a Java-based
  336. Simplex Tool, which demonstrates the workings of the simplex method on small
  337. user-entered problems and is especially useful for educational purposes.
  338. Anima-LP by Chris Jones (cvj@u.washington.edu) graphs and solves
  339. two-dimensional linear programs interactively on any Java-compatible
  340. browser; there is also a Macintosh version.
  341.  
  342. The Systems Analysis Laboratory at Seoul National University offers Linear
  343. Programming software (both Simplex and Barrier) at
  344. http://orly1.snu.ac.kr/Software.html
  345.  
  346. Will Naylor (naylor@mti.sgi.com) has a collection of software he calls
  347. WNLIB. Routines of interest include
  348. - simplex method for linear programming: contains anti-cycling and numerical
  349. stability hacks. No optimization for sparse matrix.
  350. - transportation problem/assignment problem routine: optimization for sparse
  351. matrix.
  352. Read the INSTALL.txt file for further information. WNLIB also contains
  353. routines pertaining to nonlinear optimization.
  354.  
  355. The next several suggestions are for public-domain codes that are severely
  356. limited by the algorithm they use (tableau Simplex); they may be OK for
  357. models with (on the order of) 100 variables and constraints, but it's
  358. unlikely they will be satisfactory for larger models. In the words of Matt
  359. Saltzman (mjs@clemson.edu):
  360.  
  361.      The main problems with these codes have to do with scaling, use of
  362.      explicit inverses and lack of reinversion, and handling of degeneracy.
  363.      Even small problems that are ill-conditioned or degenerate can bring
  364.      most of these tableau codes to their knees. Other disadvantages for
  365.      larger problems relate to sparsity, pricing, and maintaining the
  366.      complete nonbasic portion of the tableau. But for small, dense problems
  367.      these difficulties may not be serious enough to prevent tableau codes
  368.      from being useful, or even preferable to more "sophisticated" sparse
  369.      codes. In any event, use them with care.
  370.  
  371.    * For DOS/PC users, there is an LP and Linear Goal Programming binary
  372.      called tslin, at ftp://garbo.uwasa.fi/pc/ts (the current file name is
  373.      tslin34.zip, using ZIP compression), or else I suggest contacting Prof.
  374.      Salmi at ts@uwasa.fi . For North American users, the garbo server is
  375.      mirrored on FTP site wuarchive.wustl.edu, in directory
  376.      mirrors/garbo.uwasa.fi.
  377.    * Also on the garbo server is a file called lp261.zip, having a
  378.      descriptor of "Linear Programming Optimizer by ScanSoft". It consists
  379.      of PC binaries, and is evidently some sort of shareware (i.e., not
  380.      strictly public domain).
  381.    * There is an ACM TOMS routine for LP, #552, available at
  382.      ftp://netlib2.cs.utk.edu/toms/552. This routine was designed for
  383.      fitting data to linear constraints using an L1 norm, but it uses a
  384.      modification of the Simplex Method and could presumably be modified to
  385.      satisfy LP purposes.
  386.    * There are books that contain source code for the Simplex Method. See
  387.      the section on references. You should not expect such code to be
  388.      robust. In particular, you can check whether it uses a 2-dimensional
  389.      array for the A-matrix; if so, it is surely using the tableau Simplex
  390.      Method rather than sparse methods, and Saltzman's comments will apply.
  391.  
  392. For Macintosh users there is a free package called LinPro that is available
  393. at ftp://ftp.ari.net/MacSciTech/programming/. Some users have reported that
  394. it performs well, while one correspondent informs me he had trouble getting
  395. it to solve any problems at all; perhaps this code is sensitive to memory
  396. size of the machine. It comes with a "large example" of 100 variables, which
  397. gives a hint of its design limits. It seems to be slower than commercial
  398. codes, but that should not be a surprise (or a criticism of a free code).
  399. LinPro has its own input format and does not support MPS format.
  400.  
  401. Walter C. Riley (73700.776@compuserve.com) writes:
  402.  
  403.    * My shareware program, the R-Tek Scratchpad (rtksp106.zip $15), is
  404.      intended for teachers and students. It basically handles problems that
  405.      students in an Introduction to Finite Mathematics course might
  406.      encounter, including typical small textbook LP problems. Its primary
  407.      advantages are that it uses readable math notation, handles fractions,
  408.      and allows you to step through the problem to its solution. It is now
  409.      available on the net for ftp download at
  410.      ftp://ftp.coast.net/SimTel/win3/calc/ or one of its mirror sites.
  411.  
  412. Stephen F. Gale (sfgale@freenet.calgary.ab.ca) writes:
  413.  
  414.    * Available at http://www.freenet.calgary.ab.ca/~sfgale/simplex.html is a
  415.      fairly simple Simplex Solver written for Turbo Pascal 3.0. The original
  416.      algorithm is from the book "Some Common BASIC Programs" by Lon Poole
  417.      and Mary Borchers (ISBN 0-931988-06-3). However, I revised it
  418.      considerably when I converted it to Pascal. I then added Sensitivity
  419.      Analysis based on the book "The Operations Research Problem Solver"
  420.      (ISBN 0-87891-548-6). I have tested the program on over 30 textbook
  421.      problems, but never used it for real life applications. If someone
  422.      finds a problem with the program, I would be pleased to correct it. I
  423.      would also appreciate knowing how the program was used.
  424.  
  425. The following suggestions may represent low-cost ways of solving LPs if you
  426. already have certain software available to you.
  427.  
  428.    * All of the most popular spreadsheet programs offer an LP solver as a
  429.      feature or add-in.
  430.    * A package called QSB (Quantitative Systems for Business, from
  431.      Prentice-Hall publishers) has an LP module among its routines.
  432.    * If you have access to a commercial math library, such as SAS
  433.      (919-677-8000), IMSL (800-222-4675 or 713-784-3131 or
  434.      support@houston.vni.com) or NAG (708-971-2337), you may be able to use
  435.      an LP routine from there.
  436.    * Mathematical systems MATLAB (The Math Works, Inc., (508) 653-1415, see
  437.      comment in the NLP FAQ) and MAPLE (Waterloo Maple Software, 450 Phillip
  438.      Street, Waterloo, Ontario, Canada N2L 5J2 Phone: (519) 747-2373 Fax:
  439.      (519) 747-5284) also have LP solvers. An interface from MATLAB to
  440.      lp_solve is available from Jeff Kantor (Jeffrey.Kantor@nd.edu) in
  441.      ftp://control.cheg.nd.edu/pub/Kantor/matlab/lp_solve. A MATLAB toolkit
  442.      for solving LP models using Interior-Point methods, called LIPSOL is
  443.      available at ftp://ftp.math.umbc.edu/pub/zhang/lipsol - check the
  444.      documentation in this directory (README.1ST) for more information; the
  445.      current version is in subdirectory v0.3. There is an FTP site with
  446.      user-contributed .m files to do Simplex located at
  447.      ftp://ftp.mathworks.com/pub/contrib/optim/simplex1. There's a Usenet
  448.      newsgroup on MATLAB: comp.soft-sys.matlab. If speed matters to you,
  449.      then according to a Usenet posting by Pascal Koiran
  450.      (koiran@ens-lyon.fr), on randomly generated LP models, MATLAB was an
  451.      order of magnitude faster than MAPLE on a 200x20 problem but an order
  452.      of magnitude slower than lp_solve on a 50x100 problem. (I don't intend
  453.      to get into benchmarking in this document, but I mention these results
  454.      just to explain why I choose to focus mostly on special purpose LP
  455.      software.)
  456.  
  457. Commercial codes and modeling systems
  458.  
  459. If your models prove to be too difficult for free or add-on software to
  460. handle, then you may have to consider acquiring a commercial LP code. Dozens
  461. of such codes are on the market. There are many considerations in selecting
  462. an LP code. Speed is important, but LP is complex enough that different
  463. codes go faster on different models; you won't find a "Consumer Reports"
  464. article to say with certainty which code is THE fastest. I usually suggest
  465. getting benchmark results for your particular type of model if speed is
  466. paramount to you. Benchmarking can also help determine whether a given code
  467. has sufficient numerical stability for your kind of models.
  468.  
  469. Other questions you should answer: Can you use a stand-alone code, or do you
  470. need a code that can be used as a callable library, or do you require source
  471. code? Do you want the flexibility of a code that runs on many platforms
  472. and/or operating systems, or do you want code that's tuned to your
  473. particular hardware architecture (in which case your hardware vendor may
  474. have suggestions)? Is the choice of algorithm (Simplex, Interior-Point)
  475. important to you? Do you need an interface to a spreadsheet code? Is the
  476. purchase price an overriding concern? If you are at a university, is the
  477. software offered at an academic discount? How much hotline support do you
  478. think you'll need? There is usually a large difference in LP codes, in
  479. performance (speed, numerical stability, adaptability to computer
  480. architectures) and in features, as you climb the price scale.
  481.  
  482. In the following table is a condensed version of a survey of LP software
  483. that appeared in the June 1992 issue of OR/MS Today (a publication of
  484. INFORMS) and that has subsequently been updated in the October 1995 and
  485. April 1997 issues. Consult the full survey for more detailed information, or
  486. click on the product names to browse their developers' web pages.
  487.  
  488. The table is in two parts, the first consisting of packages that are
  489. primarily algorithmic codes, and the second containing modeling systems.
  490. Product names are linked to product or developer web sites where known.
  491.  
  492. Under "Platform" is an indication of common environments in which the code
  493. runs, with the choices being PC-DOS and/or versions of Microsoft Windows
  494. (PC), Macintosh OS (M), and Unix on various computer types (U). For other
  495. possibilities, check the full survey or contact the vendor.
  496.  
  497. Even more so than usual, I emphasize that you must use this information at
  498. your own risk. I cannot guarantee that every entry is completely correct and
  499. up-to-date, but I will gladly correct any mistakes that are pointed out to
  500. me.
  501.  
  502. Key to Features:  S=Simplex    I=Interior-Point or Barrier
  503.                   Q=Quadratic  G=General-Nonlinear
  504.                   M=MIP        N=Network
  505.                                V=Visualization
  506.  
  507. Solver
  508. Product   Features Platform      Phone   E-mail address
  509. CPLEX     SIMNQ    PC M U  702-831-7744  info@cplex.com
  510. C-WHIZ    SM       PC U    703-412-3201  ketronms@erols.com
  511. FortMP    SIMQ     PC U    630-971-2337  naginfo@nag.com
  512.                                      +44 hossein@unicom.co.uk
  513.                             1895-256484
  514.  
  515. HI-PLEX   S        PC U              +44 i.maros@ic.ac.uk
  516.                            171-594-8334
  517. HS/LP     SM       PC      201-627-1424  info@haverly.com
  518. ILOG
  519. Planner   M        PC U    415-390-9000  info@ilog.com
  520.  
  521. LAMPS     SM       PC U              +44 info@amsoft.demon.co.uk
  522.                            181-870-8882
  523. LINDO     SMQ      PC      312-988-7422  info@lindo.com
  524. LOQO      GI       PC U    609-258-0876  rvdb@princeton.edu
  525. LPS-867   SM       PC U    609-737-6800  info@main.aae.com
  526. LS-XLSOL  SM       PC      702-831-0300  info@frontsys.com
  527. MINOS     SQG      PC      415-962-8719  sales@sbsi-sol-optimize.com
  528. MINTO     M        U       404-894-6287  martin.savelsbergh@isye.gatech.edu
  529. MPSIII    SMN      PC U    703-412-3201  ketronms@erols.com
  530. OSL       SIMNQ    PC U    914-433-4740  osl@vnet.ibm.com
  531. SAS/OR    SMNGQ    PC M U  919-677-8000  saseph@unx.sas.com
  532.  
  533. SCICONIC  SM       PC U              +44 msukwt03.gztltm@eds.com
  534.                             1908-284188
  535. SOPT      SIMGQ    PC U    732-264-4700  saitech@monmouth.com
  536.                                      +81
  537.                             3-3530-2644
  538. XA        SM       PC M U  818-441-1565  sunsetsw@ix.netcom.com
  539. XPRESS-MP SIMQ     PC M    202-887-0296  info@dash.co.uk
  540.                                      +44
  541.                             1604-858993
  542.  
  543. Modeling
  544. Product        Platform          Phone   E-mail address
  545. AIMMS          PC        +31 23-5350935  info@paragon.nl
  546. AMPL           PC U        702-322-7600  info@ampl.com
  547. ANALYZE        PC          303-796-7830  hgreenbe@carbon.cudenver.edu
  548. DecisionPRO    PC          919-859-4101  vginfo@vanguardsw.com
  549. DATAFORM       PC U        703-412-3201  ketronms@erols.com
  550. GAMS           PC U        202-342-0180  sales@gams.com
  551. LINGO          PC U        800-441-2378  info@lindo.com
  552. MathPro        PC U        202-887-0296  mathpro@erols.com
  553. MIMI           PC U        908-464-8300  info@chesapeake.com
  554. MODLER         PC U        303-796-7830  hgreenbe@carbon.cudenver.edu
  555. MPL            PC          703-522-7900  info@maximal-usa.com
  556. OMNI           PC U        201-627-1424  info@haverly.com
  557. VMP            PC U        301-622-4319  j-welch@sundown-vmp.com
  558. What's Best!   PC M U      800-441-2378  info@lindo.com
  559. Visual XPRESS  PC          202-887-0296  info@dash.co.uk
  560.                         +44 1604-858993
  561.  
  562. Free demos of commercial codes
  563.  
  564. An increasing number of commercial LP software developers are making demo or
  565. academic versions available for downloading through web sites or as add-ons
  566. to book packages. Typically these versions are limited in the size of
  567. problem they accept or the length of time that they will operate, or are
  568. made available only for "academic use" (mainly research or teaching at
  569. universities). Nevertheless, they have most or all of the features of the
  570. full versions. Most run under several variations of Microsoft Windows on
  571. PCs, and/or certain Unix workstations; check the relevant web pages for
  572. details.
  573.  
  574. Downloadable free demos include:
  575.  
  576.    * AIMMS with XA and CONOPT
  577.    * ANALYZE, MODLER and RANDMOD
  578.    * LINDO and What's Best!
  579.    * LOQO with a built-in AMPL interface
  580.    * MPL with CPLEX
  581.    * Visual XPRESS with XPRESS-MP
  582.  
  583. Books that are packaged with demo software include:
  584.  
  585.    * A. Brooke, D. Kendrick and A. Meeraus, GAMS: A Users' Guide, Wadsworth
  586.      Publishing Co/Duxbury Press, ISBN 0-894-26215-7.
  587.    * R. Fourer, D.M. Gay and B.W. Kernighan, AMPL: A Modeling Language for
  588.      Mathematical Programming, Wadsworth Publishing Co/Duxbury Press, ISBN
  589.      0-534-50983-5.
  590.    * H.J. Greenberg, Modeling by Object-Driven Linear Elemental Relations: A
  591.      User's Guide for MODLER, Kluwer Academic Publishers, ISBN
  592.      0-792-39323-6.
  593.    * L. Schrage, Optimization Modeling with LINDO, LINDO Systems, order
  594.      directly from developer.
  595.  
  596. Many developers are also willing to arrange for you to "borrow" copies of
  597. their full-featured versions for purposes of evaluation. Details vary,
  598. however, so you'll have to check with each vendor whose product you're
  599. interested in.
  600.  
  601. [ ]
  602.  
  603. Q3. "Oh, and we also want to solve it as an integer program."
  604.  
  605. A: Integer LP models are ones whose variables are constrained to take
  606. integer or whole number (as opposed to fractional) values. It may not be
  607. obvious that integer programming is a very much harder problem than ordinary
  608. linear programming, but that is nonetheless the case, in both theory and
  609. practice.
  610.  
  611. Integer models are known by a variety of names and abbreviations, according
  612. to the generality of the restrictions on their variables. Mixed integer
  613. (MILP or MIP) problems require only some of the variables to take integer
  614. values, whereas pure integer (ILP or IP) problems require all variables to
  615. be integer. Zero-one (or 0-1 or binary) MIPs or IPs restrict their integer
  616. variables to the values zero and one. (The latter are more common than you
  617. might expect, because many kinds of combinatorial and logical restrictions
  618. can be modeled through the use of zero-one variables.)
  619.  
  620. For the sake of generality, the following disucssion uses the term MIP to
  621. refer to any kind of integer LP problem; the other kinds can be viewed as
  622. special cases. MIP, in turn, is a particular member of the class of
  623. combinatorial or discrete optimization problems. In fact the problem of
  624. determining whether a MIP has an objective value less than a given target is
  625. a member of the class of "NP-complete" problems, all of which are very hard
  626. to solve (at least as far as anyone has been able to tell). Since any
  627. NP-complete problem is reducible to any other, virtually any combinatorial
  628. problem of interest can be attacked in principle by solving some equivalent
  629. MIP. This approach sometimes works well in practice, though it is by no
  630. means infallible.
  631.  
  632. People are sometimes surprised to learn that MIP problems are solved using
  633. floating point arithmetic. Most available general-purpose large-scale MIP
  634. codes use a procedure called "branch-and-bound" to search for an optimal
  635. integer solution by solving a sequence of related LP "relaxations" that
  636. allow some fractional values. Good codes for MIP distinguish themselves
  637. primarily by solving shorter sequences of LPs, and secondarily by solving
  638. the individual LPs faster. (The similarities between successive LPs in the
  639. "search tree" can be exploited to speed things up considerably.) Even more
  640. so than with regular LP, a costly commercial code may prove its value if
  641. your MIP model is difficult.
  642.  
  643. Another solution approach known generally as constraint logic programming
  644. (CLP) has drawn increasing interest of late. Having their roots in studies
  645. of logical inference in artificial intelligence, CLP codes typically do not
  646. proceed by solving any LPs. As a result, compared to branch-and-bound they
  647. search "harder" but faster through the tree of potential solutions. Their
  648. greatest advantage, however, lies in their ability to tailor the search to
  649. many constraint forms that can be converted only with difficulty to the form
  650. of an integer program; their greatest success tends to be with "highly
  651. combinatorial" optimization problems such as scheduling, sequencing, and
  652. assignment, where the construction of an equivalent IP would require the
  653. definition of large numbers of zero-one variables. More information and a
  654. list of available codes can be found in the Constraints FAQ (also posted to
  655. the newsgroup comp.constraints).
  656.  
  657. Whatever your solution technique, you should be prepared to devote far more
  658. computer time and memory to solving a MIP problem than to solving the
  659. corresponding LP relaxation. (Or equivalently, you should be prepared to
  660. solve much smaller MIP problems than LP problems using a given amount of
  661. computer resources.) To further complicate matters, the difficulty of any
  662. particular MIP problem is hard to predict (in advance, at least!). Problems
  663. in no more than a hundred variables can be challenging, while others in tens
  664. of thousands of variables solve readily. The best explanations of why a
  665. particular MIP is difficult often rely on some insight into the system you
  666. are modeling, and even then tend to appear only after a lot of computational
  667. tests have been run. A related observation is that the way you formulate
  668. your model can be as important as the actual choice of solver.
  669.  
  670. Thus a MIP problem with hundreds of variables (or more) should be approached
  671. with a certain degree of caution and patience. A willingness to experiment
  672. with alternative formulations and with a MIP code's many search options
  673. often pays off in greatly improved performance. In the hardest cases, you
  674. may wish to abandon the goal of a provable optimum; by terminating a MIP
  675. code prematurely, you can often obtain a high-quality solution along with a
  676. provable upper bound on its distance from optimality. A solution whole
  677. objective value is within some fraction of 1% of optimal may be all that is
  678. required for your purposes. (Indeed, it may be an optimal solution. In
  679. contrast to methods for ordinary LP, procedures for MIP may not be able to
  680. prove a solution to be optimal until long after they have found it.)
  681.  
  682. Once one accepts that large MIP models are not typically solved to a proved
  683. optimal solution, that opens up a broad area of approximate methods,
  684. probabilistic methods and heuristics, as well as modifications to B&B. See
  685. [Balas] which contains a useful heuristic for 0-1 MIP models. See also the
  686. brief discussion of Genetic Algorithms and Simulated Annealing in the
  687. Nonlinear Programming FAQ.
  688.  
  689. A major exception to this somewhat gloomy outlook is that there are certain
  690. models whose LP solution always turns out to be integer, assuming the input
  691. data is integer to start with. In general these models have a "unimodular"
  692. constraint matrix of some sort, but by far the best-known and most widely
  693. used models of this kind are the so-called pure network flow models. It
  694. turns out that such problems are best solved by specialized routines,
  695. usually based on the simplex method, that are much faster than any
  696. general-purpose LP methods. See the section on Network models for further
  697. information.
  698.  
  699. Commercial MIP codes are listed with the commercial LP codes and modeling
  700. systems above. The April 1994 issue of OR/MS Today contains a survey of MIP
  701. codes, which largely overlaps the content of the earlier survey on LP:
  702. "Survey: Mixed Integer Programming" by Matthew Saltzman, pp 42-51. The
  703. following are notes on some publicly available codes for MIP problems.
  704.  
  705.    * The public domain code lp_solve, mentioned earlier, accepts MIP models.
  706.  
  707.    * Peter Barth has announced opbdp, an implementation in C++ of an
  708.      implicit enumeration algorithm for solving linear 0-1 optimization
  709.      problems. The algorithm compares well with commercial linear
  710.      programming-based branch-and-bound on a variety of standard 0-1 integer
  711.      programming benchmarks. He says that exploiting the logical structure
  712.      of a problem, using opbdp, yields good performance on problems where
  713.      exploiting the polyhedral structure seems to be inefficient and vice
  714.      versa. The package is also available via anonymous ftp at
  715.  
  716.          ftp://ftp.mpi-sb.mpg.de/pub/guide/staff/barth/opbdp/opbdp.tar.Z
  717.  
  718.      along with a Postscript-format technical report (in file mpii952002.ps)
  719.      describing the techniques used.
  720.  
  721.    * I have seen mention made of algorithm 333 in the Collected Algorithms
  722.      from CACM, though I'd be surprised if it was robust enough to solve
  723.      large models. I am not aware of this algorithm being available online
  724.      anywhere.
  725.  
  726.    * In [Syslo] is code for 28 algorithms, most of which pertain to some
  727.      aspect of Discrete Optimization.
  728.  
  729.    * There is a code called Omega that analyzes systems of linear equations
  730.      in integer variables. It does not solve optimization problems, except
  731.      in the case that a model reduces completely, but its features could be
  732.      useful in analyzing and reducing MIP models. It's available at
  733.      ftp.cs.umd.edu:pub/omega (documentation is provided there), or contact
  734.      Bill Pugh at pugh@cs.umd.edu.
  735.  
  736.    * Mustafa Akgul (akgul@bilkent.edu.tr) at Bilkent University maintains an
  737.      archive in ftp://ftp.bilkent.edu.tr/pub/IEOR/Opt. There is a copy of
  738.      lp_solve (though I would recommend using the official source listed in
  739.      the previous section), and there is mip386.zip, which is a
  740.      zip-compressed code for PC's. He also has a couple of network codes and
  741.      various other codes he has picked up. All this is in the further
  742.      subdirectories LP, PC, and Network. In addition to the ftp site, there
  743.      is gopher (gopher.bilkent.edu.tr), Web (www.bilkent.edu.tr), and
  744.      archive-server@bilkent.edu.tr.
  745.  
  746.    * Bob Craig of Lucent Technologies (kat3@ihgp-ebb.ih.lucent.com) has
  747.      software written in C, which implements Balas' enumerative algorithm
  748.      for solving 0-1 ILP, that he is willing to make available to those who
  749.      request it.
  750.  
  751. [ ]
  752.  
  753. Q4. "I wrote an optimization code. Where are some test models?"
  754.  
  755. A: If you want to try out your code on some real-world LP models, there is a
  756. very nice collection of small-to-medium-size ones, with a few that are
  757. rather large, at ftp://netlib2.cs.utk.edu/lp/data, popularly known as the
  758. Netlib collection (although Netlib consists of much more than just LP).
  759. These files (after you uncompress them) are in a format called MPS, which is
  760. described in another section of this document. Note that, when you receive a
  761. model, it may be compressed both with the Unix utility (use `uncompress` if
  762. the file name ends in .Z) AND with an LP-specific program (grab either
  763. emps.f or emps.c at the same time you download the model, then compile/run
  764. the program to reverse the compression).
  765.  
  766. Also on netlib is a collection of infeasible LP models, located in
  767. ftp://netlib2.cs.utk.edu/lp/infeas.
  768.  
  769. There is a collection of MIP models, called MIPLIB, housed at Rice
  770. University in http://www.caam.rice.edu/~bixby/miplib/miplib.html. FTP users
  771. can use ftp://ftp.caam.rice.edu/pub/people/bixby/miplib. Or, send an email
  772. message containing "send catalog" to softlib@rice.edu , to get started, if
  773. you can't access the files by other means.
  774.  
  775. There's a Travelling Salesman Problem library (TSPLIB) in
  776. ftp://softlib.cs.rice.edu/pub/tsplib. (Alternate address:
  777. ftp://elib.zib-berlin.de/pub/mp-testdata/tsp.) A Web version is at
  778. http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
  779.  
  780. For network flow problems, there are some generators and instances collected
  781. at DIMACS. The NETGEN and GNETGEN generator can be downloaded from netlib.
  782. Generators and instances for multicommodity network flow problems are
  783. maintained by the Operations Research group in the Department of Computer
  784. Science at the University of Pisa.
  785.  
  786. The commercial modeling language GAMS comes with about 160 test models,
  787. which you might be able to test your code with. AIMMS also comes with some
  788. test models.
  789.  
  790. There is a collection called MP-TESTDATA available at Konrad-Zuse-Zentrum
  791. fuer Informations-technik Berlin (ZIB) in
  792. ftp://elib.zib-berlin.de/pub/mp-testdata. This directory contains various
  793. subdirectories, each of which has a file named "index" containing further
  794. information. Indexed at this writing are: assign, cluster, lp, ip, matching,
  795. maxflow, mincost, set-parti, steiner-tree, tsp, vehicle-rout, and
  796. generators.
  797.  
  798. John Beasley maintains the OR-Lib, at ftp://mscmga.ms.ic.ac.uk/pub/, which
  799. contains various optimization test problems. There is an index in
  800. ftp://mscmga.ms.ic.ac.uk/pub/info.txt. WWW access now available at
  801. http://mscmga.ms.ic.ac.uk/. Have a look in the Journal of the Operational
  802. Research Society, Volume 41, Number 11, Pages 1069-72. If you can't access
  803. these resources, send e-mail to umtsk99@vaxa.cc.imperial.ac.uk to get
  804. started. Information about test problems can be obtained by emailing
  805. o.rlibrary@ic.ac.uk with the email message being the file name for the
  806. problem areas you are interested in, or just the word "info".
  807.  
  808. [ ]
  809.  
  810. Q5. "What is MPS format?"
  811.  
  812. A: MPS format was named after an early IBM LP product and has emerged as a
  813. de facto standard ASCII medium among most of the commercial LP codes.
  814. Essentially all commercial LP codes accept this format, but if you are using
  815. public domain software and have MPS files, you may need to write your own
  816. reader routine for this. It's not too hard. See also the comment regarding
  817. the lp_solve code, in another section of this document, for the availability
  818. of an MPS reader.
  819.  
  820. The main things to know about MPS format are that it is column oriented (as
  821. opposed to entering the model as equations), and everything (variables,
  822. rows, etc.) gets a name. MPS format is described in more detail in
  823. [Murtagh]. A brief description of MPS format is available at
  824. ftp://softlib.cs.rice.edu/pub/miplib
  825.  
  826. MPS is an old format, so it is set up as though you were using punch cards,
  827. and is not free format. Fields start in column 1, 5, 15, 25, 40 and 50.
  828. Sections of an MPS file are marked by so-called header cards, which are
  829. distinguished by their starting in column 1. Although it is typical to use
  830. upper-case throughout the file (like I said, MPS has long historical roots),
  831. many MPS-readers will accept mixed-case for anything except the header
  832. cards, and some allow mixed-case anywhere. The names that you choose for the
  833. individual entities (constraints or variables) are not important to the
  834. solver; you should pick names that are meaningful to you, or will be easy
  835. for a post-processing code to read.
  836.  
  837. Here is a little sample model written in MPS format (explained in more
  838. detail below):
  839.  
  840. NAME          TESTPROB
  841. ROWS
  842.  N  COST
  843.  L  LIM1
  844.  G  LIM2
  845.  E  MYEQN
  846. COLUMNS
  847.     XONE      COST                 1   LIM1                 1
  848.     XONE      LIM2                 1
  849.     YTWO      COST                 4   LIM1                 1
  850.     YTWO      MYEQN               -1
  851.     ZTHREE    COST                 9   LIM2                 1
  852.     ZTHREE    MYEQN                1
  853. RHS
  854.     RHS1      LIM1                 5   LIM2                10
  855.     RHS1      MYEQN                7
  856. BOUNDS
  857.  UP BND1      XONE                 4
  858.  LO BND1      YTWO                -1
  859.  UP BND1      YTWO                 1
  860. ENDATA
  861.  
  862. For comparison, here is the same model written out in an equation-oriented
  863. format:
  864.  
  865. Optimize
  866.  COST:    XONE + 4 YTWO + 9 ZTHREE
  867. Subject To
  868.  LIM1:    XONE + YTWO < = 5
  869.  LIM2:    XONE + ZTHREE > = 10
  870.  MYEQN:   - YTWO + ZTHREE  = 7
  871. Bounds
  872.  0 < = XONE < = 4
  873. -1 < = YTWO < = 1
  874. End
  875.  
  876. Strangely, there is nothing in MPS format that specifies the direction of
  877. optimization. And there really is no standard "default" direction; some LP
  878. codes will maximize if you don't specify otherwise, others will minimize,
  879. and still others put safety first and have no default and require you to
  880. specify it somewhere in a control program or by a calling parameter. If you
  881. have a model formulated for minimization and the code you are using insists
  882. on maximization (or vice versa), it may be easy to convert: just multiply
  883. all the coefficients in your objective function by (-1). The optimal value
  884. of the objective function will then be the negative of the true value, but
  885. the values of the variables themselves will be correct.
  886.  
  887. The NAME card can have anything you want, starting in column 15. The ROWS
  888. section defines the names of all the constraints; entries in column 2 or 3
  889. are E for equality rows, L for less-than ( <= ) rows, G for greater-than (
  890. >= ) rows, and N for non-constraining rows (the first of which would be
  891. interpreted as the objective function). The order of the rows named in this
  892. section is unimportant.
  893.  
  894. The largest part of the file is in the COLUMNS section, which is the place
  895. where the entries of the A-matrix are put. All entries for a given column
  896. must be placed consecutively, although within a column the order of the
  897. entries (rows) is irrelevant. Rows not mentioned for a column are implied to
  898. have a coefficient of zero.
  899.  
  900. The RHS section allows one or more right-hand-side vectors to be defined;
  901. most people don't bother having more than one. In the above example, the
  902. name of the RHS vector is RHS1, and has non-zero values in all 3 of the
  903. constraint rows of the problem. Rows not mentioned in an RHS vector would be
  904. assumed to have a right-hand-side of zero.
  905.  
  906. The optional BOUNDS section lets you put lower and upper bounds on
  907. individual variables (no * wild cards, unfortunately), instead of having to
  908. define extra rows in the matrix. All the bounds that have a given name in
  909. column 5 are taken together as a set. Variables not mentioned in a given
  910. BOUNDS set are taken to be non-negative (lower bound zero, no upper bound).
  911. A bound of type UP means an upper bound is applied to the variable. A bound
  912. of type LO means a lower bound is applied. A bound type of FX ("fixed")
  913. means that the variable has upper and lower bounds equal to a single value.
  914. A bound type of FR ("free") means the variable has neither lower nor upper
  915. bounds.
  916.  
  917. There is another optional section called RANGES that I won't go into here.
  918. The final card must be ENDATA, and yes, it is spelled funny.
  919.  
  920. [ ]
  921.  
  922. Q6. Topics briefly covered:
  923.  
  924. Q6.1: "What is a modeling language?"
  925.  
  926. A: There is more to linear programming (or integer programming) than optimal
  927. solutions and number-crunching. This can be appreciated by observing that
  928. modern LP software comes in two related but very different kinds of
  929. packages:
  930.  
  931.    * Algorithmic codes are devoted to finding optimal solutions to specific
  932.      linear programs. A code takes as input a compact listing of the LP
  933.      constraint coefficients (the A, b, c and related values in the standard
  934.      form) and produces as output a similarly compact listing of optimal
  935.      solution values and related information.
  936.  
  937.    * Modeling systems are designed to help people formulate LPs and analyze
  938.      their solutions. An LP modeling system takes as input a description of
  939.      a linear program in a form that people find reasonably natural and
  940.      convenient, and allows the solution output to be viewed in similar
  941.      terms; conversion to the forms requried by algorithmic codes is done
  942.      automatically. The collection of statement forms for the input is often
  943.      called a modeling language.
  944.  
  945. Most modeling systems support a variety of algorithmic codes, while the more
  946. popular codes can be used with many different modeling systems. Because
  947. packages of the two kinds are often bundled for convenience of marketing or
  948. operation, the distinction between them is sometimes obscured, but it is
  949. important to keep in mind when sorting through the many possibilities. See
  950. under Commercial Codes and Modeling Systems elsewhere in this FAQ for a list
  951. of modeling systems available. There are no free ones of note, but many do
  952. offer free demo versions.
  953.  
  954. Common alternatives to modeling languages and systems include spreadsheet
  955. front ends to optimization, and custom optimization applications written in
  956. general-purpose programming languages. You can find a discussion of the pros
  957. and cons of these approaches in What Modeling Tool Should I Use? on the
  958. Frontline Systems web site.
  959.  
  960. Q6.2: "How do I diagnose an infeasible LP model?"
  961.  
  962. A: A linear program is infeasible if the constraints are inconsistent, i.e.,
  963. if no feasible solution can be constructed. It's often difficult to track
  964. down a cause. The cure may even be ambiguous: is it that some demand was set
  965. too high, or a supply set too low? A useful technique is goal programming
  966. (or elastic programming), one variant of which is to include two explicit
  967. slack variables (positive and negative), with huge cost coefficients, in
  968. each constraint. The revised model is guaranteed to have a feasible solution
  969. (at a possibly unbearable cost); constraints that have large slack values in
  970. the "optimal" solution are prime suspects as causes of infeasibility in the
  971. original LP. (Many modelers recommend a an elastic programming philosophy
  972. even if you aren't having trouble achieving feasibility; the idea is that
  973. almost any constraint can be violated, for a great enough price.)
  974.  
  975. Another approach is to apply auxiliary algorithms that identify constraints
  976. or groups of constraints that can be considered to "cause" the infeasibility
  977. in an LP. A software system called ANALYZE was developed by Harvey Greenberg
  978. to provide computer-assisted analysis, including rule-based intelligence; he
  979. has also compiled a bibliography of more than 400 references on the subject
  980. of model analysis. A system based on the MINOS solver, called MINOS(IIS),
  981. available from John Chinneck (chinneck@sce.carleton.ca), can also be used to
  982. identify a so-called Irreducible Infeasible Subset; the IIS feature is now
  983. available in CPLEX (command "display iis"), OSL, and LINDO (command
  984. "debug"). As a final comment, commercial codes sometimes have other built-in
  985. features to help track infeasibilities.
  986.  
  987. Q6.3: "I want to know the specific constraints that contradict each other."
  988.  
  989. A: This may not be a well posed problem. If by this you mean you want to
  990. find the minimal set of constraints that should be removed to restore
  991. feasibility, this can be modeled as an Integer LP (which means, it's
  992. potentially a harder problem than the underlying LP itself). Start with a
  993. Goal Programming approach as outlined above, and introduce some 0-1
  994. variables to turn the slacks off or on. Then minimize on the sum of these
  995. 0-1 variables.
  996. John Chinneck (chinneck@sce.carleton.ca) has modified his MINOS(IIS)
  997. extension to find the Irreducible Infeasible Subset as explained in Chinneck
  998. and Dravnieks in the Spring 1991 ORSA Journal on Computing (vol 3, number
  999. 2).
  1000.  
  1001. Q6.4: "I just want to know whether or not a feasible solution *exists*."
  1002.  
  1003. A: From the standpoint of computational complexity, finding out if an LP
  1004. model has a feasible solution is essentially as hard as actually finding the
  1005. optimal LP solution, within a factor of 2 on average, in terms of effort in
  1006. the Simplex Method; plug your problem into a normal LP solver with any
  1007. objective function you like, such as c=0. For MIP models, it's also
  1008. difficult - if there exists no feasible solution, then you must go through
  1009. the entire Branch and Bound procedure (or whatever algorithm you use) to
  1010. prove this. There are no shortcuts in general, unless you know something
  1011. useful about your model's structure (e.g., if you are solving some form of a
  1012. transportation problem, you may be able to assure feasibility by checking
  1013. that the sources add up to at least as great a number as the sum of the
  1014. destinations).
  1015.  
  1016. Q6.5: "I have an LP, except it's got several objective functions."
  1017.  
  1018. A: If you have several objectives, then you may find that they cannot all be
  1019. optimized by any one solution. Instead, you will need to look for a solution
  1020. or solutions that achieve an acceptable tradeoff between objectives.
  1021. Deciding what tradeoffs are "acceptable" is a topic of investigation in its
  1022. own right. You may want to consult MCDM WorldScan, the newsletter of the
  1023. International Society on Multiple Criteria Decision Making.
  1024.  
  1025. There are a few free software packages specifically for multiple objective
  1026. linear programming, including:
  1027.  
  1028.    * ADBASE computes all efficient (i.e., nondominated) extreme points of a
  1029.      multiple objective linear program. It is available without charge for
  1030.      research and instructional purposes. If someone has a genuine need for
  1031.      such a code, they should send a request to: Ralph E. Steuer, Faculty of
  1032.      Management Science, Brooks Hall, University of Georgia, Athens, GA
  1033.      30602-6255.
  1034.    * PROTASS is also available. Currently its web page is in Polish, but you
  1035.      can write to protass@free.polbox.pl.
  1036.    * NIMBUS is an interactive multiobjective optimization system that has a
  1037.      Web interface.
  1038.  
  1039. Other approaches that have worked are:
  1040.  
  1041.    * Goal Programming (treat the objectives as constraints with costed
  1042.      slacks), or, almost equivalently, form a composite function from the
  1043.      given objective functions;
  1044.    * Pareto preference analysis (essentially brute force examination of all
  1045.      vertices);
  1046.    * Put your objective functions in priority order, optimize on one
  1047.      objective, then change it to a constraint fixed at the optimal value
  1048.      (perhaps subject to a small tolerance), and repeat with the next
  1049.      function.
  1050.  
  1051. There is a section on this whole topic in [Nemhauser]. [Schrage] has a
  1052. chapter devoted to the subject. [Hwang] has also been recommended by a
  1053. reader on Usenet. As a final piece of advice, if you can cast your model in
  1054. terms of physical realities, or dollars and cents, sometimes the multiple
  1055. objectives disappear! 8v)
  1056.  
  1057. Q6.6: "I have an LP that has large almost-independent matrix blocks that are
  1058. linked by a few constraints. Can I take advantage of this?"
  1059.  
  1060. A: Possibly. See section 6.2 in [Nemhauser] for a discussion of
  1061. Dantzig-Wolfe decomposition. I am told that the commercial code OSL has
  1062. features to assist in doing this. With any other code, you'll have to create
  1063. your own framework and then call the LP solver to solve the subproblems. The
  1064. folklore is that generally such schemes take a long time to converge so that
  1065. they're slower than just solving the model as a whole, although research
  1066. continues. For now my advice, unless you are using OSL or your model is so
  1067. huge that a good solver can't fit it in memory, is to not bother decomposing
  1068. it. It's probably more cost effective to upgrade your solver, if the
  1069. algorithm is limiting you, than to invest your time; but I suppose that's an
  1070. underlying theme in a lot of my advice. 8v)
  1071.  
  1072. Q6.7: "I am looking for an algorithm to compute the convex hull of a finite
  1073. number of points in n-dimensional space."
  1074.  
  1075. A: There is a program called qhull, available at
  1076. ftp://geom.umn.edu/pub/software/qhull.tar.Z. When you uncompress it and
  1077. untar it, it will create a directory called qhull which has source code plus
  1078. a README file. It uses the "Beneath Beyond" method, described in
  1079. [Edelsbrunner].
  1080.  
  1081. A code in C called cdd is available at ftp://ifor13.ethz.ch/pub/fukuda/cdd
  1082. and is written by Komei Fukuda; download the file named cdd-***.tar.Z, where
  1083. *** is the version number (choose the most recent version, which at last
  1084. check was 056). It solves the problem stated above, as well as that of
  1085. enumerating all vertices. There is also a C++ version at this site (version
  1086. 073).
  1087.  
  1088. A code in C called rs, by David Avis, is available at
  1089. ftp://mutt.cs.mcgill.ca/pub/C/README and implements the reverse search
  1090. method.
  1091.  
  1092. Ken Clarkson has written a program called Hull which is an ANSI C program
  1093. that computes the convex hull of a point set in general dimension. The input
  1094. is a list of points, and the output is a list of facets of the convex hull
  1095. of the points, each facet presented as a list of its vertices. It can be
  1096. downloaded from ftp://netlib.bell-labs.com/netlib/voronoi/hull.shar.Z.
  1097.  
  1098. There is a directory in ftp://elib.zib-berlin.de/pub/mathprog/polyth that
  1099. contains pointers to some tools for such problems.
  1100.  
  1101. Nina Amenta has a list of computational geometry software at
  1102. http://www.geom.umn.edu/locate/cglist.
  1103.  
  1104. Other algorithms for such problems are described in [Swart], [Seidel], and
  1105. [Avis]. Such topics are said to be discussed in [Schrijver] (page 224),
  1106. [Chvatal] (chapter 18), [Balinski], and [Mattheis] as well. Part of the
  1107. method described in [Avis], to enumerate vertices, is implemented in a
  1108. Mathematica package called VertexEnum.m at
  1109. ftp://cs.sunysb.edu/pub/Combinatorica, in file VE041.Z.
  1110.  
  1111. Q6.8: "Are there any parallel LP codes?"
  1112.  
  1113. A: The vendors for OSL, CPLEX and XPRESS-MP each have announced parallel
  1114. implementations of Branch and Bound solvers for MIP. CPLEX has also
  1115. announced parallel implementations of its barrier and dual simplex
  1116. algorithms on the Silicon Graphics Power Challenge, and OSL likewise has a
  1117. parallel implementation of its barrier method for its SP2 system.
  1118.  
  1119. Jeffrey Horn (horn@cs.wisc.edu) has compiled a bibliography of papers
  1120. relating to research on parallel B&B. There is an survey article by Gendron
  1121. and Crainic in the journal Operations Research, Vol. 42 (1994), No. 6, pp.
  1122. 1042-1066.
  1123.  
  1124. If your particular model is a good candidate for decomposition (see
  1125. Decomposition, above) then that form of parallelism could also be very
  1126. useful, but you'll have to implement it yourself. Here's what I say to
  1127. people who write parallel LP solvers as class projects:
  1128.  
  1129. You are probably working with the tableau form of the Simplex method. This
  1130. method works well for small models, but it is inefficient for most
  1131. real-world models because such models are usually <1% dense. Sparse matrix
  1132. methods dominate here. It may well be true that you can get good parallel
  1133. speedups with your code, but I'd wager that by the time you get to problems
  1134. with 1000 rows, any parallel-dense LP code will be slower than a single-
  1135. processor sparse code. And, worse yet, I think it's generally accepted that
  1136. no one currently knows how to do a good (i.e., scalable) parallel sparse LP
  1137. code. I wouldn't be harping on this point, except that most people's
  1138. interest in parallelism is because of the promise of scalability, in which
  1139. case large-scale considerations are important. Writing even a
  1140. single-processor large-scale LP code is a multi-year project, realistically.
  1141. The point is, don't get too enthralled by speedups in your code, unless
  1142. there's something to what you are doing that I haven't guessed.
  1143.  
  1144. Q6.9: "What software is there for Network models?"
  1145.  
  1146. A: In the context of linear programming, the term "network" is most often
  1147. associated with the minimum-cost network flow problem. A network for this
  1148. problem is viewed as a collection of nodes (or circles or locations) and
  1149. arcs (or lines or routes) connecting selected pairs of nodes. Arcs carry a
  1150. physical or conceptual flow of some kind, and may be directed (one-way) or
  1151. undirected (two-way). Some nodes may be sources (permitting flow to enter
  1152. the network) or sinks (permitting flow to leave).
  1153.  
  1154. The network linear programming problem is to minimize the (linear) total
  1155. cost of flows along all arcs of a network, subject to conservation of flow
  1156. at each node, and upper and/or lower bounds on the flow along each arc. This
  1157. is a special case of the general linear programming problem. The
  1158. transportation problem is an even more special case in which the network is
  1159. bipartite: all arcs run from nodes in one subset to the nodes in a disjoint
  1160. subset. A variety of other well-known network problems, including shortest
  1161. path problems, maximum flow problems, and certain assignment problems, can
  1162. also be modeled and solved as network linear programs. Details are presented
  1163. in many books on linear programming and operations research.
  1164.  
  1165. Network linear programs can be solved 10 to 100 times faster than general
  1166. linear programs of the same size, by use of specialized optimization
  1167. algorithms. Some commercial LP solvers include a version of the network
  1168. simplex method for this purpose. That method has the nice property that, if
  1169. it is given integer flow data, it will return optimal flows that are
  1170. integral. Integer network LPs can thus be solved efficiently without resort
  1171. to complex integer programming software.
  1172.  
  1173. Unfortunately, many different network problems of practical interest do not
  1174. have a formulation as a network LP. These include network LPs with
  1175. additional linear "side constraints" (such as multicommodity flow problems)
  1176. as well as problems of network routing and design that have completely
  1177. different kinds of constraints. In principle, nearly all of these network
  1178. problems can be modeled as integer programs. Some "easy" cases can be solved
  1179. much more efficiently by specialized network algorithms, however, while
  1180. other "hard" ones are so difficult that they require specialized methods
  1181. that may or may not involve some integer programming. Contrary to many
  1182. people's intuition, the statement of a hard problem may be only marginally
  1183. more complicated than the statement of some easy problem.
  1184.  
  1185. A canonical example of a hard network problem is the "traveling salesman"
  1186. problem of finding a shortest tour through a network that visits each node
  1187. once. A canonical easy problem not obviously equivalent to a linear program
  1188. is the "minimum spanning tree" problem to find a least-cost collection of
  1189. arcs that connect all the nodes. But if instead you want to connect only
  1190. some given subset of nodes (the "Steiner tree" problem) then you are faced
  1191. with a hard problem. These and many other network problems are described in
  1192. some of the references below.
  1193.  
  1194. Software for network optimization is thus in a much more fragmented state
  1195. than is general-purpose software for linear programming. The following are
  1196. some of the implementations that are available for downloading. Most are
  1197. freely available for many purposes, but check their web pages or "readme"
  1198. files for details.
  1199.  
  1200.    * ASSCT, an implementation of the Hungarian Method for the Assignment
  1201.      problem (#548 from Collected Algorithms of the ACM).
  1202.  
  1203.    * GIDEN, an interactive graphical environment for a variety of network
  1204.      problems and algorithms, available as a Java application or as an
  1205.      applet that can be executed through any Java-enabled Web browser.
  1206.      Further information is available by writing to giden@iems.nwu.edu.
  1207.  
  1208.    * MCF, a C implementation of the network simplex method (from Andreas
  1209.      Loebel, loebel@zib.de).
  1210.  
  1211.    * Netflo, the Fortran network simplex code from [Kennington], and several
  1212.      codes for maximum matching and maximum flow problems (from DIMACS,
  1213.      help@dimacs.rutgers.edu)
  1214.  
  1215.    * PPRN, for single or multicommodity network flow problems having a
  1216.      linear or nonlinear objective function, optionally with linear side
  1217.      constraints, by Jordi Castro (jcastro@etse.urv.es)
  1218.  
  1219.    * RELAX-IV for minimum-cost network flows (by Dimitri Bertsekas,
  1220.      bertsekas@lids.mit.edu and Paul Tseng, tseng@math.washington.edu); also
  1221.      a C++ version of the RELAX-IV algorithm (at the Department of Computer
  1222.      Science, University of Pisa, frangio@di.unipi.it)
  1223.  
  1224. The following indexes may also be useful:
  1225.  
  1226.    * Network optimization codes in Fortran 77 and in C, compiled by Ernesto
  1227.      Martins (eqvm@mat.uc.pt)
  1228.  
  1229.    * The network optimization library, including codes for assignment,
  1230.      shortest path, minimum-cost flow, and maximum flow/minimum cut, by
  1231.      Andrew Goldberg (avg@research.nj.nec.com).
  1232.  
  1233.    * Optimization routines for networks and graphs in the listing of
  1234.      public-domain optimization codes maintained by Jiefeng Xu
  1235.      (Jiefeng.Xu@Colorado.edu).
  1236.  
  1237.    * Network optimization listings from the NEOS Guide.
  1238.  
  1239. Fortran code for the Assignment Problem and others can also be copied
  1240. from[Burkard] and from [Martello].
  1241.  
  1242. Q6.10: "What software is there for the Traveling Salesman Problem (TSP)?"
  1243.  
  1244. A: TSP is a famously hard problem that has attracted many of the best minds
  1245. in the field. Solving for a proved optimum is combinatorial in nature;
  1246. methods have been explored both to give proved optimal solutions, and to
  1247. give approximate but "good" solutions. To my knowledge, there aren't any
  1248. commercial products to solve this problem. Public domain code for the
  1249. Asymmetric TSP is available in TOMS routine #750 available at
  1250. ftp://netlib2.cs.utk.edu/toms/750; it is documented in [Carpaneto]. For a
  1251. bibliography, check the Integer Programming section of [Nemhauser],
  1252. particularly the references with the names Groetschel and/or Padberg in
  1253. them. A good reference is [Lawler]. Another good one is [Reinelt]. There are
  1254. some heuristics for getting a "good" solution in the article by Lin and
  1255. Kernighan in Operations Research, Vol 21 (1973), pp 498-516. [Syslo]
  1256. contains some algorithms and Pascal code. Numerical Recipes [Press] contains
  1257. code that uses Simulated Annealing. [Bentley] is said to contain a
  1258. description of how to write a TSP code. Code for a solver can be obtained
  1259. via instructions in [Volgenant]. Bob Craig of Lucent Technologies
  1260. (kat3@ihgp-ebb.ih.lucent.com) has software written in C, for both exact
  1261. solution and heuristics, that he is willing to make available to those who
  1262. request it. Likewise, Chad Hurwitz (churritz@cts.com), offers a code called
  1263. tsp_solve for heuristic and optimal solution, to those who email him.
  1264.  
  1265. Q6.11: "What software is there for the Knapsack Problem?"
  1266.  
  1267. A: As with the TSP, I don't know of any commercial solvers for this specific
  1268. problem. Any good MIP solver should be able to be used, although any given
  1269. instance of this problem could be difficult. Specialized algorithms are said
  1270. to be available in [Syslo] and [Martello]. Bob Craig of Lucent Technologies
  1271. (kat3@ihgp-ebb.ih.lucent.com) has software written in C, for both exact
  1272. solution and heuristics, that he is willing to make available to those who
  1273. request it.
  1274.  
  1275. Q6.12: "What software is there for Stochastic Programming?"
  1276.  
  1277. A: [Thanks to Derek Holmes, dholmes@engin.umich.edu, for this text.] Your
  1278. success solving a stochastic program depends greatly on the characteristics
  1279. of your problem. The two broad classes of stochastic programming problems
  1280. are recourse problems and chance- constrained (or probabilistically
  1281. constrained) problems.
  1282.  
  1283. Recourse Problems are staged problems wherein one alteranates decisions with
  1284. realizations of stochastic data. The objective is to minimize total expected
  1285. costs of all decisions. The main sources of code (not necessarily public
  1286. domain) depend on how the data is distributed and how many stages (decision
  1287. points) are in the problem. For discretely distributed multistage problems,
  1288. a good package called MSLiP is available from Gus Gassman
  1289. (gassmann@ac.dal.ca, written up in Math. Prog. 47,407-423) Also, for not
  1290. huge discretely distributed problems, a deterministic equivalent can be
  1291. formed which can be solved with a standard solver. STOPGEN, available via
  1292. anonymous FTP from this author is a program which forms deterministic equiv.
  1293. MPS files from stopro problems in standard format (Birge, et. al., COAL
  1294. newsletter 17). The most recent program for continuously distributed data is
  1295. BRAIN, by K. Frauendorfer (frauendorfer@sgcl1.unisg.ch, written up in detail
  1296. in the author's monograph ``Stochastic Two-Stage Programming'', Lecture
  1297. Notes in Economics & Math. Systems #392 (Springer-Verlag).
  1298.  
  1299. CCP problems are not usually staged, and have a constraint of the form Pr(
  1300. Ax <= b ) >= alpha. The solvability of CCP problems depends on the
  1301. distribution of the data (A &/v b). I don't know of any public domain codes
  1302. for CCP probs., but you can get an idea of how to approach the problem by
  1303. reading Chapter 5 by Prof. A. Prekopa (prekopa@cancer.rutgers.edu) Y.
  1304. Ermoliev, and R. J-B. Wets, eds., Numerical Techniques for Stochastic
  1305. Optimization (Series in Comp. Math. 10, Springer-Verlag, 1988).
  1306.  
  1307. Both Springer Verlag texts mentioned above are good introductory references
  1308. to Stochastic Programming. This list of codes is far from comprehensive, but
  1309. should serve as a good starting point.
  1310.  
  1311. Q6.13: "I need to do post-optimal analysis."
  1312.  
  1313. A: Many commercial LP codes have features to do this. Also called Ranging or
  1314. Sensitivity Analysis, it gives information about how the coefficients in the
  1315. problem could change without affecting the nature of the solution. Most LP
  1316. textbooks, such as [Nemhauser], describe this. Unfortunately, all this
  1317. theory applies only to LP.
  1318.  
  1319. For a MIP model with both integer and continuous variables, you could get a
  1320. limited amount of information by fixing the integer variables at their
  1321. optimal values, re-solving the model as an LP, and doing standard
  1322. post-optimal analyses on the remaining continuous variables; but this tells
  1323. you nothing about the integer variables, which presumably are the ones of
  1324. interest. Another MIP approach would be to choose the coefficients of your
  1325. model that are of the most interest, and generate "scenarios" using values
  1326. within a stated range created by a random number generator. Perhaps five or
  1327. ten scenarios would be sufficient; you would solve each of them, and by some
  1328. means compare, contrast, or average the answers that are obtained. Noting
  1329. patterns in the solutions, for instance, may give you an idea of what
  1330. solutions might be most stable. A third approach would be to consider a
  1331. goal-programming formulation; perhaps your desire to see post-optimal
  1332. analysis is an indication that some important aspect is missing from your
  1333. model.
  1334.  
  1335. Q6.14: "Do LP codes require a starting vertex?"
  1336.  
  1337. A: No. You just have to give an LP code the constraints and the objective
  1338. function, and it will construct the vertices for you. Most codes go through
  1339. a so-called two phase method, wherein the code first looks for a feasible
  1340. solution, and then works on getting an optimal solution. The first phase can
  1341. begin anywhere, such as with all the variables at zero (though commercial
  1342. codes typically have a so-called "crash" algorithm to pick a better starting
  1343. point). So, no, you don't have to give a code a starting point. On the other
  1344. hand, it is not uncommon to do so, because it can speed up the solution time
  1345. tremendously. Commercial codes usually allow you to do this (they call it a
  1346. "basis", though that's a loose usage of a specific linear algebra concept);
  1347. free codes generally don't. You'd normally want to bother with a starting
  1348. basis only when solving families of related and difficult LP's (i.e., in
  1349. some sort of production mode).
  1350.  
  1351. Q6.15: "How can I combat cycling in the Simplex algorithm?"
  1352.  
  1353. A: Cycling is the condition that occurs when the Simplex method gets "stuck"
  1354. and finds itself repeating the same vertices over and over. While this
  1355. specific behavior is rather rare in practice, it is quite common for the
  1356. algorithm to reach a point where it temporarily stops making forward
  1357. progress in terms of improvement in the objective function; this is termed
  1358. "stalling", or more loosely known as "degeneracy" since it is caused by one
  1359. or more basic variables taking on the value of a lower or upper bound. In
  1360. most cases, the algorithm will work through this nest of coincident
  1361. vertices, then resume making tangible progress. However, in extreme cases
  1362. the degeneracy is so bad that to all intents and purposes it can be
  1363. considered cycling.
  1364.  
  1365. The simplest answer to the problem of degeneracy/cycling is often to "get a
  1366. better optimizer", i.e. one with stronger pricing algorithms, and a better
  1367. selection of features. However, obviously that is not always an option
  1368. (money!), and even the best LP codes can run into degeneracy on certain
  1369. models. Besides, they say it's a poor workman who blames his tools.
  1370.  
  1371. So, when one cannot change the optimizer, it's expedient to change the
  1372. model. Not drastically, of course, but a little "noise" can usually help to
  1373. break the ties that occur during the Simplex method. A procedure that can
  1374. work nicely is to add, to the values in the RHS, random values roughly six
  1375. orders of magnitude smaller. Depending on your model's formulation, such a
  1376. perturbation may not even seriously affect the quality of the solution
  1377. values. However, if you want to switch back to the original formulation, the
  1378. final solution basis for the perturbed model should be a useful starting
  1379. point for a "cleanup" optimization phase. (Depending on the code you are
  1380. using, this may take some ingenuity to do, however.)
  1381.  
  1382. Another helpful tactic: if your optimization code has more than one solution
  1383. algorithm, you can alternate among them. When one algorithm gets stuck,
  1384. begin again with another algorithm, using the most recent basis as a
  1385. starting point. For instance, alternating between a primal and a dual method
  1386. can move the solution away from a nasty point of degeneracy. Using partial
  1387. pricing can be a useful tactic against true cycling, as it tends to reorder
  1388. the columns. And of course Interior Point algorithms are much less affected
  1389. by (though not totally immune to) degeneracy. Unfortunately, the optimizers
  1390. richest in alternate algorithms and features also tend to be least prone to
  1391. problems with degeneracy in the first place.
  1392.  
  1393. [ ]
  1394.  
  1395. Q7. "What references and web links are there in this field?"
  1396.  
  1397. A: What follows here is an idiosyncratic list, a few books that I like, or
  1398. have been recommended on the net, or are recent. I have *not* reviewed them
  1399. all.
  1400.  
  1401. Regarding the common question of the choice of textbook for a college LP
  1402. course, it's difficult to give a blanket answer because of the variety of
  1403. topics that can be emphasized: brief overview of algorithms, deeper study of
  1404. algorithms, theorems and proofs, complexity theory, efficient linear
  1405. algebra, modeling techniques, solution analysis, and so on. A small and
  1406. unscientific poll of ORCS-L mailing list readers in 1993 uncovered a
  1407. consensus that [Chvatal] was in most ways pretty good, at least for an
  1408. algorithmically oriented class; of course, some new candidate texts have
  1409. been published in the meantime. For a class in modeling, a book about a
  1410. commercial code would be useful (LINDO, AMPL, GAMS were suggested),
  1411. especially if the students are going to use such a code; and I have always
  1412. had a fondness for the book by [Williams].
  1413.  
  1414. General reference
  1415.  
  1416.    * Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989.
  1417.      (Very broad-reaching, with large bibliography. Good reference; it's the
  1418.      place I tend to look first. Expensive, and tough reading for
  1419.      beginners.)
  1420.    * Harvey Greenberg has compiled an on-line Mathematical Programming
  1421.      Glossary.
  1422.  
  1423. Books containing source code
  1424.  
  1425.    * Best and Ritter, Linear Programming: active set analysis and computer
  1426.      programs, Prentice-Hall, 1985.
  1427.    * Bertsekas, D.P., Linear Network Optimization: Algorithms and Codes, MIT
  1428.      Press, 1991.
  1429.    * Bunday and Garside, Linear Programming in Pascal, Edward Arnold
  1430.      Publishers, 1987.
  1431.    * Bunday, Linear Programming in Basic (presumably the same publisher).
  1432.    * Burkard and Derigs, Springer Verlag Lecture Notes in Math Systems #184
  1433.      (the Assignment Problem and others).
  1434.    * Kennington & Helgason, Algorithms for Network Programming, Wiley, 1980.
  1435.      (A special case of LP; contains Fortran source code.)
  1436.    * Lau, H.T., A Numerical Library in C for Scientists and Engineers ,
  1437.      1994, CRC Press. (Contains a section on optimization.)
  1438.    * Martello and Toth, Knapsack Problems: Algorithms and Computer
  1439.      Implementations, Wiley, 1990. (Contains Fortran code, comes with a disk
  1440.      - also covers Assignment Problem.)
  1441.    * Press, Flannery, Teukolsky & Vetterling, Numerical Recipes, Cambridge,
  1442.      1986. (Comment: use their LP code with care.)
  1443.    * Syslo, Deo & Kowalik, Discrete Optimization Algorithms with Pascal
  1444.      Programs, Prentice-Hall (1983). (Contains code for 28 algorithms such
  1445.      as Revised Simplex, MIP, networks.)
  1446.  
  1447. LP textbooks
  1448.  
  1449.    * Bazaraa, Jarvis and Sherali. Linear Programming and Network Flows. Grad
  1450.      level.
  1451.    * Bertsimas, Dimitris and Tsitsiklis, John, Introduction to Linear
  1452.      Optimization. Athena Scientific, 1997 (ISBN 1-886529-19-1).
  1453.      Graduate-level text on linear programming, network flows, and discrete
  1454.      optimization.
  1455.    * Chvatal, Linear Programming, Freeman, 1983. Undergrad or grad.
  1456.    * Daellenbach and Bell, A User's Guide to LP. Good for engineers, but may
  1457.      be out of print.
  1458.    * Ecker & Kupferschmid, Introduction to Operations Research.
  1459.    * Ignizio, J.P. & Cavalier, T.M., Linear Programming, Prentice Hall,
  1460.      1994. Covers usual LP topics, plus interior point, multi-objective and
  1461.      heuristic techniques.
  1462.    * Luenberger, Introduction to Linear and Nonlinear Programming, Addison
  1463.      Wesley, 1984. Updated version of an old standby.
  1464.    * Murtagh, B., Advanced Linear Programming, McGraw-Hill, 1981. Good one
  1465.      after you've read an introductory text.
  1466.    * Murty, K., Linear and Combinatorial Programming.
  1467.    * Nash, S., and Sofer, A., Linear and Nonlinear Programming, McGraw-Hill,
  1468.      1996.
  1469.    * Nazareth, J.L., Computer Solution of Linear Programs, Oxford University
  1470.      Press, New York and Oxford, 1987.
  1471.    * Nering, E.D. & Tucker, A.W., Linear Programs and Related Problems,
  1472.      Academic Press, 1993.
  1473.    * Saigal, R., Linear Programming: A Modern Integrated Analysis, Kluwer
  1474.      Academic Publishers, 1995.
  1475.    * Schrijver, A., Theory of Linear and Integer Programming, Wiley, 1986.
  1476.      Advanced.
  1477.    * Taha, H., Operations Research: An Introduction, 1987.
  1478.    * Thie, P.R., An Introduction to Linear Programming and Game Theory,
  1479.      Wiley, 1988.
  1480.    * Vanderbei, Robert J., Linear Programming: Foundations and Extensions.
  1481.      Kluwer Academic Publishers, 1996 (ISBN 0-7923-9804-1). Balanced
  1482.      coverage of simplex and interior-point methods. Source code available
  1483.      on-line for all algorithms presented.
  1484.    * Williams, H.P., Model Building in Mathematical Programming, Wiley 1993,
  1485.      3rd edition. Little on algorithms, but excellent for learning what
  1486.      makes a good model.
  1487.  
  1488. Interior-Point LP methods (descendants of "Karmarkar's algorithm")
  1489.  
  1490.    * Arbel, Ami, Exploring Interior-Point Linear Programming, MIT Press,
  1491.      1993. Includes small-scale IBM PC software (binary only).
  1492.    * Fang and Puthenpura, Linear Optimization and Extensions. (Grad level
  1493.      textbook, also contains some Simplex and Ellipsoid. I heard mixed
  1494.      opinions on this one.)
  1495.    * Lustig, Marsten & Shanno, "Interior Point Methods for Linear
  1496.      Programming: Computational State of the Art", ORSA Journal on
  1497.      Computing, Vol. 6, No. 1, Winter 1994, pp. 1-14. Followed by commentary
  1498.      articles, and a rejoinder by the authors.
  1499.    * Roos, Terlaky and Vial, Theory and Algorithms for Linear Optimization:
  1500.      An Interior Point Approach. John Wiley, Chichester, 1997
  1501.    * Wright, Stephen J., Primal-Dual Interior-Point Methods. SIAM
  1502.      Publications, 1997. Covers theoretical, practical and computational
  1503.      aspects of the most important and useful class of interior-point
  1504.      algorithms. The web page for this book contains current information on
  1505.      interior-point codes for linear programming, including links to their
  1506.      web sites.
  1507.  
  1508. Presentations of commercially marketed systems (usable as texts for some
  1509. classes)
  1510.  
  1511.    * Bisschop & Entriken, AIMMS: The Modeling System, Paragon Decision
  1512.      Technology, 1993.
  1513.    * Brooke, Kendrick & Meeraus, GAMS: A Users' Guide, The Scientific
  1514.      Press/Duxbury Press, 1988.
  1515.    * Fourer, Gay & Kernighan, AMPL: A Modeling Language for Mathematical
  1516.      Programming, The Scientific Press/Duxbury Press, 1992. (Comes with DOS
  1517.      "student" version including MINOS and CPLEX.)
  1518.    * Greenberg, H.J., Modeling by Object-Driven Linear Elemental Relations:
  1519.      A User's Guide for MODLER, Kluwer Academic Publishers, 1993.
  1520.    * Schrage, L., LINDO: An Optimization Modeling System, The Scientific
  1521.      Press/Duxbury Press, 1991.
  1522.  
  1523. Additional books
  1524.  
  1525.    * Ahuja, Magnanti & Orlin, Network Flows, Prentice Hall, 1993.
  1526.    * Beasley, J.E., ed., Advances in Linear and Integer Programming. Oxford
  1527.      University Press, 1996 (ISBN 0-19-853856-1). Each chapter is a
  1528.      self-contained essay on one aspect of the subject.
  1529.    * Bondy & Murty, Graph Theory with Applications.
  1530.    * Edelsbrunner, Algorithms in Combinatorial Geometry, Springer Verlag,
  1531.      1987.
  1532.    * Forsythe, Malcolm & Moler, Computer Methods for Mathematical
  1533.      Computations, Prentice-Hall.
  1534.    * Gill, Murray and Wright, Numerical Linear Algebra and Optimization,
  1535.      Addison-Wesley, 1991.
  1536.    * Greenberg, H.J., A Computer-Assisted Analysis System for Mathematical
  1537.      Programming Models and Solutions: A User's Guide for ANALYZE, Kluwer
  1538.      Academic Publishers, 1993.
  1539.    * Hwang & Yoon, Multiple Attribute Decision Making : Methods and
  1540.      Applications, Springer-Verlag, Lecture Notes #186.
  1541.    * Lawler, Lenstra, et al, The Traveling Salesman Problem, Wiley, 1985.
  1542.    * More' & Wright, Optimization Software Guide, SIAM Publications, 1993.
  1543.      See also the NEOS Guide to Optimization Software.
  1544.    * Murty, Network Programming, Prentice Hall, 1992.
  1545.    * Papadimitriou & Steiglitz, Combinatorial Optimization. (Also contains a
  1546.      discussion of complexity of Simplex method.)
  1547.    * Reeves, C.R., ed., Modern Heuristic Techniques for Combinatorial
  1548.      Problems, Halsted Press (Wiley), 1993. (Contains chapters on tabu
  1549.      search, simulated annealing, genetic algorithms, neural nets, and
  1550.      Lagrangian relaxation.)
  1551.    * Reinelt, G., The Travelling Salesman: Computational Solutions for TSP
  1552.      Applications, Springer-Verlag Lecture Notes in Computer Science #840,
  1553.      1994.
  1554.  
  1555. Other publications
  1556.  
  1557.    * Avis & Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex
  1558.      Enumeration of Arrangements and Polyhedra", Discrete and Computational
  1559.      Geometry, 8 (1992), 295--313.
  1560.    * Balas, E. and Martin, C., "Pivot And Complement: A Heuristic For 0-1
  1561.      Programming Problems", Management Science, 1980, Vol 26, pp 86-96.
  1562.    * Balinski, M.L., "An Algorithm for Finding all Vertices of Convex
  1563.      Polyhedral Sets", SIAM J. 9, 1, 1961.
  1564.    * Carpaneto, Dell'amico & Toth, "A Branch-and-bound Algorithm for Large
  1565.      Scale Asymmetric Travelling Salesman Problems", ACM Transactions on
  1566.      Mathematical Software (TOMS), December 1995.
  1567.    * Mattheis and Rubin, "A Survey and Comparison of Methods for Finding All
  1568.      Vertices of Convex Polyhedral Sets", Mathematics of Operations
  1569.      Research, vol. 5 no. 2 1980, pp. 167-185.
  1570.    * Seidel, "Constructing Higher-Dimensional Convex Hulls at Logarithmic
  1571.      Cost per Face", 1986, 18th ACM STOC, 404--413.
  1572.    * Smale, Stephen, "On the Average Number of Steps in the Simplex Method
  1573.      of Linear Programming", Math Programming 27 (1983), 241-262.
  1574.    * Swart, "Finding the Convex Hull Facet by Facet", Journal of Algorithms,
  1575.      6 (1985), 17--48.
  1576.    * Volgenant, A., Symmetric TSPs, European Journal of Operations Research,
  1577.      49 (1990) 153-154.
  1578.  
  1579. On-Line Sources of Papers and Bibliographies
  1580.  
  1581.    * Michael Trick's Operations Research Page at http://mat.gsia.cmu.edu/
  1582.    * Optimization Technology Center: home of NEOS, Network-Enabled
  1583.      Optimization System.
  1584.    * WORMS (World-Wide-Web for Operations Research and Management Science)
  1585.      at http://www.maths.mu.oz.au/~worms/
  1586.    * List of interesting optimization codes in public domain at
  1587.      http://ucsu.colorado.edu/~xu/software.html. Includes many of the codes
  1588.      listed here, plus others of interest for specific problem classes.
  1589.    * Computational Mathematics Archive (London and South East Centre for
  1590.      High Performance Computing)
  1591.      http://www.lpac.ac.uk/SEL-HPC/Articles/GeneratedHtml/math.opt.html
  1592.    * Bibliography of books and survey papers on combinatorial optimization
  1593.      compiled by Brian Borchers (borchers@nmt.edu),
  1594.      ftp://archives.math.utk.edu/teaching.materials/bibliography/comb.opt.
  1595.    * Bibliography of books and papers on Interior-Point methods (taking more
  1596.      than 400 kilobytes storage with over 1300 entries!?!) in
  1597.      ftp://netlib2.cs.utk.edu/bib/intbib.bib, compiled by Dr. Eberhard
  1598.      Kranich (puett@math.uni-wuppertal.de).
  1599.    * Interior-Point Methods Online (another service of NEOS) contains most
  1600.      new reports in the area of interior-point methods that have appeared
  1601.      since December 1994 (over 200 reports as of March 1997). Abstracts for
  1602.      all reports are available, as are links to postscript source for most
  1603.      reports . A mailing list is used to notify interested parties whenever
  1604.      a new report arrives. You can join the list through a web page, or you
  1605.      can send mail to interior-point-methods-request@mcs.anl.gov containing
  1606.      the single word subscribe.
  1607.    * Information related to Semidefinite Programming is at
  1608.      ftp://orion.uwaterloo.ca/pub/henry/teaching/co769g/readme.html
  1609.    * An extensive bibliography for stochastic programming has been compiled
  1610.      by Maarten van der Vlerk at
  1611.      http://mally.eco.rug.nl/biblio/stoprog.html.
  1612.    * INFORMS home page is at http://www.informs.org/.
  1613.    * IMPS Consortium is at http://www-math.cudenver.edu/~hgreenbe/imps.html
  1614.  
  1615. On-Line Sources of Optimization Services
  1616.  
  1617. The following web sites offer, in some sense, to run your optimization
  1618. problem and return a result. Check their home pages for details, which vary
  1619. considerably. (Some are intended for nonlinear programming, but are included
  1620. here for completeness.)
  1621.  
  1622.    * DecisionNet. Provides access to "a distributed collection of decision
  1623.      technologies," including linear programming, "that are made available
  1624.      for execution over the World Wide Web. These technologies are developed
  1625.      and maintained locally by their providers. DecisionNet contains
  1626.      technology metainformation necessary to guide consumers in search,
  1627.      selection, and execution of these technologies." Facilities for
  1628.      submitting problems in popular modeling language formats are currently
  1629.      being tested.
  1630.  
  1631.    * GIDEN. An interactive graphical environment for a variety of network
  1632.      optimization problems and algorithms. It is written in Java, so you can
  1633.      try it out through any Java-enabled Web browser.
  1634.  
  1635.    * IBM Optimization Subroutine Library (OSL). Linear and quadratic
  1636.      programs in MPS format may be submitted by anonymous ftp.
  1637.  
  1638.    * Internet Enabled HQP Optimization Service. Nonlinear problems in SIF
  1639.      format may be submitted by e-mail.
  1640.  
  1641.    * MILP by Dmitry V. Golovashkin. Small-scale mixed-integer programs in a
  1642.      simple algebraic format are solved through a web form interface.
  1643.  
  1644.    * Network-Enabled Optimization System (NEOS) Server. Offers access to
  1645.      about a dozen solvers for linear and nonlinear programming, network and
  1646.      stochastic linear programming, unconstrained and bound-constrained
  1647.      optimization of nonlinear functions, and nonlinear complementarity.
  1648.      Linear programs in MPS format and nonlinear problems in the form of a C
  1649.      or Fortran program may be submitted by sending e-mail, by submitting
  1650.      URLs through a Web page, or via a high-speed socket-based Unix
  1651.      interface. Linear and nonlinear programs in the AMPL modeling language
  1652.      can also be sent to some of the solvers, by e-mail or URL.
  1653.  
  1654.    * NIMBUS. A multiobjective optimization system that accepts algebraic
  1655.      problem specifications through a series of Web forms.
  1656.  
  1657.    * Numerica. Global nonlinear optimization problems may be submitted in
  1658.      Numerica's algebraic modeling language, through a web form interface.
  1659.  
  1660. [ ]
  1661.  
  1662. Q8. "How do I access the Netlib server?"
  1663.  
  1664. A: If you have FTP access, you can try "ftp netlib2.cs.utk.edu", using
  1665. "anonymous" as the Name, and your email address as the Password. Do a "cd
  1666. (dir)" where (dir) is whatever directory was mentioned, and look around,
  1667. then do a "get (filename)" on anything that seems interesting. There often
  1668. will be a "README" file, which you would want to look at first. Another FTP
  1669. site is netlib.bell-labs.com although you will first need to do "cd netlib"
  1670. before you can cd to the (dir) you are interested in. Alternatively, you can
  1671. reach an e-mail server via "netlib@ornl.gov", to which you can send a
  1672. message saying "send index from (dir)"; follow the instructions you receive.
  1673. This is a list of sites mirroring the netlib repository:
  1674.  
  1675.    * Norway netlib@nac.no
  1676.    * England netlib@ukc.ac.uk
  1677.    * Germany anonymous@elib.zib-berlin.de
  1678.    * Taiwan netlib@nchc.edu.tw
  1679.    * Australia netlib@draci.cs.uow.edu.au
  1680.  
  1681. For those who have WWW (Mosaic, etc.) access, one can access Netlib via the
  1682. URL http://www.netlib.org. Also, there is, for X window users, a utility
  1683. called xnetlib that is available at ftp://netlib2.cs.utk.edu/xnetlib (look
  1684. at the "readme" file first).
  1685.  
  1686. [ ]
  1687.  
  1688. Q9. "Who maintains this FAQ list?"
  1689.  
  1690. A: This list was established by John W. Gregory (ashbury@skypoint.com), and
  1691. is currently being maintained by Robert Fourer (4er@iems.nwu.edu) and the
  1692. Optimization Technology Center.
  1693.  
  1694. This article is Copyright 1997 by Robert Fourer and John W. Gregory. It may
  1695. be freely redistributed in its entirety provided that this copyright notice
  1696. is not removed. It may not be sold for profit or incorporated in commercial
  1697. documents without the written permission of the copyright holder. Permission
  1698. is expressly granted for this document to be made available for file
  1699. transfer from installations offering unrestricted anonymous file transfer on
  1700. the Internet.
  1701.  
  1702. The material in this document does not reflect any official position taken
  1703. by any organization. While all information in this article is believed to be
  1704. correct at the time of writing, it is provided "as is" with no warranty
  1705. implied.
  1706.  
  1707. If you wish to cite this FAQ formally (hey, someone actually asked for
  1708. this), you may use:
  1709.  
  1710.      Fourer, Robert (4er@iems.nwu.edu) and Gregory, John W.
  1711.      (ashbury@skypoint.com), "Linear Programming FAQ" (1997). World
  1712.      Wide Web http://www.mcs.anl.gov/home/otc/
  1713.      faq/linear-programming-faq.html, Usenet sci.answers, anonymous FTP
  1714.      /pub/usenet/sci.answers/ linear-programming-faq from rtfm.mit.edu.
  1715.  
  1716. There's a mail server on rtfm.mit.edu, so if you don't have FTP privileges,
  1717. you can send an e-mail message to mail-server@rtfm.mit.edu containing:
  1718.  
  1719.     send usenet/sci.answers/linear-programming-faq
  1720.  
  1721. as the body of the message to receive the latest version (it is posted on
  1722. the first working day of each month). This FAQ is cross-posted to
  1723. news.answers and sci.op-research.
  1724.  
  1725. Suggestions, corrections, topics you'd like to see covered, and additional
  1726. material are all solicited. Send email to 4er@iems.nwu.edu.
  1727.  
  1728. [ ]
  1729.  
  1730. END linear-programming-faq
  1731.