home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / answers / linear-programming-faq < prev    next >
Text File  |  1993-12-09  |  50KB  |  949 lines
  1. Newsgroups: news.answers,sci.answers,sci.op-research
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!nic.hookup.net!swrinde!cs.utexas.edu!howland.reston.ans.net!vixen.cso.uiuc.edu!uchinews!cdsmail!timbuk.cray.com!walter.cray.com!jwg
  3. From: jwg@cray.com (John Gregory)
  4. Subject: Linear Programming FAQ
  5. Message-ID: <linear-programming-faq-1-754759312@cray.com>
  6. Followup-To: sci.op-research
  7. Summary: A List of Frequently Asked Questions about Linear Programming
  8. Originator: jwg@ceres
  9. Keywords: FAQ, LP, Linear Programming
  10. Lines: 930
  11. Nntp-Posting-Host: ceres.cray.com
  12. Reply-To: jwg@cray.com (John Gregory)
  13. Organization: Cray Research, Inc., Eagan MN USA
  14. Date: 1 Dec 93 09:22:15 CST
  15. Approved: news-answers-request@MIT.Edu
  16. Expires: 02/04/94
  17. Xref: senator-bedfellow.mit.edu news.answers:15616 sci.answers:716 sci.op-research:419
  18.  
  19. Posted-By: auto-faq 2.4
  20. Archive-name: linear-programming-faq
  21. Last-modified: December 1, 1993
  22.  
  23.          Linear Programming - Frequently Asked Questions List
  24.                        (linear-programming-faq)
  25.           Posted monthly to Usenet newsgroup sci.op-research
  26.                  Most recent update: December 1, 1993
  27.  
  28. -----------------------------------------------------------------------
  29.  
  30. "The best way to get information on Usenet isn't to ask a question, but
  31.  to post the wrong information."  -- aahz@netcom.com
  32.  
  33. Q0.  "What's in this FAQ?"
  34.  
  35. A:  Table of Contents
  36.    Q1.  "What is Linear Programming?"
  37.    Q2.  "Where is there a good code to solve LP problems?"
  38.    Q3.  "Oh, and we also want to solve it as an integer program."
  39.    Q4.  "I wrote an optimization code.  Where are some test models?"
  40.    Q5.  "What is MPS format?"
  41.    Q6.  "Just a quick question..."
  42.    Q7.  "What references are there in this field?"
  43.    Q8.  "How do I access the Netlib server?"
  44.    Q9.  "Who maintains this FAQ list?"
  45.  
  46. See also the related FAQ on Nonlinear Programming (NLP).
  47.  
  48. -----------------------------------------------------------------------
  49.  
  50. Q1.  "What is Linear Programming?"
  51.  
  52. A:  A Linear Program (LP) is a problem that can be put into the form
  53.  
  54.     minimize   cx
  55.     subject to Ax  = b
  56.                 x >= 0
  57.  
  58. where x is the vector of variables to be solved for, A is a matrix of
  59. known coefficients, and c and b are vectors of known coefficients.  The
  60. expression "cx" is called the objective function, and the equations
  61. "Ax=b" are called the constraints.  All these entities must have
  62. consistent dimensions, of course, and you can add "transpose" symbols
  63. to taste.  The matrix A is generally not square, hence you don't solve
  64. an LP by just inverting A.  Usually A has more columns than rows, and
  65. Ax=b  is therefore under-determined, leaving great latitude in the
  66. choice of x with which to minimize cx.
  67.  
  68. LP problems are usually solved by a technique known as the Simplex
  69. Method, developed in the 1940's and after.  Briefly stated, this method
  70. works by taking a sequence of square submatrices of A and solving for
  71. x, in such a way that successive solutions always improve, until a
  72. point is reached where improvement is no longer possible.  A family of
  73. LP algorithms known as Interior Point (or Barrier) methods comes from
  74. nonlinear programming approaches proposed in 1958 and further developed
  75. in the late 80's.  These methods can be faster for many (but so far not
  76. all) large-scale problems.  Such methods are characterized by
  77. constructing a sequence of trial solutions that go through the interior
  78. of the solution space, in contrast to the Simplex Method which stays
  79. on the boundary and examines only the corners (vertices).  Large-scale
  80. LP codes, whatever the algorithm, invariably use sparse matrix
  81. techniques.
  82.  
  83. LP has a variety of uses, in such areas as petroleum, finance,
  84. forestry, transportation, and the military.
  85.  
  86. The word "Programming" is used here in the sense of "planning"; the
  87. necessary relationship to computer programming was incidental to the
  88. choice of name.  Hence the phrase "LP program" to refer to a piece of
  89. software is not a redundancy, although I tend to use the term "code"
  90. instead of "program" to avoid the possible ambiguity.
  91.  
  92. -----------------------------------------------------------------------
  93.  
  94. Q2.  "Where is there a good code to solve LP problems?"
  95.  
  96. A:  Nowadays, with good commercial software (i.e., code that you pay
  97. for), models with a few thousand constraints and several thousand
  98. variables can be tackled on a 386 PC.  Workstations can often handle
  99. models with variables in the tens of thousands, or even greater, and
  100. mainframes can go larger still.  Public domain (free) codes can be
  101. relied on to solve models of somewhat smaller dimension.  The choice of
  102. code can make more difference than the choice of computer hardware.
  103. It's hard to be specific about model sizes and speed, a priori, due to
  104. the wide variation in things like model structure and variation in
  105. factorizing the basis matrices; just because a given code has solved a
  106. model of a certain dimension, it may not be able to solve *all* models
  107. of the same size, or in the same amount of time.
  108.  
  109. There is a public domain code, written in C, called "lp_solve" that its
  110. author (Michel Berkelaar, email at  michel@es.ele.tue.nl ) says has
  111. solved models with up to 30,000 variables and 50,000 constraints.  The
  112. author requests that people retrieve it by anonymous ftp from
  113. "ftp.es.ele.tue.nl" in directory pub/lp_solve.  There is an older
  114. version to be found in the Usenet archives, but it contains bugs that
  115. have been fixed in the meantime, and hence is unsupported.  (As an
  116. editorial opinion, I must state that difficult models will give this
  117. code trouble.  It's not as good as a commercial code.  But for someone
  118. who isn't sure just what kind of LP code is needed, it represents a
  119. very reasonable first try, since it does solve non-trivial-sized
  120. models, and it is free.)  The author also made available a program that
  121. converts data files from MPS-format into lp_solve's own input format;
  122. it's in the same directory, in file mps2eq_0.1.tar.Z.
  123.  
  124. For academic users only, on a limited variety of platforms, there is
  125. available a free version of LOQO, a linear/quadratic program solver.
  126. Binary executables have been installed in /pub/opt-net/software/loqo,
  127. via anonymous ftp at elib.zib-berlin.de.  There are versions for
  128. workstations by IBM, Silicon Graphics, HP, and Sun.  The package
  129. includes a subroutine library (libloqo.a), an executable (loqo), the
  130. source for the main part of loqo (loqo.c), and associated documentation
  131. (loqo.dvi and *.eps).  The algorithm used is a one-phase primal-dual-
  132. symmetric interior-point method.  If you wish to purchase a commercial
  133. version, please contact Bob Vanderbei (rvdb@Princeton.EDU) for details.
  134.  
  135. The next several suggestions are for public-domain codes that are
  136. severely limited by the algorithm they use (tableau Simplex); they may
  137. be OK for models with (on the order of) 100 variables and constraints,
  138. but it's unlikely they will be satisfactory for larger models.  1) For
  139. DOS/PC users, there is an LP and Linear Goal Programming binary called
  140. "tslin", by anonymous ftp at garbo.uwasa.fi in directory /pc/ts (the
  141. current file name is tslin33b.zip, using ZIP compression), or else I
  142. suggest contacting Prof. Salmi at ts@uwasa.fi .  For North American
  143. users, the garbo server is mirrored on ftp site wuarchive.wustl.edu,
  144. in directory mirrors/garbo.uwasa.fi .  2) Also on the garbo server is a
  145. file called lp261.zip, having a descriptor of "Linear Programming
  146. Optimizer by ScanSoft".  It consists of PC binaries, and is evidently
  147. some sort of shareware (i.e., not strictly public domain).  3) There is
  148. an ACM TOMS routine for LP, #552, available from the netlib server, in
  149. directory /netlib/toms.  This routine was designed for fitting data to
  150. linear constraints using an L1 norm, but it uses a modification of the
  151. Simplex Method and could presumably be modified to satisfy LP purposes.
  152. 4) There are books that contain source code for the Simplex Method.
  153. See the section on references.  You should not expect such code to be
  154. robust.  In particular, you can check whether it uses a 2-dimensional
  155. array for the A-matrix; if so, it is surely using the tableau Simplex
  156. Method rather than sparse methods, and it will not be useful for large
  157. models.
  158.  
  159. The following suggestions may represent a low-cost way of solving LP's
  160. if you already have certain software available to you.  1) Some
  161. spreadsheet programs have an embedded LP solver, or offer one as an
  162. installable option.  2) A package called QSB (Quantitative Systems for
  163. Business, from Prentice-Hall publishers) has an LP module among its
  164. routines.  3) If you have access to a commercial math library, such as
  165. IMSL or NAG, you may be able to use an LP routine from there.
  166. 4) Mathematical systems MATLAB (The Math Works, Inc., (508) 653-1415)
  167. and MAPLE (reference?) also have LP solvers; an interface from MATLAB
  168. to lp_solve is available from Jeff Kantor (Jeffrey.Kantor@nd.edu), and
  169. there's also a Simplex code written in the MATLAB language, available
  170. from the netlib server, file netlib/matlab/optimization/simplex1.m.Z.
  171. (There's a Usenet newsgroup on MATLAB: comp.soft-sys.matlab.)  If
  172. speed matters to you, then according to a Usenet posting by Pascal
  173. Koiran (koiran@ens-lyon.fr), on randomly generated LP models, MATLAB
  174. was an order of magnitude faster than MAPLE on a 200x20 problem but an
  175. order of magnitude slower than lp_solve on a 50x100 problem.  (I don't
  176. intend to get into benchmarking in this document, but I mention these
  177. results just to explain why I choose to focus mostly on special purpose
  178. LP software.)
  179.  
  180. If your models prove to be too difficult for free or add-on software to
  181. handle, then you may have to consider acquiring a commercial LP code.
  182. Dozens of such codes are on the market.  There are many considerations
  183. in selecting an LP code.  Speed is important, but LP is complex enough
  184. that different codes go faster on different models; you won't find a
  185. "Consumer Reports" article to say with certainty which code is THE
  186. fastest.  I usually suggest getting benchmark results for your
  187. particular type of model if speed is paramount to you.  Benchmarking
  188. can also help determine whether a given code has sufficient numerical
  189. stability for your kind of models.
  190.  
  191. Other questions you should answer: Can you use a stand-alone code, or
  192. do you need a code that can be used as a callable library, or do you
  193. require source code?  Do you want the flexibility of a code that runs
  194. on many platforms and/or operating systems, or do you want code that's
  195. tuned to your particular hardware architecture (in which case your
  196. hardware vendor may have suggestions)?  Is the choice of algorithm
  197. (Simplex, Interior Point) important to you?  Do you need an interface
  198. to a spreadsheet code?  Is the purchase price an overriding concern?
  199. If you are at a university, is the software offered at an academic
  200. discount?  How much hotline support do you think you'll need?  There is
  201. usually a large difference in LP codes, in performance (speed,
  202. numerical stability, adaptability to computer architectures) and in
  203. features, as you climb the price scale.
  204.  
  205. At the end of this section is a *very* condensed version of a survey of
  206. LP software published in the June 1992 issue of "OR/MS Today", a joint
  207. publication of ORSA (Operations Research Society of America) and TIMS
  208. (The Institute of Management Science).  For further information I would
  209. suggest you read the full article.  It's likely that you can find a
  210. copy, either through a library, or by contacting a member of these two
  211. organizations (most universities probably have several members among
  212. the faculty and student body). This magazine also carries
  213. advertisements for many of these products, which may give you
  214. additional information to help make a decision.
  215.  
  216. The author of that survey, Ramesh Sharda, has updated and expanded it
  217. for 1993 into a larger report called "Linear and Discrete Optimization
  218. and Modeling Software: A Resource Handbook".  For information, contact
  219. Lionheart Publishing Inc., 2555 Cumberland Parkway, Suite 299, Atlanta,
  220. GA 30339. Phone: (404)-431-0867.  This book is fairly expensive, and
  221. geared toward users whose needs for LP software are considerable.
  222. Another book, to be available in November 1993 is "Optimization
  223. Software Guide," by Jorge More and Stephen Wright, from SIAM Books.
  224. Call 1-800-447-7426 to order ($24.50, less ten percent if you are a
  225. SIAM member).  It sounds promising ("75 software packages...").
  226.  
  227. In the table below, I give the name of the software and the phone
  228. number listed in the June 1992 survey.  I have included, where I know
  229. of one, an email address (information not given in the June 1992
  230. survey), and other information obtained from non-proprietary sources.
  231. To keep the table short enough to fit here, I decided not to include
  232. postal addresses.  (I suppose that an "800" number will not be useful
  233. to people outside the US; consult the full survey for more information
  234. on contacting such vendors.  Also, for some companies there may exist
  235. European or Asian contact points, but this is beyond the scope of this
  236. document.)
  237.  
  238. The first part of the table consists of software I deem to be LP
  239. solvers.  The second part is software that in some sense is a front end
  240. to the solvers (modeling software).  In some cases it becomes a hazy
  241. distinction, but I hope this arrangement of information turns out to be
  242. useful to the reader.
  243.  
  244. Under "H/W" is the minimum hardware said to be needed to run the code;
  245. generally I conceive of a hierarchy where PC's (and Macintoshes) are
  246. the least powerful, then workstations (WS) like Suns and RS-6000's, on
  247. up to supercomputers, so by the symbol "^" I mean "and up", namely that
  248. most commonly-encountered platforms are supported beyond the given
  249. minimum level.
  250.  
  251. Even more so than usual, I emphasize that you must use this information
  252. at your own risk.  I provide it as a convenience to those readers who
  253. have difficulty in locating the OR/MS Today survey, I take no
  254. responsibility for errors either in the original article or by my act
  255. of copying it manually, though I will gladly correct any mistakes that
  256. are pointed out to me.
  257.  
  258. Key to Features:  S=Simplex    I=Interior-Point or Barrier
  259.                   Q=Quadratic  G=General-Nonlinear
  260.                   M=MIP        N=Network
  261.                   V=Visualization
  262. Solver
  263. Code Name    Feat. H/W        Phone        Email address
  264. ---------    ----- ---------- ------------ -------------
  265. AT&T KORBX   IQ    WS ^       908-949-8966
  266. Best Answer  S     Mac-Plus   510-943-7667
  267. CPLEX        SIMN  PC-386 ^   702-831-7744 info@cplex.com
  268. Excel        SMG   PC/Mac     206-882-8080
  269. FortLP       SM    PC ^       708-971-2337
  270. HS/LP        SM    PC-386/VAX 201-627-1424
  271. INCEPTA      SMV   PC-386     416-896-0515
  272. LAMPS        SM    PC-386 ^   413-584-1605 al@andltd.and.nl
  273. LINDO        SMQ   PC ^       800-441-2378 lindo@delphi.com
  274. LOQO         IQ    PC ^       609-258-0876 rvdb@princeton.edu
  275. LP88         S     PC         703-360-7600
  276. MathPro      SMV   PC-286/WS  202-887-0296
  277. MILP88       SM    PC         703-360-7600
  278. MILP LO      SV    PC       (+361)149-7531
  279. MPS-III      SMNQ  PC-386 ^   703-558-8701
  280. MSLP-PC      S     PC         604-361-9778
  281. OMP          SM    PC/VAX/WS  919-847-9997
  282. OSL          SIMNQ PC/WS/IBM  914-385-6034 randym@vnet.ibm.com
  283. PC-PROG      SMQ   PC         919-847-9997 Ge.vanGeldorp@lr.tudelft.nl
  284. SAS/OR       SMN   PC ^       919-677-8000
  285. SCICONIC     SM    PC-386 ^(+44)908-585858
  286. STORM        SMN   PC         216-464-1209
  287. TurboSimplex S     PC/Mac     703-351-5272
  288. What If      SMG   PC         800-447-2226
  289. XA           SM    PC ^       818-441-1565 sunsetsoft@aol.com
  290. XPRESS-MP    SM    PC-286 ^   202-887-0296
  291. YLP          S     PC ^       702-831-4967
  292.  
  293. Modeling
  294. Code Name          H/W        Phone        Email address
  295. ---------          ---------- ------------ -------------
  296. DATAFORM           PC-386 ^   703-558-8701
  297. GAMS               PC-286 ^   415-583-8840 gams@gams.com
  298. LINGO              PC ^       800-441-2378 lindo@delphi.com
  299. MIMI/LP            WS         908-464-8300
  300. MPL Sys.           PC         703-351-5272
  301. OMNI               PC-386 ^   202-627-1424
  302. VMP                PC-386/WS  301-622-0694
  303. What's Best!       PC/Mac/WS  800-441-2378 lindo@delphi.com
  304.  
  305. -----------------------------------------------------------------------
  306.  
  307. Q3.  "Oh, and we also want to solve it as an integer program.
  308.  
  309. A:  Integer LP models are ones where the answers must not take
  310. fractional values.  It may not be obvious that this is a VERY much
  311. harder problem than ordinary LP, but it is nonetheless true.  The
  312. buzzword is "NP-Completeness", the definition of which is beyond the
  313. scope of this document but means in essence that, in the worst case,
  314. the amount of time to solve a family of related problems goes up
  315. exponentially as the size of the problem grows, for all algorithms that
  316. solve such problems to a proven answer.
  317.  
  318. Integer models may be ones where only some of the variables are to be
  319. integer and others may be real-valued (termed "Mixed Integer LP" or
  320. MILP, or "Mixed Integer Programming" or MIP); or they may be ones where
  321. all the variables must be integral (termed "Integer LP" or ILP).  The
  322. class of ILP is often further subdivided into problems where the only
  323. legal values are {0,1} ("Binary" or "Zero-One" ILP), and general
  324. integer problems.  For the sake of generality, the Integer LP problem
  325. will be referred to here as MIP, since the other classes can be viewed
  326. as special cases of MIP.  MIP, in turn, is a particular member of the
  327. class of Discrete Optimization problems.
  328.  
  329. People are sometimes surprised to learn that MIP problems are solved
  330. using floating point arithmetic.  Although various algorithms for MIP
  331. have been studied, most if not all available general purpose large-
  332. scale MIP codes use a method called "Branch and Bound" to try to find
  333. an optimal solution.  Briefly stated, B&B solves MIP by solving a
  334. sequence of related LP models.  (As a point of interest, the Simplex
  335. Method currently retains an advantage over the newer Interior Point
  336. methods for solving these sequences of LP's.)  Good codes for MIP
  337. distinguish themselves more by solving shorter sequences of LP's, than
  338. by solving the individual LP's faster.  Even more so than with regular
  339. LP, a costly commercial code may prove its value to you if your MIP
  340. model is difficult.
  341.  
  342. You should be prepared to solve *far* smaller MIP models than the
  343. corresponding LP model, given a certain amount of time you wish to
  344. allow (unless you and your model happen to be very lucky). There exist
  345. models that are considered challenging, with a few dozen variables.
  346. Conversely, some models with tens of thousands of variables solve
  347. readily.  The best explanations of "why" usually seem to happen after
  348. the fact.  8v)  But a MIP model with hundreds of variables should
  349. always be approached, initially at least, with a certain amount of
  350. humility.
  351.  
  352. A major exception to this somewhat gloomy outlook is that there are
  353. certain models whose LP solution always turns out to be integer.  Best
  354. known of these is the so-called Network-Flow Problem.  Special cases of
  355. this problem are the Transportation Problem, the Assignment Problem,
  356. and the Shortest Path Problem.  The theory of unimodular matrices is
  357. fundamental here.  It turns out that these particular problems are best
  358. solved by specialized routines that take major shortcuts in the Simplex
  359. Method, and as a result are relatively quick-running even compared to
  360. ordinary LP.  Some commercial LP solvers include a network solver.  See
  361. [Kennington], which contains some source code for Netflo.  Netflo is
  362. available by anonymous ftp at dimacs.rutgers.edu, in directory
  363.     /pub/netflow/mincost/solver-1
  364. but I don't know the copyright situation (I always thought you had to
  365. buy the book to get the code).  Another text containing Fortran code is
  366. [Bertsekas], though I am unaware of any place that has the source code
  367. online.  There is an ACM TOMS routine, #548, that solves the Assignment
  368. problem using the Hungarian Method, available from the netlib server,
  369. in directory /netlib/toms.  An article in the ORSA Journal on Computing
  370. in 1991 by Kennington and Wang investigated the performance of some
  371. algorithms.
  372.  
  373. The public domain code "lp_solve", mentioned earlier, accepts MIP
  374. models, as do a large number of the commercial LP codes in the OR/MS
  375. Today survey (see section above).  I have seen mention made of
  376. algorithm 333 in the Collected Algorithms from CACM, though I'd be
  377. surprised if it was robust enough to solve large models.
  378.  
  379. In [Syslo] is code for 28 algorithms, most of which pertain to some
  380. aspect of Discrete Optimization.
  381.  
  382. There is a code called Omega that analyzes systems of linear equations
  383. in integer variables.  It does not solve optimization problems, except
  384. in the case that a model reduces completely, but its features could be
  385. useful in analyzing and reducing MIP models.  Have a look via anonymous
  386. ftp at ftp.cs.umd.edu:pub/omega (documentation is provided there), or
  387. contact Bill Pugh at pugh@cs.umd.edu.
  388.  
  389. Mustafa Akgul (AKGUL@TRBILUN.BITNET) at Bilkent University maintains an
  390. archive via anonymous ftp (firat.bcc.bilkent.edu.tr or 139.179.10.13).
  391. In addition to a copy of lp_solve (though I would recommend using the
  392. official source listed in the previous section), there is mip386.zip,
  393. which is a zip-compressed code for PC's.  He also has a couple of
  394. network codes and various other codes he has picked up.  All this is in
  395. directory pub/IEOR/Opt and its further subdirectories LP, PC, and
  396. Network.
  397.  
  398. The better commercial MIP codes have numerous parameters and options to
  399. give the user control over the solution strategy.  Most have the
  400. capability of stopping before an optimum is proved, printing the best
  401. answer obtained so far.  For many MIP models, stopping early is a
  402. practical necessity.  Fortunately, a solution that has been proved by
  403. the algorithm to be within, say, 1% of optimality often turns out to be
  404. the true optimum, and the bulk of the computation time is spent proving
  405. the optimality. For many modeling situations, a near-optimal solution
  406. is acceptable anyway.
  407.  
  408. Once one accepts that large MIP models are not typically solved to a
  409. proved optimal solution, that opens up a broad area of approximate
  410. methods, probabilistic methods and heuristics, as well as modifications
  411. to B&B.  See [Balas] which contains a useful heuristic for 0-1 MIP
  412. models.  See also the brief discussion of Genetic Algorithms and
  413. Simulated Annealing in the FAQ on Nonlinear Programming.
  414.  
  415. Whatever the solution method you choose, when trying to solve a
  416. difficult MIP model, it is usually crucial to understand the workings
  417. of the physical system (or whatever) you are modeling, and try to find
  418. some insight that will assist your chosen algorithm to work better.  A
  419. related observation is that the way you formulate your model can be as
  420. important as the actual choice of solver.  You should consider getting
  421. some assistance if this is your first time trying to solve a large
  422. (>100 integer variable) problem.
  423.  
  424. -----------------------------------------------------------------------
  425.  
  426. Q4.  "I wrote an optimization code.  Where are some test models?"
  427.  
  428. A:  If you want to try out your code on some real-world LP models,
  429. there is a very nice collection of small-to-medium-size ones (with a
  430. few that are rather large) on netlib, in directory lp/data.  The netlib
  431. LP files (after you uncompress them) are in a format called MPS, which
  432. is described in another section of this document.
  433.  
  434. Also on netlib is a collection of infeasible LP models, located in
  435. directory lp/infeas.
  436.  
  437. There is a collection of MIP models, housed at Rice University.  Send
  438. an email message containing "send catalog" to  softlib@rice.edu , to
  439. get started.  Or try anonymous ftp at softlib.cs.rice.edu, then
  440. "cd /pub/miplib".
  441.  
  442. There is a collection of network-flow codes and models at DIMACS
  443. (Rutgers University).  Use anonymous FTP at dimacs.rutgers.edu.  Start
  444. looking in /pub/netflow.  Another network generator is called NETGEN
  445. and is available on netlib (lp/generators).
  446.  
  447. The modeling language GAMS comes with about 150 test models, which you
  448. might be able to test your code with.
  449.  
  450. John Beasley has posted information on his OR-Lib, which contains
  451. various optimization test problems.  Send e-mail to
  452. umtsk99@vaxa.cc.imperial.ac.uk to get started.  Or have a look in the
  453. Journal of the Operational Research Society, Volume 41, Number 11,
  454. Pages 1069-72.  Information about test problems for the problem areas
  455. listed below can be obtained by emailing o.rlibrary@ic.ac.uk with the
  456. email message being the file name for the problem areas you are
  457. interested in.
  458.  
  459.   Problem area                                  File name
  460.  
  461.   Assignment problem                            assigninfo
  462.   Crew scheduling                               cspinfo
  463.   Data envelopment analysis                     deainfo
  464.   Generalised assignment problem                gapinfo
  465.   Integer programming                           mipinfo
  466.   Linear programming                            lpinfo
  467.   Location:
  468.        capacitated warehouse location           capinfo
  469.        p-median                                 pmedinfo
  470.        uncapacitated warehouse location         uncapinfo
  471.   Multiple knapsack problem                     mknapinfo
  472.   Quadratic assignment problem                  qapinfo
  473.   Resource constrained shortest path            rcspinfo
  474.   Scheduling:
  475.        flow shop                                flowshopinfo
  476.        job shop                                 jobshopinfo
  477.        open shop                                openshopinfo
  478.   Set covering                                  scpinfo
  479.   Set partitioning                              sppinfo
  480.   Steiner:
  481.        Euclidean Steiner problem                esteininfo
  482.        Rectilinear Steiner problem              rsteininfo
  483.        Steiner problem in graphs                steininfo
  484.   Travelling salesman problem                   tspinfo
  485.   Two-dimensional cutting:
  486.        assortment problem                       assortinfo
  487.        constrained guillotine                   cgcutinfo
  488.        constrained non-guillotine               ngcutinfo
  489.        unconstrained guillotine                 gcutinfo
  490.   Vehicle routing:
  491.        fixed areas                              areainfo
  492.        fixed routes                             fixedinfo
  493.        period routing                           periodinfo
  494.        single period                            vrpinfo
  495.  
  496. -----------------------------------------------------------------------
  497.  
  498. Q5.  "What is MPS format?"
  499.  
  500. A:  MPS format was named after an early IBM LP product and has emerged
  501. as a de facto standard ASCII medium among most of the commercial LP
  502. codes.  Essentially all commercial LP codes accept this format, but if
  503. you are using public domain software and have MPS files, you may need
  504. to write your own reader routine for this.  It's not too hard.  See
  505. also the comment regarding the lp_solve code, in another section of
  506. this document, for the availability of an MPS reader.
  507.  
  508. The main things to know about MPS format are that it is column oriented
  509. (as opposed to entering the model as equations), and everything
  510. (variables, rows, etc.) gets a name.  MPS format is described in more
  511. detail in [Murtagh].
  512.  
  513. MPS is an old format, so it is set up as though you were using punch
  514. cards, and is not free format. Fields start in column 1, 5, 15, 25, 40
  515. and 50.  Sections of an MPS file are marked by so-called header cards,
  516. which are distinguished by their starting in column 1.  Although it is
  517. typical to use upper-case throughout the file (like I said, MPS has
  518. long historical roots), many MPS-readers will accept mixed-case for
  519. anything except the header cards, and some allow mixed-case anywhere.
  520. The names that you choose for the individual entities (constraints or
  521. variables) are not important to the solver; you should pick names that
  522. are meaningful to you, or will be easy for a post-processing code to
  523. read.
  524.  
  525. Here is a little sample model written in MPS format (explained in more
  526. detail below):
  527.  
  528. NAME          TESTPROB
  529. ROWS
  530.  N  COST
  531.  L  LIM1
  532.  G  LIM2
  533.  E  MYEQN
  534. COLUMNS
  535.     XONE      COST                 1   LIM1                 1
  536.     XONE      LIM2                 1
  537.     YTWO      COST                 4   LIM1                 1
  538.     YTWO      MYEQN               -1
  539.     ZTHREE    COST                 9   LIM2                 1
  540.     ZTHREE    MYEQN                1
  541. RHS
  542.     RHS1      LIM1                 5   LIM2                10
  543.     RHS1      MYEQN                7
  544. BOUNDS
  545.  UP BND1      XONE                 4
  546.  LO BND1      YTWO                -1
  547.  UP BND1      YTWO                 1
  548. ENDATA
  549.  
  550. For comparison, here is the same model written out in an equation-
  551. oriented format:
  552.  
  553. Optimize
  554.  COST:    XONE + 4 YTWO + 9 ZTHREE
  555. Subject To
  556.  LIM1:    XONE + YTWO <= 5
  557.  LIM2:    XONE + ZTHREE >= 10
  558.  MYEQN:   - YTWO + ZTHREE  = 7
  559. Bounds
  560.  0 <= XONE <= 4
  561. -1 <= YTWO <= 1
  562. End
  563.  
  564. Strangely, there is nothing in MPS format that specifies the direction
  565. of optimization.  And there really is no standard "default" direction;
  566. some LP codes will maximize if you don't specify otherwise, others will
  567. minimize, and still others put safety first and have no default and
  568. require you to specify it somewhere in a control program or by a
  569. calling parameter.  If you have a model formulated for minimization
  570. and the code you are using insists on maximization (or vice versa), it
  571. may be easy to convert: just multiply all the coefficients in your
  572. objective function by (-1).  The optimal value of the objective
  573. function will then be the negative of the true value, but the values of
  574. the variables themselves will be correct.
  575.  
  576. The NAME card can have anything you want, starting in column 15.  The
  577. ROWS section defines the names of all the constraints; entries in
  578. column 2 or 3 are E for equality rows, L for less-than ( <= ) rows, G
  579. for greater-than ( >= ) rows, and N for non-constraining rows (the
  580. first of which would be interpreted as the objective function).  The
  581. order of the rows named in this section is unimportant.
  582.  
  583. The largest part of the file is in the COLUMNS section, which is the
  584. place where the entries of the A-matrix are put.  All entries for a
  585. given column must be placed consecutively, although within a column the
  586. order of the entries (rows) is irrelevant. Rows not mentioned for a
  587. column are implied to have a coefficient of zero.
  588.  
  589. The RHS section allows one or more right-hand-side vectors to be
  590. defined; most people don't bother having more than one.  In the above
  591. example, the name of the RHS vector is RHS1, and has non-zero values
  592. in all 3 of the constraint rows of the problem.  Rows not mentioned in
  593. an RHS vector would be assumed to have a right-hand-side of zero.
  594.  
  595. The optional BOUNDS section lets you put lower and upper bounds on
  596. individual variables (no * wild cards, unfortunately), instead of
  597. having to define extra rows in the matrix.  All the bounds that have
  598. a given name in column 5 are taken together as a set.  Variables not
  599. mentioned in a given BOUNDS set are taken to be non-negative (lower
  600. bound zero, no upper bound).  A bound of type UP means an upper bound
  601. is applied to the variable.  A bound of type LO means a lower bound is
  602. applied.  A bound type of FX ("fixed") means that the variable has
  603. upper and lower bounds equal to a single value.  A bound type of FR
  604. ("free") means the variable has neither lower nor upper bounds.
  605.  
  606. There is another optional section called RANGES that I won't go into
  607. here. The final card must be ENDATA, and yes, it is spelled funny.
  608.  
  609. -----------------------------------------------------------------------
  610.  
  611. Q6.  "Just a quick question..."
  612.  
  613. Q:  What is a matrix generator?
  614. A:  This is a code that creates input for an LP (or MIP, or NLP) code,
  615.     using a more natural input than MPS format.  There are no free
  616.     ones.  Matrix generators can be roughly broken into two classes,
  617.     column oriented ones, and equation oriented ones.  The former class
  618.     is older, and includes such commercial products as OMNI (Haverley
  619.     Systems) and DATAFORM (Ketron).  Big names in the latter class are
  620.     GAMS (Scientific Press), LINGO (LINDO Systems), and AMPL
  621.     (information is in netlib/opt on the netlib server, or send email
  622.     to 70742.555@compuserve.com).  These products have links to various
  623.     solvers (commercial and otherwise).
  624.  
  625. Q:  How do I diagnose an infeasible LP model?
  626. A:  A model is infeasible if the constraints are inconsistent, i.e., if
  627.     no feasible solution can be constructed.  It's often difficult to
  628.     track down a cause.  The cure may even be ambiguous: is it that
  629.     some demand was set too high, or a supply set too low?  A useful
  630.     technique is Goal Programming, one variant of which is to include
  631.     two explicit slack variables (positive and negative), with huge
  632.     cost coefficients, in each constraint.  The revised model is
  633.     guaranteed to have a solution, and you can look at which rows have
  634.     slacks that are included in the "optimal" solution.  By the way, I
  635.     recommend a Goal Programming philosophy even if you aren't having
  636.     trouble with feasibility; "come on, you could probably violate this
  637.     constraint for a price."  8v)  Another approach is Fourier-Motzkin
  638.     Elimination (article by Danztig and Eaves in the Journal of
  639.     Combinatorial Theory (A) 14, 288-297 (1973).  A software system
  640.     called ANALYZE was developed by Harvey Greenberg to provide
  641.     computer-assisted analysis, including rule-based intelligence;
  642.     for further information about this code, and a bibliography of more
  643.     than 400 references on the subject of model analysis, contact
  644.     Greenberg at HGREENBERG@cudnvr.denver.colorado.edu.  A system based
  645.     on the MINOS solver, called MINOS(IIS), available from John
  646.     Chinneck (chinneck@sce.carleton.ca), can also be used to identify
  647.     a so-called Irreducible Infeasible Subset.  As a final comment,
  648.     commercial codes sometimes have built-in features to help.
  649.  
  650. Q:  I want to know the specific constraints that contradict each other.
  651. A:  This may not be a well posed problem.  If by this you mean you want
  652.     to find the minimal set of constraints that should be removed to
  653.     restore feasibility, this can be modeled as an Integer LP (which
  654.     means, it's potentially a harder problem than the underlying LP
  655.     itself). Start with a Goal Programming approach as outlined above,
  656.     and introduce some 0-1 variables to turn the slacks off or on.
  657.     Then minimize on the sum of these 0-1 variables.  An article
  658.     covering another approach to this question is by Chinneck and
  659.     Dravnieks in the Spring 1991 ORSA Journal on Computing (vol 3,
  660.     number 2).
  661.  
  662. Q:  I just want to know whether or not a feasible solution *exists*.
  663. A:  From the standpoint of computational complexity, finding out if a
  664.     model has a feasible solution is essentially as hard as finding the
  665.     optimal LP solution, within a factor of 2 on average, in terms of
  666.     effort in the Simplex Method.  There are no shortcuts in general,
  667.     unless you know something useful about your model's structure
  668.     (e.g., if you are solving some form of a transportation problem,
  669.     you may be able to assure feasibility by checking that the sources
  670.     add up to at least as great a number as the sum of the
  671.     destinations).
  672.  
  673. Q:  I have an LP, except it's got several objective functions.
  674. A:  Fundamental to the class of Multiple Criteria models is that there
  675.     may no longer be the concept of a unique solution.  I am unaware of
  676.     any public domain code to approach such problems, though I have
  677.     seen a reference to MATLAB's Optimization Toolbox.  Approaches that
  678.     have worked are:
  679.     - Goal Programming (treat the objectives as constraints with costed
  680.       slacks), or, almost equivalently, form a composite function from
  681.       the given objective functions;
  682.     - Pareto preference analysis (essentially brute force examination);
  683.     - Put your objective functions in priority order, optimize on one
  684.       objective, then change it to a constraint fixed at the optimal
  685.       value (perhaps subject to a small tolerance), and repeat with the
  686.       next function.
  687.     There is a section on this whole topic in Reference [1].  As a
  688.     final piece of advice, if you can cast your model in terms of
  689.     physical realities, or dollars and cents, sometimes the multiple
  690.     objectives disappear!  8v)
  691.  
  692. Q:  I have an LP that has large almost-independent matrix blocks that
  693.     are linked by a few constraints.  Can I take advantage of this?
  694. A:  In theory, yes.  See section 6.2 in Reference [1] for a discussion
  695.     of Dantzig-Wolfe decomposition.  I am told that the commercial code
  696.     OSL has features to assist in doing this.  With any other code,
  697.     you'll have to create your own framework and then call the LP
  698.     solver to solve the subproblems.  The folklore is that generally
  699.     such schemes take a long time to converge so that they're slower
  700.     than just solving the model as a whole, although research
  701.     continues.  For now my advice, unless you are using OSL or your
  702.     model is so huge that a good solver can't fit it in memory, is to
  703.     not bother decomposing it.  It's probably more cost effective to
  704.     upgrade your solver, if the algorithm is limiting you, than to
  705.     invest your time; but I suppose that's an underlying theme in a lot
  706.     of my advice. 8v)
  707.  
  708. Q:  I need to find all integer points in a polytope.
  709. A:  There is no known way of doing this efficiently (i.e., with an
  710.     algorithm that grows only polynomially with the problem size).  For
  711.     small models, it may be practical to find your answer by complete
  712.     enumeration.  A related question is how to find all the vertices of
  713.     an LP, with the same pessimistic answer.  [Schrijver] is said to
  714.     discuss this.  Two people mentioned on the net, said to be working
  715.     on code for this, are Dick Helgason (helgason@seas.smu.edu) and
  716.     Betty Hickman (hickman@odin.unomaha.edu).
  717.  
  718. Q:  Are there any parallel LP codes?
  719. A:  IBM has announced a parallel Branch and Bound capability in their
  720.     package OSL, for use on clusters of workstations.  "This is real,
  721.     live commercial software, not a freebie. Contact
  722.     forrest@watson.ibm.com".  Jeffrey Horn (horn@cs.wisc.edu) recently
  723.     compiled a bibliography of papers relating to research on parallel
  724.     B&B.  There is an annotated bibliography of parallel methods in
  725.     Operations Research in general, in Vol 1 (1), 1989 of the ORSA
  726.     Journal on Computing, although by now it might be a little out of
  727.     date.  I'm not aware of any implementations (beyond the "toy"
  728.     level) of general sparse Simplex or interior-point solvers on
  729.     parallel machines.  If your particular model is a good candidate
  730.     for decomposition (see topic, above) then parallelism could be very
  731.     useful, but you'll have to implement it yourself.
  732.  
  733. Q:  I am trying to solve a Traveling Salesman Problem ...
  734. A:  TSP is a famously hard problem that has attracted many of the best
  735.     minds in the field.  Look at the bibliography in the Integer
  736.     Programming section of Reference [1], particularly the ones with
  737.     the names Groetschel and/or Padberg in them.  Solving for a proved
  738.     optimum is combinatorial in nature.  There are some heuristics for
  739.     getting a "good" solution; see the article by Lin and Kernighan in
  740.     Operations Research, Vol 21 (1973), pp 498-516.  I don't believe
  741.     there are any commercial products to solve this problem.  [Syslo]
  742.     contains some algorithms and Pascal code.
  743.  
  744. Q:  I need to do post-optimal analysis.
  745. A:  Many commercial LP codes have features to do this.  Also called
  746.     Ranging or Sensitivity Analysis, it gives information about how the
  747.     coefficients in the problem could change without affecting the
  748.     nature of the solution.  Most LP textbooks, such as Reference [1],
  749.     describe this.  Unfortunately, all this theory applies only to LP.
  750.  
  751.     For a MIP model with both integer and continuous variables, you
  752.     could get a limited amount of information by fixing the integer
  753.     variables at their optimal values, resolving the model as an LP,
  754.     and doing standard post-optimal analyses on the remaining
  755.     continuous variables; but this tells you nothing about the integer
  756.     variables, which presumably are the ones of interest.  Another MIP
  757.     approach would be to choose the coefficients of your model that are
  758.     of the most interest, and generate "scenarios" using values within
  759.     a stated range created by a random number generator.  Perhaps five
  760.     or ten scenarios would be sufficient; you would solve each of them,
  761.     and by some means compare, contrast, or average the answers that
  762.     are obtained.  Noting patterns in the solutions, for instance, may
  763.     give you an idea of what solutions might be most stable.  A third
  764.     approach would be to consider a goal-programming formulation;
  765.     perhaps your desire to see post-optimal analysis is an indication
  766.     that some important aspect is missing from your model.
  767.  
  768. Q:  Some versions of the Simplex algorithm require as input a vertex.
  769.     Do all LP codes require a starting vertex?
  770. A:  No.  You just have to give an LP code the constraints and the
  771.     objective function, and it will construct the vertices for you.
  772.     Most codes go through a so-called two phase method, wherein the
  773.     code first looks for a feasible solution, and then works on getting
  774.     an optimal solution.  The first phase can begin anywhere, such as
  775.     with all the variables at zero (though commercial codes typically
  776.     have a so-called "crash" algorithm to pick a better starting
  777.     point).  So, no, you don't have to give a code a starting point.
  778.     On the other hand, it is not uncommon to do so, because it can
  779.     speed up the solution time tremendously.  Commercial codes usually
  780.     allow you to do this (they call it a "basis", though that's a loose
  781.     usage of a specific linear algebra concept); free codes generally
  782.     don't.  You'd normally want to bother with a starting basis only
  783.     when solving families of related and difficult LP's (i.e., in some
  784.     sort of production mode).
  785.  
  786. -----------------------------------------------------------------------
  787.  
  788. Q7.  "What references are there in this field?"
  789.  
  790. A:  What follows here is an idiosyncratic list, a few books that I like
  791. or have been recommended on the net.  I have *not* reviewed them all.
  792.  
  793. Regarding the common question of the choice of textbook for a college
  794. LP course, it's difficult to give a blanket answer because of the
  795. variety of topics that can be emphasized: brief overview of algorithms,
  796. deeper study of algorithms, theorems and proofs, complexity theory,
  797. efficient linear algebra, modeling techniques, solution analysis, and
  798. so on.  An unscientific poll of ORCS-L mailing list readers uncovered a
  799. consensus that [Chvatal] was in most ways pretty good, at least for an
  800. algorithmically oriented class.  For a class in modeling, a book about
  801. a commercial code (LINDO, AMPL, GAMS are suggested) would be useful,
  802. especially if the students are going to use such a code; and I have
  803. always had a fondness for [Williams].  I have marked with an arrow
  804. ("->") books that received positive mention in this poll (I included
  805. my own votes too  8v) ).
  806.  
  807. General reference  [1]
  808. -  Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland,
  809.    1989.  (Very broad-reaching, with large bibliography.  Good
  810.    reference; it's the place I tend to look first.  Expensive, and
  811.    tough reading for beginners.)
  812.  
  813. LP textbooks
  814. -> Bazaraa, Jarvis and Sherali.  Linear Programming and Network Flows.
  815.    (Grad level.)
  816. -> Chvatal, Linear Programming, Freeman, 1983.  (Undergrad or grad.)
  817. -> Daellenbach and Bell, A User's Guide to LP.  (Good for engineers,
  818.    but may be out of print.)
  819. -> Ecker & Kupferschmid, Introduction to Operations Research.
  820. -  Luenberger, Introduction to Linear and Nonlinear Programming,
  821.    Addison Wesley, 1984.  (Updated version of an old standby.)
  822. -> Murtagh, B., Advanced Linear Programming, McGraw-Hill, 1981.  (Good
  823.    one after you've read an introductory text.)
  824. -  Murty, K., Linear and Combinatorial Programming.
  825. -> Schrijver, A., Theory of Linear and Integer Programming, Wiley,
  826.    1986.  (Advanced)
  827. -> Taha, H., Operations Research: An Introduction, 1987.
  828. -> Thie, P.R., An Introduction to Linear Programming and Game Theory,
  829.    Wiley, 1988.
  830. -> Williams, H.P., Model Building in Mathematical Programming, Wiley
  831.    1985.  (Little on algorithms, but excellent for learning what makes
  832.    a good model.)
  833.  
  834. Interior Point LP (popularly but imprecisely called "Karmarkar")
  835. (There is also a bibliography (with over 1300 entries!?!) obtainable by
  836. mailing to "netlib@ornl.gov" and saying "send intbib.bib from bib".)
  837. -> Fang and Puthenpura, Linear Optimization and Extensions.  (Grad
  838.    level textbook, also contains some Simplex and Ellipsoid.  I heard
  839.    mixed opinions on this one.)
  840. -  Lustig, Marsten & Shanno, "Interior Point Methods for Linear
  841.    Programming - Computational State of the Art", to appear in ORSA
  842.    Journal on Computing, early 1994.  (Available as a tech report from
  843.    shanno@dantzig.rutgers.edu as RUTCOR Report RRR 41-92.)
  844. -  Marsten, et al., "Interior Point Methods for Linear Programming",
  845.    Interfaces, pp 105-116, July-August 1990.  (Introductory article,
  846.    written by authors of a good commercial code, article superseded
  847.    by [Lustig] when it appears.)
  848.  
  849. Documentation for commercial codes
  850. -> Brooke, Kendrick & Meeraus, GAMS: A Users' Guide, The Scientific
  851.    Press, 1988.
  852. -> Fourer, Gay & Kernighan, AMPL: A Modeling Language for Mathematical
  853.    Programming, The Scientific Press, 1992.
  854. -> Greenberg, H.J., Modeling by Object-Driven Linear Elemental
  855.    Relations: A User's Guide for MODLER, Kluwer Academic Publishers,
  856.    1993.
  857. -> Schrage, L., LINDO: An Optimization Modeling System, The Scientific
  858.    Press, 1991.
  859.  
  860. Books containing source code
  861.  
  862. -  Arbel, Ami, Exploring Interior-Point Linear Programming, MIT Press,
  863.    1993.  (New, I have no information about the quality of this book.
  864.    Supposed to include IBM PC software.)
  865. -  Best and Ritter, Linear Programming: active set analysis and
  866.    computer programs, Prentice-Hall, 1985.
  867. -  Bertsekas, D.P., Linear Network Optimization: Algorithms and Codes,
  868.    MIT Press, 1991.
  869. -  Bunday and Garside, Linear Programming in Pascal, Edward Arnold
  870.    Publishers, 1987.
  871. -  Bunday, Linear Programming in Basic (presumably the same publisher).
  872. -  Kennington & Helgason, Algorithms for Network Programming, Wiley,
  873.    1980.  (A special case of LP; contains Fortran source code.)
  874. -  Press, Flannery, Teukolsky & Vetterling , Numerical Recipes,
  875.    Cambridge, 1986.    (Comment: use their LP code with care.)
  876. -  Syslo, Deo & Kowalik, Discrete Optimization Algorithms with Pascal
  877.    Programs, Prentice-Hall (1983).  (Contains code for 28 algorithms
  878.    such as Revised Simplex, MIP, networks.)
  879.  
  880. Other publications
  881. -  Ahuja, Magnanti & Orlin, Network Flows, Prentice Hall, 1993.
  882. -  Balas, E. and Martin, C., "Pivot And Complement: A Heuristic For 0-1
  883.    Programming Problems", Management Science, 1980, Vol 26, pp 86-96.
  884. -  Bondy & Murty, Graph Theory with Applications.
  885. -  Forsythe, Malcolm & Moler, Computer Methods for Mathematical
  886.    Computations, Prentice-Hall.
  887. -> Gill, Murray and Wright, Numerical Linear Algebra and Optimization,
  888.    Addison-Wesley, 1991.
  889. -  Greenberg, H.J., A Computer-Assisted Analysis System for
  890.    Mathematical Programming Models and Solutions: A User's Guide for
  891.    ANALYZE, Kluwer Academic Publishers, 1993.
  892. -  Lawler, Lenstra, et al, The Traveling Salesman Problem, Wiley, 1985.
  893. -  Murty, Network Programming, Prentice Hall, 1992.
  894. -  Reeves, C.R., ed., Modern Heuristic Techniques for Combinatorial
  895.    Problems, Halsted Press (Wiley).  (Contains chapters on tabu search,
  896.    simulated annealing, genetic algorithms, neural nets, and Lagrangean
  897.    relaxation.)
  898.  
  899. -----------------------------------------------------------------------
  900.  
  901. Q8.  "How do I access the Netlib server?"
  902.  
  903. A:  If you have ftp access, you can try "ftp research.att.com", using
  904. "netlib" as the Name, and your email address as the Password.  Do a
  905. "cd <dir>" where <dir> is whatever directory was mentioned, and look
  906. around, then do a "get <filename>" on anything that seems interesting.
  907. There often will be a "README" file, which you would want to look at
  908. first.  Alternatively, you can reach an e-mail server via
  909. "netlib@ornl.gov", to which you can send a message saying "send index
  910. from <dir>"; follow the instructions you receive.
  911.  
  912. -----------------------------------------------------------------------
  913.  
  914. Q9.  "Who maintains this FAQ list?"
  915.  
  916. A:  John W. Gregory      jwg@cray.com          612-683-3673
  917.     Applications Dept.   Cray Research, Inc.   Eagan, MN 55121 USA
  918.  
  919. I suppose I should say something here to the effect that "the material
  920. in this document does not reflect any official position taken by Cray
  921. Research, Inc."  Also, "use at your own risk", "no endorsement of
  922. products mentioned", etc., etc.  "IMHO"s are implicit throughout.
  923.  
  924. In compiling this information, I have drawn on my own knowledge of the
  925. field, plus information from contributors to Usenet groups and the
  926. ORCS-L mailing list.  I give my thanks to all those who have offered
  927. advice and support.  I've tried to keep my own biases (primarily,
  928. toward the high end of computing) from dominating what I write here,
  929. and other viewpoints that I've missed are welcome.  Suggestions,
  930. corrections, topics you'd like to see covered, and additional material
  931. (particularly on NLP) are solicited.
  932.  
  933. Copies of this FAQ list may be made freely, as long as it is
  934. distributed at no charge and with the date of last update and this
  935. disclaimer included.  If you wish to cite this FAQ formally (hey,
  936. someone actually asked me this), you may use:
  937.   Gregory, John W. (1993) "Linear Programming FAQ", Usenet
  938.   sci.answers.  Available via anonymous ftp from rtfm.mit.edu
  939.   in /pub/usenet/sci.answers/linear-programming-faq
  940.  
  941. There's a mail server on that machine, so if you don't have ftp
  942. privileges, you can send an e-mail message to
  943. mail-server@rtfm.mit.edu containing:
  944.     send usenet/sci.answers/linear-programming-faq
  945. as the body of the message.
  946.  
  947. -----------------------------------------------------------------------
  948. END linear-programming-faq
  949.