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)