LP_SOLVE(1ES) LP_SOLVE(1ES)
NAME
lp_solve - Solve (mixed integer) linear programming
problem.
SYNOPSIS
lp_solve [option]* "<" <input-file>
OPTIONS
-v Verbose mode. Among other things, shows all the
pivots.
-h Help mode, prints the usage.
-d Debug mode, all intermediate results are
printed, and the branch-and-bound decisions in
case of (mixed) integer problems.
-p Print the values of the dual variables as well
in the result. They are named r_1 until r_XXXXX
unless specified by the user. Note that bounds
(constraints on just one variable) are not
considered real constraints, and are not given a
row in the matrix, and are therefore not printed
here.
-b <bound> Specify an upper (when minimizing) or lower
(when maximizing) limit for the value of the
objective function to the program. Only useful
for (mixed) integer problems. If close enough,
may speed up the calculations. The same result
can be obtained by adding an extra constraint to
the problem.
-c When branching in MILP problems, take the
ceiling of the selected non-integer variable
first instead of the floor. This can influence
the speed of MILP problems.
-e <value> Specify the accuracy with which it is checked
whether the value of a variable is really
integer. <value> must be between 0 and 0.5.
Default value is 1e-6 and should be OK for most
applications. Of course only useful for MILP
problems.
-i Print all intermediate valid solutions. Can give
you useful solutions even if the total run time
is too long. Only useful for (mixed) integer
problems.
-scale <value>
Scale all coefficients by <value> while solving.
Page 1 (printed 11/16/94)
LP_SOLVE(1ES) LP_SOLVE(1ES)
This is useful if you have mainly very large or
very small coefficients, and are running into
numerical problems because of this. For a
problem with both large and small coefficients
the -autoscale option might be more appropriate.
-autoscale Both rows and columns are scaled according to
the geometric mean of the coefficients on them
before solving. This might improve the numerical
stability of your problem.
DESCRIPTION
The linear programming problem can be formulated as: Solve
A.x >= V1, with V2.x maximal. A is a matrix, x a vector of
(nonnegative) variables, V1 a vector called the right hand
side, and V2 a vector specifying the objective function.
Any number of the variables may be specified to be of type
integer.
This program solves problems of this kind. It is slightly
more general than the above problem, in that every row of A
(specifying one constraint) can have its own (in)equality,
<=, >= or =. The result specifies values for all variables.
Uses a 'Simplex' algorithm and sparse matrix methods, for
pure LP problems. If one or more of the variables is
declared integer, the Simplex algorithm is iterated with a
branch and bound algorithm, until the desired optimal
solution is found.
INTERRUPT
In order to make it possible to get useful solutions for a
mixed integer problem which takes too long to finish
completely, the "interrupt" signal (kill -INT, ^C for many
people) will not terminate the program when it is solving a
MILP problem, but rather print the best valid solution found
so far. This feature is not useful and thus disabled when
you are solving a pure LP problem. If you see all zeros, it
implies that no valid solution has been found yet. To really
terminate the program, use a different signal, like KILL.
The "-i" option will print all intermediate valid solutions.
INPUT SYNTAX
The input syntax is a set of algebraic expressions and "int"
declarations in the following order:
<objective function>
<constraint>+
<declaration>*
where:
- <objective function> is a linear combination of variables,
ending with a semicolon, optionally preceded by "max: " or
Page 2 (printed 11/16/94)
LP_SOLVE(1ES) LP_SOLVE(1ES)
"min: " to indicate whether you want it to be minimized or
maximized. The case is not important, "Max:" or "MAX:"
will work as well. Maximization is the default.
- <constraint> is an optional constraint name followed by a
colon plus a linear combination of variables and
constants, followed by a relational operator, followed
again by a linear combination of variables and constants,
ending with a semicolon. The relational operator can be
any of the following: "<" "<=" "=" ">" ">=". There
is no semantic difference between "<" and "<=" nor
between ">" and ">=" (even for integer variables!).
- <declaration> is of the form: "int" <var>+ ";"
Commas are allowed between variables.
So, the simplest linear problem consists of an objective
function and 1 constraint.
EXAMPLE
The simple problem:
x1 >= 1
x2 >= 1
x1 + x2 >= 2
minimize x1 + x2 (= maximize -(x1 + x2)), with x1 integer
can be written as follows:
-x1 + -x2;
(or min: x1 + x2;)
x1 > 1;
x2 > 1;
x1 + x2 > 2;
int x1;
The correct result for (x1, x2) is of course (1, 1).
BUGS
Specifying a constraint name for a bound (constraints on
just single variables) does not have an effect: they are not
stored inside the main matrix and are not assigned a dual
variable. I am not going to change this behavior.
There are a few situations where lp_solve is known to give
wrong "No solutions".
- The problem consists entirely of constraints on just
single variables (so-called "bounds", like x < 1; ) and
no constraint with more than 1 variable (like x + 3 y >
17; ). This leaves lp_solve with an empty problem
matrix, as bounds are not stored in the main matrix. No
real-life examples should be of this form, so I am not
Page 3 (printed 11/16/94)
LP_SOLVE(1ES) LP_SOLVE(1ES)
really chasing this problem.
- There are variables in the objective function which do
not occur in a constraint with more than 1 variable,
but just in a bound. This is a bug in lp_solve which I
would like to repair, but I have sofar been
unsuccessful. Anyway, this can easily be avoided, as
the value of a variable just occurring in a bound and
the objective function is trivially clear from the
beginning. You can also just constrain the value of
the entire objective function in the first constraint
by a number which you know will not constrict your LP
problem.
- Many people forget that lp_solve can only handle
POSITIVE values for the variables.
- Sometimes problems are numerically unstable, and the
unavoidable rounding errors inside lp_solve will cause
wrong results (usually aborts or wrong "no soution"
messages). It is very hard to give general solutions to
this problem, but try to keep all values in your
problem in the order of magnitude of 1 by proper
scaling. lp_solve does not do do any scaling itself.
Almost parallel constraints are also not very good for
numerical stability. Use "lp_solve -v" and observe the
values of the pivots to see if there are any
dangerously large or low numbers there.
Building lp_solve with long doubles (see the Makefile)
can help to increase numerical stability, but will also
increase the run time considerably.
You can consult the author as well if you encounter
numerical problems, but please remember that it is very
easy to formulate an infeasible LP problem, so be sure
there is a solution.
SEE ALSO
The implementation of the simplex kernel was mainly based
on:
W. Orchard-Hays: "Advanced Linear Programming Computing
Techniques", McGraw-Hill 1968
The mixed integer branch and bound part was inspired by:
section 6.4 of "An Introduction to Linear Programming and
Game Theory" by Paul R. Thie, second edition published by
John Wiley and Sons in 1988.
This book refers to:
Dakin, R.J., "A Tree Search Algorithm for MILP Problems",
Comput. J., 8 (1965) pp. 250-255
CONTRIBUTED BY
M.R.C.M. Berkelaar
Eindhoven University of Technology
Page 4 (printed 11/16/94)
LP_SOLVE(1ES) LP_SOLVE(1ES)
Design Automation Section
P.O. Box 513
NL-5600 MB Eindhoven, The Netherlands
phone ...-31-40-473345
E-mail: michel@es.ele.tue.nl
STATUS
Use at own risk. Bug reports are welcome, as well as success
stories.
Page 5 (printed 11/16/94)