README file for lrs : reverse search vertex enumeration program ------------------------------------------------------------------------- Dear Colleagues: To install and run lrs please see the user's guide: ftp://mutt.cs.mcgill.ca/pub/C/USERGUIDE.html This README file serves as a record of various previous versions of lrs that may still be arround. As usual, please report bugs and other strange behaviour! -david avis avis@cs.mcgill.ca ------------------------------------------------------------------------------ 98.4.29 lrs3.2a.c fixes a bug in the output routine which occasionally caused facet(s) to not print when the input is a V-representation. _________________________________________________________________ 97.9.25 lrs3.1e.c is now available for use. Main new features: 1. V-representation, H-representation explicit. 2. Geometric rays can be obtained. 3. Volume compuatation fixed. 4. Origin handled consistently. 1. Input files should begin with: name H-representation or name V-representation where name is the name of the polyhedron. The "V-representation" is equivalent to the old "hull" option, which will still be recognized. In this case the input will be processed as a set of vertices and rays. The "H-representation" is the old default and will be assumed if neither "V-representation" nor "hull" is specified. In this case, the input is processed as a system of inequalities. In the output, the correct label will be attached: eg. if input is "H-representation" then output is "V-representation". eg. For the centred unit square: unit_square V-representation begin 4 3 rational 1 -1/2 -1/2 1 -1/2 1/2 1 1/2 -1/2 1 1/2 1/2 end and unit_square H-representation begin 4 3 rational 1 -2 0 1 0 -2 1 0 2 1 2 0 end 2. To print all geometric rays, place the option geometric after the end statement. Rays are output in the form: 0 x_1 .. x_d * 1 y_1 .. y_d This indicates ray x_1 .. x_d is incident with vertex y_1 .. y_d. This option should only be used if the input file is a H-representation. 3. A bug in the volume computation for rational input and with the "V-representation" (hull) option has been fixed. (Thanks to Andreas Enge for reporting this.) 4. In older versions, a V-representation of a pointed cone produced the "facet" 1 0 0 .. 0 This will no longer be output. Note, however, that the vertex 1 0 0 .. 0 (ie. the origin) must be present in the input file of a V-representation of a pointed cone. _______________________________________________________________________________ 97.3.27 lrs3.0.c is now available for TEST only, I expect it has bugs... Main features: 1. Hull computation 2. Volume more general 3. Cones are handled without producing duplicate rays 4. Cache 1. To compute the convex hull of a set of vertices and/or rays place the option hull BEFORE the begin line. (note cdd users need to place it after the end) If the input is all vertices (ie. a one in column one for every row) the output of lrs will not contain duplicates. 2. Place the option volume after the end line. If the input is a set of vertices (a one in column one for every row) which contain the origin in the interior of the convex hull, then the volume is computed. Rational input is allowed now. 3. If the input is a cone (ie. a zero in column one for each row) the output will not contain duplicate rays. (A new lexmin test is used). 4. David Bremner kindly installed a dictionary cache, which allows backtracking without pivoting if the dictionary is in the cache. A default is set for 10 dictionaries, and this can be reset by cache n after the end line. cache 1 is pure reverse search without extra memory. NOTES: (1) lrs usually performs faster with the hull option set. This is because it prefers cones, and a hull problem is lifted to a cone in one higher dimension. I have observed speed ups of more than 5 times by using hull. (2) Compile as usual (see below). If you have trouble compiling, try compile option -DOMIT_SIGNALS and/or -DOMIT_TIMES ---------------------------------------------------------------- 97.2.28 Version 2.5n of lrs.c includes various improvements to make the program easier to use and more compatible with Komei Fukuda's cdd+ (http://www.ifor.math.ethz.ch/staff/fukuda/cdd_home/cdd.html). cdd+ contains many features that can be used in conjunction with lrs by using cdd+'s postanalysis option (eg. for facet/vertex adjacency and incidence relationships). I highly recommended you to read Fukuda's cddplus manual for help in setting up input files. Most files set up for cdd+ should run with lrs, although some options (such as hull) are not implemented and some (such as lexmin etc.) are not relevant to lrs. Version 2.5n has NOT been thoroughly tested, so I have left the earlier Version 2.5i (lrs25i.c.gz) in case you encounter difficulties. Main Changes for lrs 2.5n: 1. Build function incorporated, so an initial vertex is not required. 2. Initial vertex can be specified implicitly(as before) or explicitly. 3. LP functions of maximize/minimize. 4. Dynamic allocation of maximum digit size. 5. Interrupt signal handling to allow restart. 6. Change to output format of printcobasis option to print inequality numbers. 7. Restart now uses inequality numbers rather than cobasic indices. (4 and 5 kindly implemented by David Bremner). The program is compiled as before: (Recommended compiler: gcc) gcc -O lrs.c /* 32 bit machines */ gcc -O -DB64 lrs.c /* 64 bit machines */ Details 1. lrs will now handle an input file for any polyhedron P={x: b - Ax >= 0 } specified by m inequalities in d=n-1 dimensions, even if no starting vertex is known. The build program is no longer needed. If a starting vertex is not known the progam uses Dual Bland's rule to find one. 2. If a stating vertex is known, the processing will be faster if it is specified in one of two ways: implicitly: by including the d defining inequalities last in the input file, or explicitly: by the startingcobasis option startingcobasis i i i ... i 1 2 3 d where the indices are in the range 1..m and give d linearly independent inequalities which are satisfied as equations by the vertex. 3. LP functions of maximize/minimize are implemented as for cdd+. The option maximize c c c .... c 0 1 2 d simply maximizes the function c + c x + c x + ... + c x 0 1 1 2 2 d d over the given polyhedron. A optimal vertex is given when it exists, otherwise for unbounded solutions a vertex and ray is given. The minimize will be performed if the option minimize c c c .... c 0 1 2 d is specified. 4. lrs now allows dynamic allocation of maximum integer size. To specify a maximum integer size, include the option line: digits n BEFORE the begin line, where n is the maximum number of decimal digits required for the computation. The default is set to 180 digits. Memory allocated is directly proportional to n. At the end of a run a message is given informing the user of the maximum integer size encountered. This may be used to optimize memory usage on subsequent runs (if doing estimation for example). The output: *Max digits= 45/180 indicates that the maximum integer encountered had 45 decimal digits, and the program allowed up to 180 digit integers. 5. It is now possible to interrupt lrs and get the latest cobasis which can be used for restarting (useful if machine is going down!) If given a signal operation USR1 print current cobasis and continue TERM print current cobasis and terminate INT (ctrl-C) ditto HUP ditto 6. The printcobasis option now provides of list of the inequalities that define the current cobasis. For example the output: V#3 R#0 B#11 h=3 facets 5 7 9 10 11 det=16 1 0 1/4 1/4 1/4 1/4 indicates the vertex ( 0 1/4 1/4 1/4 1/4 ) is defined by solving input inequalities numbered 5 7 9 10 11 as equations. As usual the option printcobasis n prints every nth cobasis, and every cobasis if n is omitted. 7. The restart option has been modified to be compatible with the new output format of printcobasis. Before cobasic indices were used to specify a restart, now we use the inequality numbers. To restart from the basis given above, include the option: restart 3 0 11 3 5 7 9 10 11 (ie. include all numbers from the printcobasis line except the last one.) NOTE: The original input file must be used for the restart, since any change in the ordering of the inequalities, or in the startingcobasis would be disastrous! _________________________________________________________________ 95.10.17 Version 2.5i lrs.c is a greatly modified version of earlier versions, and use of earlier versions is not recommended. The same input format is maintained, however the output is slightly modified to be more consistent. The primary difference from earlier versions is that lrs uses lexicographic pivoting, which is considerably faster and more accurate than the previous method of least subscript rule + explicit perturbation. It also produces extreme rays for unbounded polytopes. Each vertex is output once, but extreme rays may be repeated, so piping the output through a buffer (buffer.c) is recommended. lrs.c accepts integer and/or rational input, but rational is converted internally to integer. The code itself uses all integer extended precision. Determinant information is given for bases. This can be interpreted as the volume of a set of input points provided: (a) input is all integer (b) first column is all one (c) the origin is interior to the convex hull. Recommended compiler: gcc. Compile with gcc -O lrs.c /* 32 bit machines */ gcc -O -DB64 lrs.c /* 64 bit machines */ ------------------------------------------------------------------------- qrs.c _____ qrs.c implements Jack Edmond's Qpivot scheme and is usually substantially faster than rs.c. It can only be used with integer inputs. To be efficient, any common divisors of a row or column should be removed. It does not use the Euclidean algorithm to reduce rational numbers. Without perturbation is generates all bases of the input system. A new program buffer.c is provided to clean up the output as it arrives. It is useful when the perturb option is used, since the same vertex may be output many times. It can be used as a filter with or without arguments: rs < file.ine | buffer or rs < file.ine | buffer maxline maxbuffer It builds a circular buffer of maxbuffer (default 50) lines of maxline (default 5000) characters each. If an output line is already in the buffer, it is not output. Note that the script clean is inferior for huge files, since it sorts the whole output and then removes duplicates. Compile as for lrs.c depending on integer size. _________________________________________________________________ Estimation of Number of Vertices -------------------------------- For use with lrs or qrs. This is useful to estimate the number of bases/vertices in large problems. To use the estimator specify a maximum depth and the number of probes to be taken for each estimate. The estimator makes this number of probes from each node at maximum depth, and computes a global estimate of tree size. This is unbiased, ie. the expected value of the estimate is the number of nodes in the tree. The estimate has very large variance, however, and is usually an underestimate. It is better to make fewer probes from deeper in the tree than more probes from the root. Examples: (include these lines in the options section at the end of .ine file) maxdepth 0 estimates 100 Makes 100 probes from root and estimates tree size. maxdepth 3 estimates 1 Makes one probe from each node at depth 3 in the tree. Note: The estimator can be used for unperturbed polytopes and gives separate estimates for vertices and bases. The former has VERY large variance, but it is unbiased. For perturbed polytopes, both estimates will usually be the same. __________________________________________________________________________ INPUT -------- Sample input files are in the subdirectory ine with corresponding output files in the subdirectory ext. The exact input specifications are given in "files" in this directory. The program rs computes all of the vertices of a linear system Ax<=b, for an m by d matrix A. The variables are not assumed to be non-negative. It is assumed that the last d rows define a vertex of the polytope. If a vertex is not known, the program build.c takes a standard input file and permutes the rows so that the last d define a vertex. Before compiling the program, make sure the constant D is at least d and M is at least m, in the source rs.c. The defaults are M=100, D=100. The input file must contain: begin m d+1 integer (or rational for lrs) b -A row by row. end various option flags described below Any line beginning with a keyword other than those below is skipped. If the problem does have the form Ax<=b, x>=0 then the flag "non-negative" is used after the constraints are entered. The identity matrix should be the last d constraints. Ie., for d=3 0 1 0 0 0 0 1 0 0 0 0 1 Options allbases -print all bases rather than just distinct vertices. printcobasis k -print cobasis indices for every k-th vertex,needed for restart nonnegative -last d constraints are the identity matrix specifying x>=0 and b is nonnegative. debug start end -debug mode from basis number start until basis number end. if start and end are both zero, debug mode is on for the whole run perturb seed nrange drange ***for qrs only, lrs does this symbolically *** -for degenerate polytopes, randomly perturb the rhs vector b by adding a rational x/y where 1<=x<=nrange and y=drange This option gives huge speedups for highly degenerate polytopes. The output is the unperturbed vertex, so the same vertex may be output more than once since it corresponds to different perturbed vertices. restart vertex# basis# depth cobasis indices -restart from known vertex, by giving the vertex number, basis number, depth and a list of all cobasic indices. This information is given in standard output. maxdepth depth -do a search down to the specified depth, but do not go deeper. estimates k -perform k probes from each node at maxdepth, computing an estimate of tree size mindepth depth -do not backtrack above indicated depth. This is useful when restarting from a known vertex at known depth. Distributed computing can be done by first doing a search limited by limited by maxdepth, down to say depth=2 with the estimates option set to estimate tree size. Then on different work stations restart from each vertex at depth=2 with mindepth 2. This will generate all vertices in "parallel". --------------------------------------------------------------------------------------------- OUTPUT ------ The output of lrs gives vertices and/or extreme rays. For vertices, the format is 1 x_1 x_2 ... x_d where x_1 .. x_d are the coordinates in rationals for the vertex. A ray is output 0 x_1 ... x_d where x_1 ... x_d is some point on the extreme ray (ie the vector can be scaled by any positive number to give the ray. qrs gives only vertex output.