


 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))                                                 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))

9


 NNNNAAAAMMMMEEEE
      lp_solve  - Solve (mixed integer) linear programming problem.

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

 OOOOPPPPTTTTIIIIOOOONNNNSSSS
      -v          Verbose mode

      -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.

 DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
      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


9                                    - 1 -      Formatted:  November 16, 1993






 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))                                                 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))

9


      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.

 IIIINNNNTTTTEEEERRRRRRRRUUUUPPPPTTTT
      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.

 IIIINNNNPPPPUUUUTTTT SSSSYYYYNNNNTTTTAAAAXXXX
      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 "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.

 EEEEXXXXAAAAMMMMPPPPLLLLEEEE
      The simple problem:
9


                                    - 2 -      Formatted:  November 16, 1993






 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))                                                 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))

9


      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).

 BBBBUUUUGGGGSSSS
      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 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


9                                    - 3 -      Formatted:  November 16, 1993






 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))                                                 LLLLPPPP____SSSSOOOOLLLLVVVVEEEE((((1111EEEESSSS))))

9


           "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.

 SSSSEEEEEEEE AAAALLLLSSSSOOOO
      The implementation of the simplex kernel was mainly based on:
      W. Orchard-Hays: "Advanced Linear Programming Computing Techniques",
      McGraw-Hill 1968

 CCCCOOOONNNNTTTTRRRRIIIIBBBBUUUUTTTTEEEEDDDD BBBBYYYY
      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

 SSSSTTTTAAAATTTTUUUUSSSS
      Use at own risk. Bug reports are welcome, as well as success stories.

























9


                                    - 4 -      Formatted:  November 16, 1993



