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