LP_SOLVE

Section: Misc. Reference Manual Pages (1ES)
Index Return to Main Contents

NAME

lp_solve - Solve (mixed integer) linear programming problem.

SYNOPSIS

lp_solve [option]* "<" <input-file>

OPTIONS

-v: Verbose mode
-h: Help mode, prints the usage
-d: Debug mode, all intermediate results are printed, and the branch-and-bound decissions in case of (mixed) integer problems.
-b <bound>: Specify a lower 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.
-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.

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 variables, V1 a vector called the right hand side, and V2 a vector specifying the objective function.
Any of the variables may be specified 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 equation) can have its own (un)equality, <=, >= or =. Also there is a possibility to specify bounds and ranges for individual variables (which could also be done in A of course). 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, but print the best valid solution found sofar. 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.

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.
-: <constraint> is 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: "<" "<=" "=" ">" ">=".
-: <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
minimise x1 + x2 (= maximise -(x1 + x2)), with x1 integer

can be written as follows:

-x1 + -x2;
x1 > 1;
x2 > 1;
int x1;

The correct result for (x1, x2) is of course (1, 1).

BUGS

Due to the implementation, bounds (constraints on just one variable), do not enter into the A-matrix. Therefore, extremely simple problems with only bounds sometimes cannot be solved, because they define the empty problem. Real-life examples probably never have this property.

CONTRIBUTED BY

M.R.C.M. Berkelaar
Eindhoven University of Technology
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 succes stories.

This document was created by man2html, using the manual pages.
Time: 21:59:37 GMT, January 07, 2025