home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / utility / 650 / lpsolve / lp_solve.man < prev    next >
Encoding:
Text File  |  1992-12-17  |  4.7 KB  |  198 lines
  1.  
  2.  
  3. LP_SOLVE(1ES)       UNIX Programmer's Manual        LP_SOLVE(1ES)
  4.  
  5.  
  6.  
  7. NAME
  8.      lp_solve  - Solve (mixed integer) linear programming prob-
  9.      lem.
  10.  
  11. SYNOPSIS
  12.      lp_solve [option]* "<" <input-file>
  13.  
  14. OPTIONS
  15.      -v          Verbose mode
  16.  
  17.      -h          Help mode, prints the usage
  18.  
  19.      -d          Debug mode, all intermediate results are
  20.                  printed, and the branch-and-bound decissions in
  21.                  case of (mixed) integer problems.
  22.  
  23.      -b <bound>  Specify a lower limit for the value of the
  24.                  objective function to the program. Only useful
  25.                  for (mixed) integer problems.  If close enough,
  26.                  may speed up the calculations.
  27.  
  28.      -i          Print all intermediate valid solutions. Can give
  29.                  you useful solutions even if the total run time
  30.                  is too long.  Only useful for (mixed) integer
  31.                  problems.
  32.  
  33. DESCRIPTION
  34.      The linear programming problem can be formulated as: Solve
  35.      A.x >= V1, with V2.x maximal. A is a matrix, x a vector of
  36.      variables, V1 a vector called the right hand side, and V2 a
  37.      vector specifying the objective function.
  38.      Any of the variables may be specified integer.
  39.      This program solves problems of this kind. It is slightly
  40.      more general than the above problem, in that every row of A
  41.      (specifying one equation) can have its own (un)equality, <=,
  42.      >= or =. Also there is a possibility to specify bounds and
  43.      ranges for individual variables (which could also be done in
  44.      A of course). The result specifies values for all variables.
  45.      Uses a 'Simplex' algorithm and sparse matrix methods, for
  46.      pure LP problems.  If one or more of the variables is
  47.      declared integer, the Simplex algorithm is iterated with a
  48.      branch and bound algorithm, until the desired optimal solu-
  49.      tion is found.
  50.  
  51. INTERRUPT
  52.      In order to make it possible to get useful solutions for a
  53.      mixed integer problem which takes too long to finish com-
  54.      pletely, the "interrupt" signal (kill -INT, ^C for many peo-
  55.      ple) will not terminate the program, but print the best
  56.      valid solution found sofar. If you see all zeros, it implies
  57.      that no valid solution has been found yet. To really ter-
  58.      minate the program, use a different signal, like KILL.
  59.  
  60.  
  61.  
  62. Printed 6/17/92                                                 1
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. LP_SOLVE(1ES)       UNIX Programmer's Manual        LP_SOLVE(1ES)
  70.  
  71.  
  72.  
  73. INPUT SYNTAX
  74.      The input syntax is a set of algebraic expressions and "int"
  75.      declarations in the following order:
  76.  
  77.      <objective function>
  78.      <constraint>+
  79.      <declaration>*
  80.  
  81.      where:
  82.  
  83.      - <objective function> is a linear combination of variables,
  84.        ending with a semicolon.
  85.  
  86.      - <constraint> is a linear combination of variables and con-
  87.        stants, followed by a relational operator, followed again
  88.        by a linear combination of variables and constants, ending
  89.        with a semicolon. The relational operator can be any of
  90.        the following: "<" "<=" "=" ">" ">=".
  91.  
  92.      - <declaration> is of the form: "int" <var>+ ";" Commas are
  93.        allowed between variables.
  94.  
  95.        So, the simplest linear problem consists of an objective
  96.        function and 1 constraint.
  97.  
  98. EXAMPLE
  99.      The simple problem:
  100.  
  101.      x1 >= 1
  102.      x2 >= 1
  103.      minimise x1 + x2 (= maximise -(x1 + x2)), with x1 integer
  104.  
  105.      can be written as follows:
  106.  
  107.      -x1 + -x2;
  108.      x1 > 1;
  109.      x2 > 1;
  110.      int x1;
  111.  
  112.      The correct result for (x1, x2) is of course (1, 1).
  113.  
  114. BUGS
  115.      Due to the implementation, bounds (constraints on just one
  116.      variable), do not enter into the A-matrix. Therefore,
  117.      extremely simple problems with only bounds sometimes cannot
  118.      be solved, because they define the empty problem. Real-life
  119.      examples probably never have this property.
  120.  
  121. SEE ALSO
  122.      The implementation of the simplex kernel was mainly based
  123.      on:
  124.      W. Orchard-Hays: "Advanced Linear Programming Computing
  125.  
  126.  
  127.  
  128. Printed 6/17/92                                                 2
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135. LP_SOLVE(1ES)       UNIX Programmer's Manual        LP_SOLVE(1ES)
  136.  
  137.  
  138.  
  139.      Techniques", McGrawhill 1968
  140.  
  141. CONTRIBUTED BY
  142.      M.R.C.M. Berkelaar
  143.      Eindhoven University of Technology
  144.      Design Automation Section
  145.      P.O. Box 513
  146.      NL-5600 MB Eindhoven, The Netherlands
  147.      phone ...-31-40-473345
  148.      E-mail: michel@es.ele.tue.nl
  149.  
  150. STATUS
  151.      Use at own risk. Bug reports are welcome, as well as succes
  152.      stories.
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194. Printed 6/17/92                                                 3
  195.  
  196.  
  197.  
  198.