home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 200-299 / ff250.lzh / ASimplex / ASimplex.doc < prev    next >
Text File  |  1989-09-16  |  11KB  |  382 lines
  1.  
  2.                           ASimplex Version 1.5
  3.                           ====================
  4.  
  5.                         THE AMIGA-Simplex-Program
  6.  
  7.                       (c) 07.08.1989 Stefan Foerster
  8.  
  9.  
  10.  
  11. "ASimplex" is placed in the Public Domain. Nevertheless no part of this
  12. program may be sold or used in any commercial program. Private use is free.
  13.  
  14.  
  15. This is version 1.5 of "ASimplex". Its new features are:
  16.  
  17.   o I fixed a bug that caused ASimplex 1.2 to stop after phase I with the
  18.     message "This problem is not solveable" with some linear programs,
  19.     because of numerical instability. This is the main reason of this
  20.     update.
  21.  
  22.   o It is now possible to run ASimplex from CLI.
  23.  
  24.   o ASimplex now uses its own window for I/O.
  25.  
  26.   o Some new/improved ASimplex-commands.
  27.  
  28.  
  29.  
  30. I hope that this release is bug-free and bullet-proof. If it is not or
  31. if you have any suggestions or money that you want to send me, here is
  32. my address:
  33.  
  34.           Stefan Foerster
  35.           Weinbergstr. 29
  36.           8877 Burtenbach
  37.           West-Germany
  38.  
  39.  
  40.  
  41.  
  42. ASimplex is an implementation of the famous simplex-algorithm for solving
  43. linear programs. It was developed as a project in the course "Optimierung I"
  44. held at the university of Augsburg by Prof. Dr. Groetschel. It is written
  45. in C using the Manx Aztec C Compiler V3.6a.
  46.  
  47.  
  48. In general, linear programs are of the form
  49.  
  50.   max dx (or min dx), Ax = a, Bx <= b, Cx >= c, l <= x <= u,
  51.  
  52. where A, B and C are matrices and a,b,c,d,x,l and u are vectors.
  53. dx is called the objective (or cost) function that is to be maximized (or
  54. minimized) subject to the constraints Ax = a, Bx <=b, Cx >=c and l <= x <= u.
  55.  
  56. For example:
  57.  
  58.   min           x1 +   x2 -   x3
  59.  
  60.   subject to    x1 - 4*x2 + 3*x3 <= 6
  61.                 x1 + 2*x2 -   x3 <= 1
  62.                 x1 + 2*x2 +   x3 <= 8
  63.  
  64.                          0 <= x1 <= 1
  65.                          0 <= x2 <= 1
  66.                          0 <= x3 <= 3
  67.  
  68. with
  69.  
  70.       / 1  -4   3 \      / 6 \      / 1 \      / 0 \      / 1 \      / x1 \
  71.   B = | 1   2  -1 |, b = | 1 |, d = | 1 |, u = | 0 |, l = | 1 |, x = | x2 |
  72.       \ 1   2   1 /      \ 8 /      \-1 /      \ 0 /      \ 3 /      \ x3 /
  73.  
  74.  
  75.  
  76.  
  77. Commands of ASimplex:
  78. ---------------------
  79.  
  80.  
  81. HELP
  82.  
  83. HELP lets you see all possible commands.
  84.  
  85.  
  86.  
  87. LOAD <file> [-cGOAL] [-bRHS] [-rRANGE] [-uBOUND] [-m] [-fFILE]
  88.  
  89. With LOAD ASimplex reads the data of a linear program. The data must be
  90. in the standardized MPSX-format (MPSX is a trademark of IBM). A brief
  91. description of this format follows later; now you should only know, that
  92. the data is subdivided into sections and it is possible for some sections
  93. to contain data for different linear programs (e.g. different objective
  94. functions: Data belonging to a certain objective function has a unique
  95. identifier).
  96.  
  97. <file>   The file-name of the file you want to load.
  98.  
  99. -cGOAL   GOAL is the identifier of the objective function you want to use.
  100.          if -cGOAL is not specified there are two possible cases: ASimplex
  101.          uses the objective function it finds (if there is only one) or it
  102.          asks you to choose one.
  103.  
  104. -bRHS    RHS is the identifier of the right hand side you want to use.
  105.          (b in the above example).
  106.  
  107. -rRANGE  RANGE is the identifier of the range you want to use.
  108.  
  109. -uBOUND  BOUND is the identifier of the bounds (l and u in the above
  110.          example).
  111.  
  112. -m       If -m is specified, ASimplex tries to minimize the objective
  113.          functions; otherwise it tries to maximize it. If the global
  114.          setting MINIMIZE is ON (see below), then -m means maximize.
  115.  
  116. -fFILE   If -fFILE is specified, ASimplex writes the result to the file
  117.          "FILE" (FILE could for example be PRT: to get the results to
  118.          the printer).
  119.  
  120.  
  121.  
  122. VERBOSE [N]
  123.  
  124. VERBOSE is a flag that can be ON or OFF. If it is ON, you get further
  125. information what ASimplex currently does. Default is OFF. You can use
  126. an optional integer [N] to print only every Nth iteration.
  127.  
  128.  
  129.  
  130. INVERT [N]
  131.  
  132. ASimplex permanently stores the inverse of a special matrix and updates
  133. it every iteration. This leads to numerical errors. Therefore it is possible
  134. to re-invert this matrix from time to time.
  135. INVERT N sets the invert-frequency to N. Default is 50.
  136. INVERT 0 means no re-inversion.
  137. INVERT displays the current invert-frequency.
  138.  
  139.  
  140.  
  141. PRICE [MIXED|CYCL|STEEP]
  142.  
  143. PRICE sets the pricing-method ASimplex uses to find the pivot-column. I
  144. have implemented two different ones:
  145.  
  146. - cyclic smallest index rule (CYCL): fast but in most cases leads to
  147.   more iterations than the
  148.  
  149. - steepest ascent rule (STEEP)
  150.  
  151. - MIXED is a combination of CYCL and STEEP.
  152.  
  153. MIXED is the default setting.
  154.  
  155.  
  156.  
  157. MINIMIZE
  158.  
  159. MINIMIZE is a flag that can be ON or OFF. If it is ON and no '-m' is
  160. specified in the LOAD command, ASimplex minimizes the cost function,
  161. otherwise it maximizes it. '-m' always means the opposite of the
  162. MINIMIZE flag.
  163.  
  164.  
  165.  
  166. PRIORITY [N]
  167.  
  168. PRIORITY N sets the task-priority of ASimplex to N (0<=N<=20).
  169. PRIORITY gives the current task-priority. Default is 0.
  170.  
  171.  
  172.  
  173. DEFAULT
  174.  
  175. DEFAULT resets everything to its default value.
  176.  
  177.  
  178.  
  179. QUIT
  180.  
  181. Leave ASimplex.
  182.  
  183.  
  184.  
  185.  
  186. The MPSX-format
  187. ---------------
  188.  
  189.  
  190. The data of a linear program is subdivided into sections. The sections are
  191.  
  192.   NAME
  193.   ROWS
  194.   COLUMNS
  195.   RHS
  196.   RANGES
  197.   BOUNDS
  198.   ENDATA
  199.  
  200. where RANGES and BOUNDS are optional.
  201.  
  202.  
  203.  
  204. i)    NAME-section:
  205.       The NAME-section determines the name of the linear program. In the
  206.       above example you could write
  207.  
  208.       NAME example
  209.  
  210.  
  211.  
  212. ii)   ROWS-section:
  213.       You have to give every constraint of the linear program a name. This
  214.       name and the type of the constraint is determined in the ROWS-section.
  215.       The possible types are:
  216.       N   no constraint, objective function
  217.       E   "="   equality
  218.       L   "<="  less than or equal
  219.       G   ">="  greater than or equal
  220.       In the above example you could write:
  221.  
  222.       ROWS
  223.         N goal
  224.         L constr1
  225.         L constr2
  226.         L constr3
  227.  
  228.  
  229.  
  230. iii)  COLUMNS-section:
  231.       The COLUMNS-section determines the variables and the coefficients
  232.       for every variable (in the constraints and in the objective function).
  233.       If a coefficient is not specified, it is assumed to be 0.
  234.       In the above example you could write:
  235.  
  236.       COLUMNS
  237.         x1  goal      1
  238.         x1  constr1   1
  239.         x1  constr2   1
  240.         x1  constr3   1
  241.         x2  goal      1
  242.         x2  constr1   -4
  243.         x2  constr2   2
  244.         x2  constr3   2
  245.         x3  goal      -1
  246.         x3  constr1   3
  247.         x3  constr2   -1
  248.         x3  constr3   1
  249.  
  250.       It is possible to use two fields in one line, e.g.
  251.  
  252.         x1  goal      1     constr1     1
  253.  
  254.  
  255.  
  256. iv)   RHS-section:
  257.       In this section every value of the right hand side is determined.
  258.       If a value is missing it is assumed to be 0. Our example:
  259.  
  260.       RHS
  261.         b   constr1   6     constr2     1
  262.         b   constr3   8
  263.  
  264.       b is the name of this right hand side. If you want to define a second
  265.       right hand side, you could write
  266.  
  267.         b2  constr1   -2    constr2     9
  268.         b2  constr3   3.5
  269.  
  270.       It is possible to use two fields in one line.
  271.  
  272.  
  273.  
  274. v)    RANGES-section:
  275.       Say you have the two constraints      2*x1 + x2  <= 10  and
  276.                                             2*x1 + x2  >= 8   .
  277.       You could write them in the form 8 <= 2*x1 + x2  <= 10  .
  278.       Then it is possible to define only one constraint in the ROWS-section
  279.       and define a range (a left hand side) in the RANGES-section, e.g.:
  280.  
  281.       ROWS
  282.         l constr
  283.         ...
  284.       RHS
  285.         b constr  10
  286.         ...
  287.       RANGES
  288.         r constr  2   ( IMPORTANT: not 8, but 2 = 10-8 !!! )
  289.  
  290.       r is the name of the range. It is possible to have several different
  291.       ranges in one RANGES-section and to specify two fields in one line.
  292.       The RANGES-section is optional.
  293.  
  294.  
  295.  
  296. vi)   BOUNDS-section:
  297.       The BOUNDS-section defines the lower and upper bound (l and u) of the
  298.       linear program. Missing values in l are assumed to be 0 and missing
  299.       values in u are assumed to be "infinite". The BOUNDS-section is
  300.       optional. Every line begins with a "UP" (for upper bound) or "LO"
  301.       (for lower bound), followed by the name of the bounds. It is possible
  302.       to specify more than one bounds-name. Our example:
  303.  
  304.       BOUNDS
  305.         UP  bound   x1    1
  306.         UP  bound   x2    1
  307.         UP  bound   x3    3
  308.  
  309.  
  310.  
  311. vii)  ENDATA-section:
  312.       ENDATA simply is the end of the data.
  313.  
  314.  
  315.  
  316.  
  317. Further notes on MPSX:
  318. ----------------------
  319.  
  320. - Identifier are restricted up to 8 characters. They can consist of every
  321.   printable character (except of space- and tab-characters). Lowercase
  322.   letters are converted to uppercase letters. The identifier after NAME
  323.   can have up to 33 characters to be compatible to AmigaDOS.
  324.  
  325. - Fields don't have to start in special columns (as in the original MPSX-
  326.   format coming from hollerith-cards). The only restriction is, that
  327.   section names have to start in column 1 the other lines mustn't start in
  328.   column 1.
  329.  
  330. - Lines can have a maximum length of 255 charcters. Every line must have a
  331.   new-line-character ('\n') at the end.
  332.  
  333.  
  334.  
  335. Technical notes:
  336. ----------------
  337.  
  338. - ASimplex uses double precision IEEE-arithmetic. "infinite" is represented
  339.   as NAN (Not A Number).
  340.  
  341. - The linear programs can have any size that fits into the memory. The only
  342.   "restriction" is that you can't have more than 32767 rows or columns.
  343.   But that's not really restricting, because e.g. you'd have a LP with
  344.   10000 rows and 20000 columns you'd need 2.2GBytes!
  345.  
  346. - If you have a PAL-Amiga you can change the size of the I/O-window by
  347.   simply replacing the line
  348.  
  349.     #define NTSC  1  with
  350.  
  351.     #define PAL   1
  352.  
  353.   an recompiling ASimplex with the make-utility.
  354.  
  355.  
  356.  
  357. Test-LPs:
  358. ---------
  359.  
  360. I have also included some LPs that I used to test ASimplex. AFIRO,
  361. ADLITTLE, SHARE2B and ISRAEL are four of the standard-test-LPs you
  362. can get via NETLIB from the Bell Laboratories. K_MINTY is a Klee-
  363. Minty-problem as an example that needs a lot of iterations compared
  364. to its size. The other LPs are my creations.
  365.  
  366.  
  367. Name        Rows    Cols    Nonzeros   Optimal value
  368. -------------------------------------------------------------------
  369.  
  370. AFIRO         28      32      88       min = -4.6475314285714e+02
  371. ADLITTLE      57      97     465       min =  2.2549496316238e+05
  372. SHARE2B       97      79     730       min = -4.1573224074142e+02
  373. ISRAEL       175     142    2358       min = -8.9664482186305e+05
  374.  
  375. EXAMPLE        4       3      12       min = -2.25, max = 1.0
  376. K_MINTY       11      10      65       min =  0   , max = 1e+18
  377. A36            3       6      14       min =  0   , max = unbounded       
  378. P142           6       3      12       min =  9.313225746e-10
  379.                                        max =  4011719.987
  380. P142DUAL       4       5      14       min =  4011719.987
  381.                                        max =  unbounded
  382.