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)