LP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES) NAME lp_solve - Solve (mixed integer) linear programming prob- lem. SYNOPSIS lp_solve [option]* "<" 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 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 solu- tion is found. INTERRUPT In order to make it possible to get useful solutions for a mixed integer problem which takes too long to finish com- pletely, the "interrupt" signal (kill -INT, ^C for many peo- ple) 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 ter- minate the program, use a different signal, like KILL. Printed 6/17/92 1 LP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES) INPUT SYNTAX The input syntax is a set of algebraic expressions and "int" declarations in the following order: + * where: - is a linear combination of variables, ending with a semicolon. - is a linear combination of variables and con- stants, 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: "<" "<=" "=" ">" ">=". - is of the form: "int" + ";" 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. SEE ALSO The implementation of the simplex kernel was mainly based on: W. Orchard-Hays: "Advanced Linear Programming Computing Printed 6/17/92 2 LP_SOLVE(1ES) UNIX Programmer's Manual LP_SOLVE(1ES) Techniques", McGrawhill 1968 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. Printed 6/17/92 3