David Avis avis@cs.mcgill.ca http://cgm.cs.mcgill.ca/~avis

Introduction

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

Unpack with:

% gunzip lrslib-041.tar.gz

% tar xvf lrslib-041.tar

Go to the new directory

% cd lrslib-041

% 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

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

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.

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

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).

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.