lrslib: A callable library of functions implementing
lrs and redund
lrsmp: An extended precision arithmetic package for lrslib
lrslong: A fixed precision integer package for lrslib
lrsgmp: An interface for lrslib to the GNU MP arithmetic package.
lrs.c: Transform H-representation to V-representation or vice versa
redund.c Remove redundancies from H or V-representation
vedemo.c Generate vertices of a set of hypercubes
chdemo.c Generate facets from a set of generated cyclic polytopes
lpdemo.c Solve a series of lp problems on generated cubes
buffer.c Remove duplicates output (parallel geometric rays in unbounded non-pointed polyhedra)
The demo drivers use an "lp-solve" like procedures to construct the input matrix (and objective function if needed). These programs should be easily modifiable to solve similar problems for other polyhedra. Normally all that is necessary is for the user to modify the procedure used to generate the polyhedron: makecube in the case of vedemo and makecyclic in the case of chdemo.
For the moment, the only documentation I can offer for the main drivers and library procedures are the comments in the individual programs. Consult the User's manual for usage instructions.
These programs can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please read the file COPYING carefully before using. Please inform the author of any interesting applications for which lrs was helpful.
Go to the new directory
% cd lrslib-041
Test the program by typing:
Test the programs by typing: vedemo, chdemo, lpdemo or lpdemo1
make binaries by typing
% make gmp
Test the programs by typing: glrs
chdemo.c facet enumeration
lpdemo.c linear programming
Main components of all demos
The main components of each demo are similar, and concern problem set up, memory allocation and memory cleanup:
long lrs_init (char *name); /* initialize lrslib and arithmetic package for prog "name" */
This procedure is called once at the beginning of the driver, and does basic setup functions. "name" will be output with some information about version numer or lrslib and which arithmetic package is used. FALSE is returned in case of failure.
lrs_dat *lrs_alloc_dat (char *name); /* allocate for lrs_dat structure "name" */
This procedure produces a structure of type lrs_dat (usually saved in variable Q) which has basically static information about the problem. This includes a large number of flags and a few arrays for indices. All flags are set at default values (see lrslib.h) but can be overridden after the function has been called. A NULL pointer is returned in case of failure. It is called once for each problem to be solved.
lrs_dic *lrs_alloc_dic (lrs_dat * Q); /* allocate for lrs_dic structure corr. to Q */
This procedure produces a structure of type lrs_dic (usually saved in variable P) which has basically dynamic information about the problem. This includes mainly the dictionary matrix, basic and cobasic indices and their row and column locations. For vertex or facet enumeration additional lrs_dic structures are created automatically and cached, to speed up backtracking. A NULL pointer is returned in case of failure.
void lrs_free_dic ( lrs_dic *P, lrs_dat *Q);
Free the space allocated for lrs_dic structures. This includes all cached structures. This procedure must be called before lrs_free_dat. It should be called before starting a new problem.
void lrs_free_dat ( lrs_dat *Q);
Free the space allocated for lrs_dat structure. It should be called before starting a new problem.void lrs_close (char *name); /* close lrs lib program "name" */
Final clean up. This is called once at the end of the run.Building the data matrix
For an H-representation, the data for the problem b+Ax >= 0 is entered row by row. This is illustrated in program makecube(lrs_dic P, lrs_dat Q) (in vedemo.c).The procedure for entering a row of data is:
void lrs_set_row(lrs_dic *P, lrs_dat *Q, long
row, long num, long den, long ineq);
Here row is the row number of the current row in the matrix, a long integer from 1 to Q->m. The long arrays num and den contain the numerator and denominator coeficients, and have length Q->n. The long integer ineq is replaced by either GE (TRUE) or EQ (FALSE) to represent an inequality or equation respectively.A V-representation is built in a similar way, as illustrated in makecyclic(lrs_dic P, lrs_dat Q) (in chdemo.c). This also makes use of lrs_set_row. For a vertex, num=1L, and for an extreme ray or linearity num=0L. (In both cases den=1L). ineq is TRUE for a vertex or extreme ray, and FALSE for a linearity.
If an objective function is required (eg., linear programming) it can be set up using:
void lrs_set_obj(lrs_dic *P, lrs_dat *Q, long num, long den, long max);
The long arrays num, den hold the objective function coeficients. num is a constant term. The long integer max has values MAXIMIZE(TRUE) or MINIMIZE(FALSE).There are two additional procedures that perform the same functions, but where the coefficients are given in lrs_mp format:
void lrs_set_row_mp(lrs_dic *P, lrs_dat *Q, long row, lrs_mp_vector num, lrs_mp_vector den, long ineq);
void lrs_set_obj_mp(lrs_dic *P, lrs_dat *Q, lrs_mp_vector num, lrs_mp_vector den, long max);
Reverse search: vedemo and chdemo
After constructing the input data, reverse search
is used to generate all vertices/rays(vedemo) or facets(chdemo). Unless
the tree search will be customized in some way, there is no need to change
this part of the demo programs. To
begin a starting basis is found using:
long lrs_getfirstbasis (lrs_dic ** P, lrs_dat * Q, lrs_mp_matrix * Lin, long no_output);
If there are redundant columns in the input data, a linearity space is computed and stored in matrix Lin. The procedure returnslong lrs_getnextbasis (lrs_dic **P, lrs_dat * Q, long prune);
This procedure returns FALSE when there are no more bases to find. The variable prune can be set to TRUE to cause the reverse search to prune the tree at the current vertex, ie. to backtrack rather than going deeper in the tree.Output extraction
A dictionary potentially represents one vertex and several extreme rays (vertex enumeration) or several facets (facet enumeration). Due to degeneracy, the same vertex/ray/facet may be generated several times. The procedure
long lrs_getsolution (lrs_dic * P, lrs_dat * Q, lrs_mp_vector output, long col);
checks each column col of the dictionary to see if it contains some output, and if so returns TRUE with output containing the respective integer coefficients. To avoid duplication, only the lexicographically minimum representation of a given output is extracted by lrs_getsolution. The output coefficients need to be divided by P->det to get the correct rational output. This is done by the procedure
void lrs_printoutput (lrs_dat * Q, lrs_mp_vector output);
The program lpdemo.c solves a set of linear programs on hypercubes, using makecube to construct the constraint matrices. Once the dictionary has been generated, a single call to
long lrs_solvelp (lrs_dic * P, lrs_dat * Q, long maximize);
solves the linear program.
D. Avis, "lrs: A Revised Implementation of the Reverse Search
Vertex Enumeration Algorithm," In: Polytopes - Combinatorics and Computation,
G. Kalai & G. Ziegler eds., Birkhauser-Verlag, DMV Seminar Band 29,
pp. 177-198 (2000).
D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration
Algorithm," Optimization Methods and Software, Vol. 10, pp.107-124
D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol 7,pp.265-301(1997). http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps
D. Avis and L. Devroye, "Estimating the Number of Vertices of a Polyhedron," pp. 179-190 in Snapshots of Computational and Discrete Geometry, ed. D. Avis and P. Bose, School of Computer Science, McGill University (1994). http://cgm.cs.mcgill.ca/~avis/doc/avis/AD94a.ps
D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra," Discrete and Computational Geometry, Vol. 8, pp. 295-313 (1992). http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps
D. Bremner, K. Fukuda and A. Marzetta, Primal-Dual Methods for Vertex
and Facet Enumeration, 13th ACM
Symposium on Computational Geometry SCG 1997, 49-56.