lrslib programmer's guide Version 4.1

Introduction

lrslib consists of the following main components

Libraries:

    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.

Main Drivers:
lrs.c: Transform H-representation to V-representation or vice versa
redund.c Remove redundancies from H or V-representation

Demo drivers:
    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

Utilities:
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.

Installation

From lrs home page, click on "Download" and retrieve the file lrslib-041.tar.gz
    Unpack with:
       % gunzip lrslib-041.tar.gz
       % tar xvf lrslib-041.tar

Go to the new directory
% cd lrslib-041

Installation with built in arithmetic libraries.

     make binaries by typing
       % make all               (most 32 bit unix machines)
    or
      % make all64              (64 bit integer machines such as DEC Alpha)
    or
      % make nosigs        ( 32 bit machines without signals/timing routines)

Test the program by typing: lrs cube.ine
redund cubetop.ine

Install demos.

%make demo

Test the programs by typing: vedemo, chdemo, lpdemo or lpdemo1

Installation with GNU MP library

To use the GNU MP library, it is necessary to first install it and record its location. The
default makefile assumes: /usr/local/include and /usr/local/lib for headers and binaries
respectively. Edit the gmp: section of "makefile" appropriately.

make binaries by typing
% make gmp

Test the programs by typing: glrs cube.ine
gredund cube.ine

Demos

Demo drivers that are designed for user modification are included with this release:

vedemo.c           vertex enumeration
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[0]=1L, and for an extreme ray or linearity num[0]=0L. (In both cases den[0]=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[0] 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 returns

long 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);

Linear Programming

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.

Acknowledgements and References

I would like to thank many people for helping with this implementation project. Komei Fukuda encouraged me from the start, collaborated in designing the file formats, and provided many suggestions for improving the code. David Bremner implemented memory allocation, caching and signals. Jerry Quinn coded the integer divide routine. Bug reports were provided by many users, for which I thank them. In particular Gerardo Garbulsky's extensive use of earlier versions suggested many refinements, Ambros Marzetta demonstrated the importance of caching and Andreas Enge helped debug the volume computation. Oleg Pikhurko convinced me of the need for the lp-solve like procedures described in the Demos section.

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).
http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps

D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration Algorithm," Optimization Methods and Software, Vol. 10, pp.107-124 (1998)
http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps

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.