🚀 go-pugleaf

In response to the steady trickle of questions about Linear Programming 
(LP) and related topics, I am posting a first draft of a FAQ list.  If 
it proves worthwhile (or at least, if I don't get flamed tooooo badly), 
I may re-post it to this newsgroup every month or two, or as repeat 
questions arise.  

I suppose I should say something here to the effect that "the material
in this document does not reflect any official position taken by Cray 
Research, Inc."  Also, "use at your own risk", etc., etc.  I probably 
should have put in more "IMHO"s, but it's hard to know where to stop. 
(I probably should have put in a few more smilies here and there too, 
to assist the humor impaired.  Be on your toes.  8v) )

I've tried to keep my own biases (primarily, toward the high end of 
computing) from dominating what I write here, and other viewpoints are 
welcome.  Suggestions, corrections, topics you'd like to see covered, 
and additional material are solicited.  Comments to the effect "who 
died and made *you* optimal?" will likely result in you getting stuck 
with maintaining the FAQ instead of me.  8v)


- John Gregory
  LP Specialist
  Applications Department
  Cray Research, Inc.
  jwg@cray.com
  612-683-3673


-------------------------------------------------------------------


                           LP-FAQ  
        (Linear Programming - Frequently Asked Questions)


1.  "What is Linear Programming?"

A:  A linear program (LP) is a problem that can be put into 
the form

    minimize   cx
    subject to Ax=b
                x>=0

where x is the vector to be solved for, A is a matrix of known
coefficients, and c and b are vectors (of proper dimension) of
known coefficients.  The matrix A is generally not square, and 
usually has more columns than rows.  Ax=b is therefore under-
determined, leaving (usually) great latitude in the choice of x
to minimize cx.

Many problems can be put into this form.  For instance, if you
want to maximize instead of minimize, multiply the c vector by
-1.  If you have constraints that are inequalities rather than
equations, you can introduce one new variable ("slack") to each
inequality and treat the augmented row of the matrix as an
equation.

LP problems are usually solved by a technique known as the Simplex 
Method, developed in the 1940's and after.  Briefly stated, this 
method works by taking a sequence of square submatrices of A and 
solving for x, in such a way that successive solutions always 
improve, until a point is reached where no improvement is possible.  
A family of LP algorithms known as Interior Point methods has been 
developed starting in the 1980's, that can be faster for many (but 
so far not all) problems.

LP has a variety of uses, in such areas as petroleum, finance, 
transportation, forestry, and military.

-------------------------------------------------------------------

2.  "Where is there a good code, preferably public domain, to 
solve Linear Programming problems?"

A:  It depends on the difficulty of your models.  LP technology and
computer technology have both made such great leaps that models
that were previously considered "large" are now routinely solved.
Nowadays, models with a few thousand constraints, and several 
thousand variables, can be tackled with a PC.  Good LP codes on 
workstations can often handle models with variables in the tens 
of thousands, or even greater.  It's hard to be specific about
sizes and speed, a priori, due to the wide variation in things like 
model structure and difficulty in factorizing the basis matrices.

There is a recently released public domain code called "lp_solve"
that is available on Usenet in the "comp.sources.reviewed" news-
group.  Its author claims to have solved models with up to 30,000
variables and 50,000 constraints.  My own experience with this
code is not quite so optimistic; still, for someone who isn't
sure just what kind of LP code is needed, it represents a very
reasonable first try, and the price is right.

For MS-DOS PC users, Prof. Timo Salmi at the University of Vaasa
in Finland offers a code called "tslin".  You should be able to 
access it by ftp at garbo.uwasa.fi in directory /pc/ts, or else 
I suggest contacting Prof. Salmi at ts@uwasa.fi.

The consensus is that the LP code published in Numerical Recipes 
is not at all strong, and should be avoided for heavy-duty use.
If your requirement is for a solver that can handle 100-variable
models, it might be OK.

If your models prove to be too difficult for free software to 
handle, then you can consider acquiring a commercial code.  There 
are probably close to 100 such codes on the market. I have my own 
opinions, but for reasons of space, generality and fairness (my wife 
works for one such company), I will not attempt even to list the 
codes I know of here.  Instead I refer you to the annual survey of 
LP software published in "OR/MS Today", a joint publication of ORSA 
(Operations Research Society of America) and TIMS (The Institute of 
Management Science).  I think it's likely that you can find a copy 
of the June, 1992 issue, either through a library, or by contacting 
a member of these two organizations (most universities probably have 
several members among the faculty).  The survey lists almost fifty 
actively marketed products.  This publication also carries advertisements
for many of these products, which may give you additional information
to help make a decision.

There are many considerations in selecting an LP code.  Speed
is important, but LP is complex enough that different codes do
well on different models; you won't find a "Consumer Reports"  8v)
article to say with certainty which code is the fastest.  I usually 
suggest getting benchmark results for your particular type of model 
if speed is paramount to you.  Benchmarking may also help determine
whether a given code has sufficient numerical stability for your
kind of models.

Other questions you should answer: Can you use a stand-alone code, or 
do you need a code that can be used as a callable library, or do you 
require source code?  Do you want the flexibility of a code that runs 
on many platforms and/or operating systems, or do you want code that's 
tuned to your particular hardware architecture (in which case your
hardware vendor may have suggestions)?  Is the choice of algorithm 
(Simplex, Interior Point) important to you?  Do you need an interface 
to a spreadsheet program?  Is the purchase price an overriding concern?  
Is the software offered at an academic discount (assuming you are at a 
university)?  How much hotline support do you think you'll need?  

It may not always be true that "you get what you pay for," but it is 
rare that you get more than you pay for.  8v)   There is usually a 
large difference in LP codes, in performance (speed, numerical 
stability, adaptability to computer architectures) and features, as 
you climb the price scale.

-------------------------------------------------------------------

3.  "Oh, and we also want to solve it as an integer program."

A:  Hmm.  You want
    - Large models
    - Integer solutions
    - Public domain code
Pick one or maybe two of the above.  You can't have all three.  8v)

Integer LP (ILP, a special case of Mixed Integer Programming or MIP) 
models are ones where the answers must not take fractional values.  
It may not be obvious that this is a much, much harder problem than 
ordinary LP, but it is nonetheless true.  You should be prepared to 
solve far smaller ILP models than the corresponding LP model, given 
a certain amount of time you wish to allow (unless you and your model 
happen to be very lucky). There exist models that are considered 
challenging, with mere hundreds of variables. Conversely, some models 
with tens of thousands of variables solve readily.  It all depends.

Although various algorithms for ILP have been studied, most if not
all available general purpose large-scale LP codes use a method called 
"Branch and Bound" to try to find an optimal solution.  In a nutshell, 
B-B solves ILP by solving a sequence of ordinary LP models.  Good codes 
for ILP distinguish themselves more by solving shorter sequences of 
LP's, than by solving the individual LP's faster.  (As a point of 
interest, the Simplex Method currently retains an advantage over the
newer Interior Point methods for solving these sequences.)  Even 
moreso than with regular LP, a costly commercial code may prove its 
value to you if your ILP is difficult.

The public domain code "lp_solve", mentioned above, accepts ILP models,
as do a large proportion of the commercial LP codes in the OR/MS 
Today survey.  The better codes have numerous parameters and options
to give the user control over the solution strategy. Most have the 
capability of stopping before an optimum is proved, printing the best 
answer obtained so far.  For many ILP models, stopping early is a
practical necessity. Fortunately, a solution that has been proven by 
the algorithm to be within, say, 1% of optimality often turns out 
actually to be the true optimum, and the bulk of the computation time 
is spent proving the optimality. For many modeling situations, a near-
optimal solution is acceptable anyway.
 
Since it is often not possible to let the computer work on a problem 
long enough for optimality to be proved (say, because your doctor has 
told you that you have only 70 years to live  8v) ), that opens up a 
broad area of approximate methods, probabilistic methods and heuristics, 
as well as stopping B-B early.  Claims have been made for Genetic 
Algorithms and Simulated Annealing, though (IMHO) these successes have 
been problem dependent and difficult to generalize.  When trying to 
solve a difficult ILP model, it is usually crucial to understand the 
workings of whatever it is you are modeling, and try to find some insight 
that will assist your chosen algorithm to work better.  A related 
observation is that the way you formulate your model can be as important 
as the actual choice of solver.  You should consider getting some 
assistance if this is your first time trying to solve a large (>100 
variable) problem.

-------------------------------------------------------------------

4a.  "I'VE WRITTEN A C00L LP CODE.  HOW CAN I TEST IT?   SIGNED, BIFF"
4b.  "What is MPS format?"

A:  In light of the comments above, I hope your aims are fairly modest,
for there are already a lot of good codes out there.  I hope your code
makes use of sparse matrix techniques, rather than using a tableau
form of the Simplex method, because the latter usually ends up being
numerically unstable and very slow.

If you want to try out your code on some real-world models, there is 
a very nice collection of small-to-medium-size ones on netlib.  If you
have ftp access, you can try "ftp research.att.com", using "netlib"
as the Name, and your email address as the password. Do a "cd lp/data"
and look around. There should be a "readme" file, which you would 
want to look at first.  Alternatively, you can reach an e-mail
server via "netlib@ornl.gov", to which you can send a message saying
"send index from lp/data" and follow the instructions you receive.

The Netlib LP files (after you uncompress them) are in a format called 
MPS, which was named after an early IBM LP product and has emerged as 
a de-facto standard ASCII medium among most of the various commercial 
LP codes.  You will need to write your own reader routine for this, but 
it's not too hard. The main things to know about MPS format are that it 
is column oriented (as opposed to entering the model as equations), and 
everything (variables, rows, etc.) gets a name.  Here is a little sample 
model, explained in more detail below:

NAME          METALS   
ROWS
  N VALUE
  E YIELD
  L FE
  L MN
  L CU
  L MG
  G AL
  L SI
COLUMNS
    BIN1      VALUE       0.03         YIELD           1.
    BIN1      FE          0.15         CU             .03
    BIN1      MN          0.02         MG             .02
    BIN1      AL          0.7          SI             .02
    BIN2      VALUE       0.08         YIELD           1.
    BIN2      FE           .04         CU             .05
    BIN2      MN           .04         MG             .03
    BIN2      AL           .75         SI             .06
    BIN3      VALUE       0.17         YIELD         1.
    BIN3      FE           .02         CU             .08
    BIN3      MN           .01         AL             .8
    BIN3      SI           .08
    BIN4      VALUE       0.12         YIELD         1.
    BIN4      FE           .04         CU             .02
    BIN4      MN           .02         AL             .75
    BIN4      SI          0.12
    BIN5      VALUE       0.15         YIELD         1.
    BIN5      FE           .02         CU             .06
    BIN5      MN           .02         MG             .01
    BIN5      SI           .02         AL             .8
    ALUM      VALUE       0.21         YIELD         1.
    ALUM      FE           .01         CU             .01
    ALUM      AL           .97         SI             .01
    SILCON    VALUE       0.38         YIELD         1.
    SILCON    FE           .03         SI             .97
RHS
    ALOY1     YIELD        2000.       FE              60.
    ALOY1     CU            100.       MN              40.
    ALOY1     MG             30.       AL            1500.
    ALOY1     SI            300.
BOUNDS
 UP PROD1     BIN1            200.00
 UP PROD1     BIN2            750.00
 LO PROD1     BIN3            400.00
 UP PROD1     BIN3            800.00
 LO PROD1     BIN4            100.00
 UP PROD1     BIN4            700.00
 UP PROD1     BIN5           1500.00
ENDATA


MPS is an old format, so it is set up as though you were using
punch cards, and is not free format. Fields start in column 1,
5, 15, 25, 40 and 50.  The NAME card can be anything you want.
The ROWS section defines the names of all the constraints; 
entries in column 2 or 3 are E for equality rows, L for less-than
( <= ) rows, G for greater-than  ( >= ) rows, and N for non-
constraining rows (the first of which would be interpreted as 
the objective function).

The largest part of the file is in the COLUMNS section, which is 
the place where the entries of the A-matrix are put.  All entries 
for a given column must be placed consecutively, although within 
a column the order of the entries (rows) is irrelevant. Rows not 
mentioned for a column are assumed to have a coefficient of zero.

The RHS section allows one or more right-hand-side vectors to be 
defined; most people don't bother having more than one.  The 
optional BOUNDS section lets you put lower and upper bounds on 
individual variables (no * wildcards, unfortunately), instead of 
having to define extra rows in the matrix.  All the bounds that 
have a given name in column 5 are taken together as a set.  Variables
not mentioned in a BOUNDS set are taken to be non-negative.  There 
is another optional section called RANGES that I won't go into 
here. The final card must be the ENDATA, and yes, it is spelled 
funny.

MPS format is described in more detail in Murtagh's book, listed
below.

For comparison, here is the same model written out in equation 
format.

Minimize
 VALUE: 0.03 BIN1 + 0.08 BIN2 + 0.17 BIN3 + 0.12 BIN4 + 0.15 BIN5 
 + 0.21 ALUM + 0.38 SILCON
Subject To
 YIELD: BIN1 + BIN2 + BIN3 + BIN4 + BIN5 + ALUM + SILCON  = 2000
 FE:    0.15 BIN1 + 0.04 BIN2 + 0.02 BIN3 + 0.04 BIN4 + 0.02 BIN5 
        + 0.01 ALUM + 0.03 SILCON <= 60
 MN:    0.02 BIN1 + 0.04 BIN2 + 0.01 BIN3 + 0.02 BIN4 + 0.02 BIN5 
        <= 40
 CU:    0.03 BIN1 + 0.05 BIN2 + 0.08 BIN3 + 0.02 BIN4 + 0.06 BIN5 
        + 0.01 ALUM <= 100
 MG:    0.02 BIN1 + 0.03 BIN2 + 0.01 BIN5 <= 30
 AL:    0.7 BIN1 + 0.75 BIN2 + 0.8 BIN3 + 0.75 BIN4 + 0.8 BIN5 
        + 0.97 ALUM >= 1500
 SI:    0.02 BIN1 + 0.06 BIN2 + 0.08 BIN3 + 0.12 BIN4 + 0.02 BIN5 
        + 0.01 ALUM + 0.97 SILCON <= 300
and
        0 <= BIN1 <= 200
        0 <= BIN2 <= 750
        400 <= BIN3 <= 800
        100 <= BIN4 <= 700
        0 <= BIN5 <= 1500

-------------------------------------------------------------------

5.  "What software is there for non-linear optimization?"

A:  I don't claim as much expertise in this area, but the question 
is frequent enough to be worth addressing.  If I get enough feedback,
this section might grow large enough to need to be split off as
a separate FAQ list.

Several of the LP codes referenced above have specialized routines, 
particularly for Quadratic Programming (linear constraints with
a quadratic objective function). Many nonlinear problems can be
solved by application of a sequence of QP approximations.

Nonlinear solution techniques can be divided into various categories,
such as unconstrained, linearly constrained, or general.  Here is 
a summary of codes mentioned in newsgroups in the past year, not 
sorted into categories.

NPSOL - Stanford University, Office of Technology Licensing, 415-723-0651.

MINOS - Stanford University, Office of Technology Licensing, 415-723-0651.

NAG Library routine E04UCF.

IMSL routine UMINF and UMIDH.

Harwell Library routine VF04.

Hooke and Jeeves algorithm - reference?

DFPMIN - Numerical Recipes

FSQP -  Contact Andre Tits, andre@src.umd.edu  

CONMIN - Vanderplaats and Associates, Goleta CA

GRG2 - Leon Lasdon, University of Texas, Austin TX

-------------------------------------------------------------------

6.  "What books are there on optimization?"

A:  Too many to count.  Here are a few that I like or have been 
recommended on the net:

Dennis & Schnabel, Numerical Methods for Unconstrained Optimization
and Nonlinear Equations, Prentice Hall.

Fletcher, R., Practical Methods of Optimization, Wiley 1987.

Forsythe, Malcolm & Moler, Computer Methods for Mathematical
Computations, Prentice-Hall.

Gill, Murray & Wright, Practical Optimization, Academic Press.

Kahaner, Moler & Nash, Numerical Methods and Software, Prentice-Hall.

Murtagh, Advanced Linear Programming, McGraw-Hill, 1981.

Williams, H.P., Model Building in Mathematical Programming, Wiley 1985.

-------------------------------------------------------------------