User's Guide for lrs - Version 4.2
June 1, 2005
Copyright(C) 2005
lrs home page
What's
New
in Version 4.2
What's
New
in Version 4.1
What's New in
Version 4.0
Introduction (revised)
Installation
(revised)
File Formats
Basic Options (revised)
Arithmetic Packages
Estimation
Fourier Elimination (new in V4.2)
Linear Programming(revised)
Nash Equilibria (new in V4.2)
Volume Computation
Voronoi Diagrams
Extreme
Point Enumeration and Redundant Inequalities
Linearities
Timing and Interrupts
Error Messages and
Troubleshooting
Hints and Comments
Acknowledgements and References
What's New in Version 4.2
The main additions in Version 4.2 are two new drivers:
- nash:
Computes
all Nash equlibria of a two person non-cooperative game. Can handle
bounds on payoff functions.
- fourier: Projects a polyhedron
given by an H-representation onto a
subspace using Fourier elimination (contributed by Tallman Nkgau).
There is a new bound
option in lrs that truncates the reverse search
tree when the objective function is less than the given bound for a
maximization problem, or greater than the bound for minimization. When
lrs is used to solve LPs, the dual
variables will now be printed for
the optimum solution.
Other new basic options: dualperturb, project, printslack
The nonnegative
option should now work correctly even if the origin is not a
vertex of the
polyhedron.
What's New in Version 4.1
Version 4.1 of lrslib contains no
substantial revisions to the basic algorithms, but contains complete
garbage collection and some simple drivers for solving vertex
enumeration, convex hull and linear programming problems on generate
polyhedra. The generation of input internally is simplified by the
inclusion of some lpsolve like procedures to enable easy construction
of the constraint matrix. Documentation for this is contained in
http://cgm.cs.mcgill.ca/~avis/C/lrslib/lrslib.html
A new feature of the basic package is the nonnegative
option that speeds up the solution of problems with H-representation:
b+Ax >= 0,
x>=0
Note: The origin must be a
vertex of the feasible region for Version 4.1.
What's New in Version
4.0 (included in Version 4.1)
Version 4.0 of lrs is
distributed as the callable library lrslib.
Two drivers are supplied, lrs.c and redund.c , that replace the corresponding
programs in previous distributions. The new programs should be
compatible with earlier ones, and correctly process existing input
files. New in this version is that input files need not be of full
dimension, and input equations or linearities
may be specified. In addition, input files may contain redundant
columns, which are closely connected to linearities. See also the
section File Formats for more
information.
This distribution also comes with three arithmetic lpackages: lrsmp, lrslong and lrsgmp . The
library lrsmp is essentially the same extended precision package
included in earlier distributions. lrslong is an implementation using
long integer arithmetic, which is considerably faster, but does no
overflow checking. lrsgmp is an interface to GNU MP which must be installed
first. Binaries are produced for all arithmetic packages using the
distributed make file.
Most of the functions required for lrs
and redund are included in the library lrslib. This is compiled with either of the
arithmetic packages. One of the purposes of supplying a library is to
allow simple customization of the reverse search procedure. The program
lrs.c is the reverse search driver, and
supplies each output vector to the user. It can be customized to prune
the search according to various criteria,
eg., if the value of some objective function falls below some value, or
if
an integer vector is produced etc.
The installation procedure
has been
simplified, and the package is distributed as a compressed tar file.
Included
is a makefile for various configurations and some typical input files.
Binaries
are also included for some platforms.
There are new options: incidence ,
which lists
all inequalities (resp. vertices/rays) which are incident with the
current
output vertex/ray (resp. facet). and truncate
which
prunes the search tree everytime a vertex different from the starting
vertex
is reached.
Introduction
A polyhedron can be described by a list of inequalities (H-representation)
or as by a list of its vertices and extreme rays (V-representation).lrs
is a C program that converts a H-representation of a polyhedron to
its V-representation, and vice versa. These problems are known
respectively at the vertex enumeration and convex hull
problems.
Fukuda's
FAQ
page contains a more detailed introduction to the problem,
along
with many useful tips for the new user.
lrs is based on the reverse search algorithm of Avis and
Fukuda(1992) , modified to use lexicographic pivoting and
implemented in rational arithmetic. See Avis(1998a)
for a technical description, and Avis(1998b)
for some computational experience. The input files are in Polyhedra
format , developed by Fukuda and the author. The format is
essentially
self-dual, and the output file produced can be read in as an input
file,
with very minor modifications, to perform the reverse transformation.
This
format is compatible with that used in Fukuda's cdd
package, which performs the same transformations using a version of
the double description method. cdd can also be
used in conjunction with lrs as a pre-processor for
projections to subspaces, or as a post processor for computing the
entire face lattice. Another program using the same file format is the
primal-dual method pd,
developed by
Bremner, Fukuda and Marzetta . It is essentially dual to lrs,
and is very efficient for computing H-representations of simple
polyhedra,
and V-representations of simplicial polyhedra. It will compute the
volume
of a polytope given by an H-representation.
Another program based on the double description method is
Christof and Loebel's
porta , and a versatile tool for the algorithmic treatment of
polytopes is Gawrilow and Joswig's polymake
package. Barber et al.'s
qhull.
A package for volume computation called Vinci
has been developped by Enge. A comprehensive general source of related
infomation are Erickson's
Computational Geometry Pages.
In version 4.0, polyhedra handled by lrs need not be
full dimensional and may contain input linearities and redundant
columns . lrs accepts either integer or rational input,
and produces integer or rational output. All computations are done
exactly using either extended precision arithmetic or fixed long
integer arithmetic. In the latter case no overflow checking is
performed, and the user is advised to check
results using the extended precision version. Since it is a pivot based
method, lrs can be very slow for degenerate inputs: i.e..
H-representations of non-simple polyhedra, and V-representations of
non-simplicial polyhedra. On the other hand, it does not store the
vertices/ rays or facets produced, so for very large problems it may be
the only method that can solve the
problem. A discussion of various vertex enumeration/convex hull
methods
and the types of polyhedra that cause them to behave badly is contained
in Avis,
Bremner and Seidel( 1997).
Additional functions of lrs include:
- Estimating the number of vertices/rays or facets of a polytope,
and estimating the total running time
- Computing the volume of a polytope given by a V-representation
- Solving LP problems for a polyhedron given by a H-representation
- Computing the Voronoi vertices and rays for an input set of data
points
- The ability to suspend and restart execution at any time
A second program, redund, is supplied for removing redundancy
from and H or V-representation. In the former case, this involves the
removal of any inequalities that are not required to represent the
polyhedron. In the latter case, this is the problem of evaluating
the extreme points and rays of a V-representation. These problems are
normally considerably easier than the transforamtions performed by
lrs. In some cases,
redundancy can greatly slow the processing time taken by lrs,
and
it is advisble to remove any redundancy from the input file using
redund
before applying lrs.
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/redund were helpful.
Installation
cube
V-representation
begin
***** 4 rational
1 1 1 1
1 -1 1 1
1 1 -1 1
1 -1 -1 1
1 1 1 -1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 -1
end
This is a list of the 8 vertices with each co-ordinate +/-
1. The ***** should be replaced by the actual number, 8, of
vertices. Since lrs does not save the output produced, it does
not know this value until the execution terminates. This output is now
essentially the same as file cube.ext. To complete the test type:
Now the output produced is essentially the file
cube.ine, with the inequalities appearing in a different order.
The program buffer is a small utility that can be used to remove
duplicate line in the output that may occur if the input is not a
polytope or a pointed cone. For such unbounded polyhedra, rays
may appear in the output more than once. The program takes two optional
integer parameters:
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. To use buffer, pipe the output from lrs:
File Formats
Example files can be found in the directories ine and ext which come
in the standard distribution. File formats were developed jointly with
Komei Fukuda and are compatible with cdd
. The cdd manual contains additional information and examples.
The input for lrs is a H- or V- representation of a polytope.
These files have the following formats:
H-representation
name
H-representation
{options}
{linearities
} /* new in version 4.0 */
begin
m n rational
{list of inequalities }
end
{options}
name is a user supplied name for the
polytope. If the line H-representation is omitted,
H-representation is assumed. The input coefficients are read in
free format, and are not checked for type.
Coefficients are separated by white space. Normally this file would be
saved
with filename suffix .ine but this not required. Comments
may
appear before the begin or after the end, and to avoid interpretation
as
an option, should begin with a special character such as "*" or "#".
The integer m is the number of inequalities, and the
integer n is the dimension of the input +1.
A list of inequalities contains the coefficients of inequalities of the
form
a_{0} + a_{1 }x_{1 }+ ... + a_{n-1}
x_{n-1} >= 0.
This inequality is input as the line
a_{0 }a_{1 }... a_{n-1}
The coefficients can be entered as integers or rationals in the
format x/y.
For example, the square centred at the origin with side length two has
inequalities
1 + x_{1} >= 0 1+ x_{2
}>=0 1-x_{
1 }>=
0 1-x_{2
}>=0
and would be represented by the input file
square
*centred square of side 2
H-representation
begin
4 3 rational
1 1 0
1 0 1
1 -1 0
1 0 -1
end
V-representation
name
V-representation
{options}
{linearities
}
/* new in version 4.0 */
begin
m n rational
{list of vertices and extreme rays}
end
{options)
name is a user supplied name for the polytope.
The line V-representation is required. The input coefficients are
read in free format, and are not checked for type. Coefficients are
separated
by white space. Comments may appear before the begin or after the end,
and
to avoid interpretation as an option, should begin with a special
character
such as "*" or "#".Normally this file would be stored with filename
suffix
. ext, but this is not required.
The integer m is the number of vertices and rays, and
the integer n is the dimension of the input +1.
Each vertex is given in the form
1 v_{0 } v _{1 }...
v_{n-1}
Each ray is given in the form
0 r_{0 } r _{1 }...
r_{n-1}
where r_{0 } r _{1 }... r_{
n-1}is a point on the ray.
There must be at least one vertex in each file. For bounded
polyhedra there will be no rays entered.
The coefficients can be entered as integers or rationals in the format
x/y.
For example, the unit square centred at the origin has vertices
(1,1) ,(1,-1),(-1,1),(-1,-1)
and would be represented by the input file
square
*centred square of side 2
V-representation
begin
4 3 rational
1 1 1
1 1 -1
1 -1 1
1 -1 -1
end
The positive quadrant has vertex (0,0) and rays (1,0) (0,1) and is
represented
quadrant
*positive quadrant
V-representation
begin
3 3 rational
1 0 0
0 1 0
0 0 1
end
Its H-representation contains the inequalities x_{1 }>=
0 and x_{2} >= 0 :
quadrant
*positive quadrant
H-representation
begin
2 3 rational
0 1 0
0 0 1
end
Note for cdd users: lrs
uses essentially the same file format as cdd. Files prepared
for cdd should work with little or no modification. Note
that the V-representation corresponds to the "hull" option in cdd.
Options specific to cdd can be left in the input files and will
be ignored by lrs.
Note the input files for lrs are read in free format, after
the
line m n rational lrs
will look for exactly m*n rationals or
integers separated by white space (blank, carriage return, tab
etc.). lrs will not "drop" extra columns of input if n is less
than the number of columns supplied.
Basic Options
New
for Version 4.2: bound, dualperturb, printslack, project
lrs has many options to allow various functions to be
performed, and to modify the output produced. Almost all options are
placed after the end statement, maintaining compatibility with cdd.
Where this is not the case, it will be mentioned explicitly. All
options are optional.
allbases
This option instructs lrs to list each vertex (or facet) for
each of its bases. Normally a vertex (or facet) is only output when its
lex-min basis is found, to avoid duplications - see section Output Duplication . This option is often combined
with printcobasis .
bound x
New in Ver
4.2 // Use
with H-representation - for lrs or nash //
Either the maximize or minimize option
should be selected. x is an integer or rational.
For maximization (resp. minimization) the reverse search tree is
truncated whenever the current objective value is less (resp.
more) than x .
cache n
lrs stores the latest n dictionaries in the reverse
search tree. This speeds up the backtracking step, but requires more
memory. If n is set to one, there is no caching and "pure"
reverse search is performed. The default is n=10. At the end of a
run a message gives cache information. The output
*Dictionary Cache: max size= 4 misses=
10/1340 Tree Depth=5
indicates that with cache size set to 4, only 10 of the 1340
dictionaries computed were not in the cache during backtracking
and had to be
recomputed. The maximum tree depth was 5, so there would be no misses
with
a cache size of 6. Full caching reduces processing time by about 40%.
debug startingbasis endingbasis
Print out cryptic but detailed trace, dictionaries etc.
starting at #B=startingbasis and ending at #B=endingbasis. debug 0 0 gives a
complete trace.
digits n
// placed before the begin statement//
n is the maximum number of decimal digits to be used. If this is
exceeded the program terminates with a message (it can usually be
restarted). The default is set to about 100 digits. 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 and
speed on subsequent runs (if doing estimation for example). The output:
*Max digits= 45/100
indicates that the maximum integer encountered had 45 decimal digits,
and the program allowed up to 100 digit integers.
dualperturb
If lrs
is executed with the maximize
or minimize option, the
reverse search tree is rooted at an optimum vertex for this function.
If there are mulitiple optimum vertices, the output will often not be
complete. This option gives a small perturbation to the objective to
avoid this.
A warning message is given if the starting dictionary is dual
degenerate .
estimates k
Estimate the output size. Used in conjunction with maxdepth - see Estimation.
geometric
// H-representation or voronoi option only //
With this option, each ray is printed together with the vertex with
which it is incident. They output has the form:
0 r_{0 } r _{1 }...
r_{n-1}* 1 v_{0 } v _{1 }...
v_{n-1}
This indicates ray 0 r_{0 } r _{1
}... r_{n-1}is incident with vertex
1 v_{0 } v _{1 }...
v_{n-1}. For the quadrant, the output is:
1 0 0
0 0 1 * 1 0 0
0 1 0 * 1 0 0
This indicates the origin is a vertex, and there are two geometric
rays: (0,t) and (t,0) both adjacent to the origin. For more information
see Geometric Rays in Hints and
Comments .
incidence // New in version 4.0 //
This option automatically switches on
printcobasis , so see below for a description of this option first.
For input H-representation, indices of all
input inequalities that contain the vertex/ray that is about to be
output. For a simplicial face, there is no new output, since these
indices are already listed. Otherwise, the additional tight
inequalities are listed after a colon.
Eg:
V#1 R#0 B#1 h=0 facets 12 14 15
16 : 9 10 11 13 I#8 det= 8
1 0 0 0
1
The vertex 0 0
0 1 satisfies 8 input inequalities as
equations, as indicated by I#8 : those with indices 12,14,15,16 are in the cobasis, and those with indices 9, 10, 11, 13 are
in the basis. For a ray:
V#1 R#5 B#1 h=0 facets 5 9* 10 11 12
13 : 2 3 4 I#8 det= 8
0 1 1 0
0 1 1
Here the ray
1 1 0 0 1 1 lies on 8 inequalities, with indices 5 10 11 12 13 in
basis and 2 3 4 in cobasis. The
starred index 9* indicates that the ray is terminated by the input
inequality 9. This inequality is in the cobasis and defines the vertex
from which the ray starts.
For input V-representation, indices of all
input vertices/rays that lie on the facet that is about to be output:
F#5 B#3 h=2 vertices/rays 7 8* 11 13
15 : 1 3 5 9 I#8 det= 16
1 -1 0 0 0
The facet generated by inequality x_{1}
<= 1 contains 8 input vertices, as indicated by I#8: those with
indices 7,11,13,15 are in the cobasis, and those with indices 1 3 5 9 are in the
basis.The starred index 8* indicates that this vertex is also in the
cobasis, but is not contained in the facet. It arises due to the
lifting operation used with input V-representations.
#incidence
The same as printcobasis. Included
for compatability
with cdd.
linearity k i_{1 }i_{2
} i ... i_{k}
The input contains k linearities in rows i_{1 }i_{2 }i ... i_{k }of
the input file are equations. See Linearities.
maxdepth k
The search will be truncated at depth k. All
bases with depth less than or equal to k will be computed. k
is a non-negative integer, and this option is used for estimates
- see Estimation.
Note: For H-representations, rays at
depth k will not be reported. For V-representations, facets at depth k
will not be reported.
maximize a_{0}
a_{1 }... a_{n-1}
// H-representation only //
minimize a_{0}
a_{1 }... a_{n-1}
// H-representation only //
If used with
lrs the starting vertex maximizes
(or minimizes) the function a
_{0} + a
_{1 }x
_{
1 }+ ... + a
_{n-1} x
_{n-1}.
The dualperturb option may be needed to avoid dual degeneracy.
See Nash Equilibria and
Linear
Programming
mindepth k
Backtracking
will be terminated at depth k, for k a non-negative integer. This can
be used for running reverse search on subtrees as separate processes,
e.g. in a distributed computing environment.
nonnegative
//modified in lrs 4.2 //
// This option must come before the begin statement//
//H-representation only //
Bug:
Can only be used if the origin is a vertex of the polyhedron
For problems where the input is an
H-representation of the form b+Ax>=0, x>=0 (ie. all variables
non-negative, all constraints inequalities) it is not necessary to give
the non-negative constraints explicitly if the nonnegative option is
used. This option cannot be used for V-representations, or with the linearity option (in
which case the linearities will be treated as
inequalities). This option may be used with redund , but the implied
nonnegativity constraints are not tested
themselves for redundancy. To test everything it is necessary to enter
the
nonnegativity constraints explicitly in the input file. (In Ver 4.1,
the origin must be a vertex).
printcobasis
k
Modified in lrs4.0
Every k'th cobasis is printed. If k is omitted,
the cobasis is printed for each vertex/ray/facet that is output.
For
a long run it is useful to print the cobasis occasionally so that the
program can be restarted if necessary.
H-representation: If the
input is an H-representation the cobasis is a list the indices of
the inequalities from the input file that define the current vertex or
ray. For example, with input cube.ine a typical output is:
V#5 R#0 B#5 h=1 facets 3 4 5 I#3 det=1
1 1 1 -1
This indicates that the vertex (1,1,-1) is
defined by the 3rd, 4th and 5th facet inequalities in the input file
being satisfied as equations. It is the (B#)5th basis computed, and there have been (V#)5 vertices and
(R#)0 rays output up to this point. I#3 means that this vertex is
incident
with 3 input inequalities, ie. it is non-degenerate. See option incidence above for
more information.
For rays, a cobasis is also printed. In this
case the cobasis is the cobasis of the vertex from which the ray
emanates. One of the indices is starred, this indicates the inequality
to be dropped from the cobasis to define the ray. For example the
output:
V#1 R#6 B#4 h=1 facets 2 4* 5 7 I#3
det=1
0 1 1 2 1
indicates that the ray (1,1,2,1)
emanates from a vertex with cobasis defined by input inequalities 2 4 5
7 satisfied as equations. The ray is defined by dropping the equation
with
index 4. Note that there may not appear any vertex in the output with
cobasis
2 4 5 7, since the corresponding vertex may be degenerate and printed
with
another (the lex-min) cobasis. To find out which vertices correspond to
which rays, use also the geometric option. Now the output may appear:
V#1 R#6 B#4 h=1 facets 2 4* 5 7 I#3
det=1
0 1 1 2 1 * 1 0 0 0 0
This indicates that the ray is incident to the
origin. Alternatively, if the allbases
option is used, all cobases will be
printed out.
V-representation: If the input is a V-representation, the
cobasis is a list of the input vertices /rays that define the current
facet. For example, with input file cube.ext a typical output is:
F#5 B#4 h=3 vertices/rays 2 3 4 5* I#3
det= 8
1 0 0 -1
There have been 5 facets output up to this
point, and 4 bases have been computed. This facet is defined by
the vertices in positions 2,3,4 in the input file. The additional
cobasis
index 5* appears because a V-representation is lifted to one higher
dimension
before processing, and this index fills out the cobasis. I#3 means that
this
facet is incident with 3 input vertices/rays, ie. it is non-degenerate.
See
option incidence above for more information.
To initiate lrs from this
facet all 4 indices must be given in this order (omit the *), eg.
startingcobasis 2 3 4 5
Similarly, all 4 indices must be
given in order to restart from this facet:
restart 5 4 3 2 3 4 5
printslack
New in Ver
4.2 // Use
with H-representation //
lrs
prints a list of the indices of the input inequalities that are
satisfied strictly for the current vertex, ie. corresponding slack
variable is positive.
If nonnegative is set, the
list will also include indices n+i for each decision variable x_{i}
which is positive.
project
restart V# R# B# depth {facet
#s
or
vertex/ray #s}
Modified in lrs4.0
lrs can be restarted from
any known cobasis. The calculation will proceed to normal termination.
All of the information is contained in the output from a printcobasis
option. The order of the indices is very important, enter
them exactly as they appear in the output from the previously aborted
run. To restart from cobasis:
V#5 R#0 B#5 h=1 facets 3 4 5 det=1
enter:
restart 5 0 5 1 3 4 5
F#5 B#4 h=3 vertices/rays 2 3 4 5*
det= 8
1 0 0 -1
enter
restart 5 4 3 2 3 4 5
Note that if some cobasic index is followed
by a "*", then the index only, without the "*", is included in
the restart line.
Caution:
When restarting, output from the restart dictionary may be duplicated,
and the final totals of number of vertices/rays/facets may reflect this.
startingcobasis i_{1 }i_{2 }i
... i_{n-1}
This allows the user to specify a known cobasis
for beginning the reverse search. i_{1
}i_{2 }i ... i_{n-1}_{ } is a list of the inequalities (for H-representation)
or vertices/rays (for V-representation) that define a cobasis. If it is
invalid, or this option is not specified, lrs will find its own
starting cobasis. For example, with cube.ine, the user can start at
vertex (-1,1,-1) by specifying:
startingcobasis 1 3 4
truncate // H-representation only
//
The reverse search tree is
truncated(pruned) whenever a new vertex is encountered. Note: This does note
necessarily produce the set of all vertices adjacent to the optimum
vertex in the polyhedron, but just a subset of them.
verbose
Print slightly more detailed
information about the run.
volume
// V-representation only //
voronoi
// V-representation only - place
immediately after end statement //
Arithmetic
Packages
(new in Version 4.0)
Version 4.0 comes with a choice of arithmetic packages. Currently
available are:
lrsmp
Extended precision arithmetic used in previous releases
lrslong Fixed
length long integer arithmetic. No overflow checking
but 5-10 times faster than lrsmp.
lrsgmp An
interface to GNU MP which must be installed first.
Runs 1-6 times faster than lrsmp on typical problems.
The standard make gives binaries lrs/redund with
lrsmp, and lrs1/redund1 with lrslong. The fixed integer package is
particularly useful with 64 bit machines, and fairly large
combinatorial problems (15-20 dimensions) have been correctly solved.
It may be useful for doing empirical work, eg. searching for polyhedra
with certain properties. Final results should always be checked using lrsmp. If you have GNU MP installed, "make
gmp" will produce binaries glrs/gredund using this library. It
may be necessary to edit the makefile to specify the path to gmp.
Estimation
The estimation feature of lrs allows estimates to be made of
the output size and running time. These are based on Knuth's technique
for estimating the size of backtracking trees, and are described in Avis and
Devroye(1994). The estimate is unbiased, that is the
expected value of the estimate is the actual value. To get an estimate
use the maxdepth option to limit the
search depth, and the estimates
option:
maxdepth d
estimates k
This will cause lrs to perform k random probes from each
node of the tree at depth d. k should be at least 1 and d at least
zero.
H-representation: If the input is an H-representation, the
program gives an unbiased estimate of the number of vertices and
rays in the V-representation, and the total number of bases that
will be computed by lrs. For the H-representation cube.ine,
the options maxdepth 1 and estimates 1 produce the output:
*Estimates: vertices=9
rays=0 bases=9
*Total number of tree nodes evaluated: 6
In this case the V-representation of the cube is estimated to have 9
vertices, and it is estimated that lrs will compute a total of
9
bases. The estimate was based on evaluating 6 tree nodes. Note:
The estimate for the number of rays may be an overestimate if the
polyhedron
is not a cone, since some rays may be duplicated in the output - see
subsection Output Duplication.
V-representation: If the input
is
a V-representation, the program gives an unbiased estimate of the
number of
facets in the H-representation, and the total number of bases that lrs
will compute. For V-representation cube.ext, the options maxdepth 0 and
estimates 3 produce the output:
*Estimates: facets=7 bases=8
*Total number of tree nodes evaluated: 7
In this cases it is estimated that the H-representation of the cube
will contain 7 facets, and it is estimated that lrs will
compute a total of 7 bases to find it. The estimate was formed by
evaluating 7 tree nodes. Note: The number of facets estimated
may be an overestimate if the polyhedron is not bounded - see
subsection Output Duplication.
Voronoi diagrams: Estimates for the number of Voronoi
vertices and Voronoi rays for a V-representation of a set of data
points may be obtained by combining the voronoi,
estimates and maxdepth options.
Repeated estimates: In order to get estimates with
different random
probes, lrs can be given a seed for the random number
generator. There
are two ways: an option and a command line argument.
seed n
The integer n is used as a seed for the random
number generator.
The command line argument is an integer n which will be the seed
and overrides a seed given as an option.
lrs n < filename
Using the estimator: The running time of lrs is
proportional to the number of bases, so an estimate of the number of
bases gives an easy way to estimate the running time for solving the
complete problem by lrs. For the case of polytopes that contain
the origin, a V-representation can be processed as an H-representation
and vice-versa (this is an application of duality). Hence facet
estimates for a V-representation can also be obtained by running the
problem as an H-representation with
the estimates option. The estimated number of vertices will be in this
case
be an unbiased estimate for the number of facets for the original
problem.
So running the estimator on the file cube.ext with the header set as
H-representation , maxdepth 0 and
estimates 3, we get the output:
*Estimates: vertices=5
rays=0 bases=9
*Total number of tree nodes evaluated: 8
Since the origin is an interior point, the
estimated number of vertices is an accurate estimate of the number of
facets of the H-representation of the cube. Similarly,
estimates for an input H-representation of a polytope containing
the origin
may be obtained by processing the file as a V-representation. The
output
will be essentially the same, but the number of bases computed may be
very
different, see the subsection H-
vs V-representation. For a large problem
of this type, it is useful to get estimates for the number of bases
that lrs will compute for both V- and H-representations, so
that simpler
problem can be chosen.
The estimates may also be used to judge the feasibility of solving
the problem using other codes. For example, any code that uses
triangulation/perturbation to resolve degeneracy will have trouble if
the number of bases is huge. Codes which must store all the output in
memory (currently all codes except reverse search methods such as lrs)
will have trouble if the estimated output size is huge.
Fourier Elimination
Tallman Nkgau has contributed a driver fourier that computes the
projection of a polyhedron given by its H-representation onto a
selected set of coordinates. The program can be compiled by
make fourier
and is run by the command
fourier file.ine [fileout]
file.ine is a standard H-representation that does not contain linearities.
Following the end statement, insert the option:
project t
a_{1 }... a_{t
}_{The output will be the polyhedron projected onto
the coordinates}_{ }a_{1 }... a_{t }_{ ,
each of which is a unique number betwen 1 and n.}_{
}
Nash
Equilibria
New in Version 4.2
All Nash equilibria (NE) for a two
person noncooperative game are computed using two interleaved reverse
search vertex enumeration steps.
The input for the problem are two m by n matrices A,B of integers or
rationals. The first player is the row player, the second is the column
player.
If row i and column j are played, player 1 receives A_{i,j} and
player 2 receives B_{i,j}. (Program
runs faster if m is <= n , see below.)
The easiest way to use the program nash is to first run setupnash on a
file containing:
m n
matrix A
matrix B
eg. the file game is for a game with m=3 n=2:
3 2
0 6
2 5
3 3
1 0
0 2
4 3
% setupnash game gane1 game2
produces two H-representations, game1 and game2, one for each player.
To get the equilibrium, run
% nash game1 game2
*nash:lrslib v.4.2, 2005.6.1(32bit,lrsmp.h)
*Copyright (C) 1995,2005, David Avis avis@cs.mcgill.ca
*Input taken from file game1
*Second input taken from file game2
***** 5 4 rational
2 1/3 2/3 4
1 2/3 1/3 0 2/3
2 2/3 1/3 3
1 0 1/3 2/3 8/3
2 1 0 3
1 0 0 1 4
*Number of equilibria found: 3
Each row beginning 1 is a strategy for the row player yielding a NE
with each row beginning 2 listed immediately above it.
The payoff for player 2 is the last number on the line beginning 1, and
vice versa.
Eg: first two lines of output: player 1 uses row probabilities 2/3 2/3
0 resulting in a payoff of 2/3 to player 2.
Player 2 uses column probabilities 1/3 2/3 yielding a payoff of 4 to
player 1.
Optionally, lower bounds on the payoff functions to either or both
players may be included.
To give a lower bound of r on the payoff for player 1 add the options
to file game2 (yes that is correct!)
To give a lower bound of r on the payoff for player 2 add the options
to file game1
dualperturb
maximize 0 0 .... 0 1
(n entries to be given)
bound r
( r is integer or rational)
If m is greater than n then the
program usually runs faster by transposing the players. This is
achieved by running:
% nash game2 game1
If you wish to construct the game1 and game2 files by hand, they are
fragile and should be done exactly as follows:
For player 1: eg. game1
One linearity in the last row
Identity matrix with additional final column 0
Transpose of payoff matrix for player 2 with final column 1
Last row is prob sum to one
For player 2: eg. game2
One linearity in the last row
Payoff matrix for player 1 with final column 1
Identity matrix with additional final column 0
Last row is prob sum to one
Corresponding to file game above we get
*game: player 1
H-representation
linearity 1 6
begin
6 5 rational
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 -1 0 -4 1
0 0 -2 -3 1
-1 1 1 1 0
end
*game: player 2
H-representation
linearity 1 6
begin
6 4 rational
0 0 -6 1
0 -2 -5 1
0 -3 -3 1
0 1 0 0
0 0 1 0
-1 1 1 0
end
Linear
Programming
( Revised
V4.2)
lrs can be used to solve linear programming
problems in rational arithmetic when the input is an
H-representation.
Use the option:
lponly
and one of the options maximize or minize:
maximize a_{0}
a_{1 }... a_{n-1}
// H-representation only //
simply maximizes the function a_{0} + a_{1 }x_{
1 }+ ... + a_{n-1} x_{n-1}
over the given polyhedron. A optimal vertex is given when it
exists, otherwise for unbounded solutions a vertex and ray is given. A
minimization will be performed if the following option is
specified:
minimize a_{0}
a_{1 }... a_{n-1}
// H-representation only //
To print the dictionary at a few key points also include the option:
verbose
New
in V4.2. Dual variables are now printed at
termination. If the linearity option is used, only a partial list of
dual variables will be given.
Dual variable y_{i} refers to inequality number i in the input.
Volume Computation
lrs can be used to compute the volume of a full
dimensional polytope given as a V-representation. The option
volume
// V-representation only //
will cause the volume to be computed. For input cube.ext, the output
is:
*Volume=8
If the volume option is applied
to an H-representation, the results are not predictable. If the option
is
applied to a V-representation of a polytope that is not full
dimensional, the volume of a projected polytope is computed. The
projection used is to the lexicographically smallest coordinate
subspace, see Avis,
Fukuda, Picozzi
(2002).
For polytopes given by a H-representation, it will first be
necessary to
compute the V-representation.
Voronoi Diagrams
lrs can be used the compute the V-vertices of a Voronoi diagram
of a set of data points in n-1 dimensional space. To do this we use a
standard lifting procedure (see, e.g., Edelsbrunner, "Algorithms in
Combinatorial Geometry," pp 296-297) . Each point is mapped to a half
space tangent to the parabaloid in n dimensions, by the mapping:
p_{1 } , p_{2 } , ...., p_{ n-1}
-> (p_{1 }^{ 2 }+
p_{2}^{2 }+ ... + p_{n-1}^{2 }
) - 2 p_{1} x_{ 1 } - 2 p_{2 } x_{2
}- .... - 2 p_{ n-1 }x_{n -1 } + x _{n}>=
0
lrs is applied to the H-representation so created. This
transformation is performed automatically for a V-representation if the
voronoi
// V-representation only - place
immediately after end statement //
option is specified.
Note: The input file must consist entirely of
data points (no rays), i.e.. there must be a one in column one of each
line. The volume option
should not be used, since the volume reported will not be the volume of
the original V-representation.
The output will consist of the Voronoi vertices (columns beginning with
a one) and Voronoi rays (columns beginning with zero) for the Voronoi
diagram defined on the data points. If the printcobasis option is given, the n "data points" indices produced will tell
which set of input data points corresponds to the given Voronoi vertex
or ray. In case of degeneracies, a given Voronoi vertex may be
generated by more than n of the input data points. In this case, use of
the allbases option will cause
all sets of n input data points corresponding to a Voronoi vertex
to be printed. For Voronoi rays, the immediately preceding
cobasis is
the cobasis of the the Voronoi vertex from which the ray
emanates. The
index followed by a * is the data point to drop in order to generate
the ray. If the geometric option
is given the correspondence between Voronoi rays and Voronoi vertices
will be produced automatically.
Example: Compute the Voronoi
diagram of the planar point set (0,0), (2,1), (1,2), (0,4), (4,0),
(4,4) (2,-4).
vor7-3
*6 Voronoi vertices and 5 rays
*7 input data points
V-representation
begin
7 3 integer
1 0 0
1 2 1
1 1 2
1 0 4
1 4 0
1 4 4
1 2 -4
end
voronoi
printcobasis
allbases
geometric
The output produced is
V-representation
begin
***** 3 rational
V#1 R#0 B#1 h=0 data points 1 5 7 det=64
1 2 -3/2
V#1 R#1 B#1 h=0 data points 1 5* 7 det=64
0 -2 -1 * 1 2 -3/2
V#1 R#2 B#1 h=0 data points 1* 5 7 det=64
0 2 -1 * 1 2 -3/2
V#1 R#2 B#2 h=1 data points 1 2 5 det=16
1 2 -3/2
V#2 R#2 B#3 h=2 data points 1 2 3 det=12
1 5/6 5/6
V#3 R#2 B#4 h=3 data points 1 3 4 det=16
1 -3/2 2
V#3 R#3 B#4 h=3 data points 1 3* 4 det=16
0 -1 0 * 1 -3/2 2
V#4 R#3 B#5 h=2 data points 2 5 6 det=32
1 15/4 2
V#4 R#4 B#5 h=2 data points 2* 5 6 det=32
0 1 0 * 1 15/4 2
V#5 R#4 B#6 h=3 data points 2 3 6 det=20
1 27/10 27/10
V#6 R#4 B#7 h=4 data points 3 4 6 det=32
1 2 15/4
V#6 R#5 B#7 h=4 data points 3* 4 6 det=32
0 0 1 * 1 2 15/4
end
The output contains 6 Voronoi vertices :
(2, -3/2), (5/6,5/6),(-3/2,2),(15/4,2),
(27/10,27/10), (2,15/4).
The Voronoi vertex (2,-3/2) appears twice in the
output with data point indices 1 5 7 and 1 2 5. This means
that it is degenerate and is defined by the set of 4 input data point
in
positions 1,2,5,7 in the input file. I.e.. it is the centre of an
empty
circle through the four input data points (0,0), (2,1), 4,0),
(2,-4). The other Voronoi vertices appear once each and are
defined respectively by the data points with
indices (i.e.. position in the input file) 1 2 3, 1 3
4, 2 5 6, 2 3 6 and 3 4 6. The Voronoi diagram has 5
rays
(2, -3/2) + (-2t,-t),
(2,-3/2)+(2t,-t), (-3/2,2)+(-t,0),
(15/4,2)+(t,0), (2,15/4)+(0,t)
For example, the first ray in the output
appears:
V#1 R#1 B#1 h=0 data points 1 5* 7 det=64
0 -2 -1 * 1 2 -3/2
This means that the ray (-2t,-t) emanates
from the vertex defined by data points 1 5 7, namely (2, -3/2). The
asterisk on index 5 indicates that the ray is defined by the data
points with indices 5 and 7, namely (0,0) and (2,-4).
Extreme Point Enumeration and Redundant Inequalities
A convex hull problem that occurs frequently is to enumerate the
extreme points (vertices) of a given set of input points. This problem
is in fact much simpler than the problem of finding the facets of the
given input point set. It can be solved by linear programming.
The dual problem is to remove redundant inequalities from an
H-representation. An input inequality is redundant if it can be
deleted without changing the polyhedron. The program redund also
solves these problems. They can be solved by cdd using the
vertex_listing and facet_listing options.
To remove input points that are not vertices from a V-representation
or redundant inequalities from an H-representation use the command:
The resulting file can be used directly with lrs,
or even piped into lrs. In fact, lrs works best if the input is
non-redundant, see the section Redundancy
vs Degeneracy.
Note: Versions of redund prior to this release failed to remove
redundancy from the starting basis.
Linearities
(New in Version 4.0)
linearity k i_{1 }i_{2
}i ... i_{k}
The input file contains k linearities. If the input is a
H-representation, the rows i_{1 } i_{2
}i ... i_{k }of the input file are
equations. For a V-representation, the rows with these indices should
begin with zero in column one, and will be interpreted as lines rather
than rays. Linearities defined on the input vertices of a
V-representation are not defined, but the program will accept them and
produce some output. Each of the indice i_{k}
must be a distinct number between 1
and m. With an
H-representation, linearities are useful for enumeration of vertices on
a facet or lower dimensional subspace. For example the file:
cube_ridge
*cube of side 2 centred at the origin
H-representation
linearity 2 1 5
begin
6 4 rational
1 1 0 0
1 0 1 0
1 0 0 1
1 -1 0 0
1 0 -1 0
1 0 0 -1
end
causes vertices to be enumerated on the
ridge which
is the intersection of the two facets
x_{1} = -1
and x_{2} = 1
so the output is the pair of vertices
cube_ridge
*Input linearity in row(s) 1
5
V-representation
begin
2 4 rational
1 -1 1 1
1 -1 1 -1
end
Specifying linearities in this way will often produce
redundancy , especially if the dimension of the problem is reduced
considerably.
As a preprocessing step, it is useful to apply to remove any redundancy
by redund. In the case of the above problem the output
produced by redund is:
cube
*Input linearity in row(s) 1
5
*row 2 was redundant and removed
*row 4 was redundant and removed
H-representation
linearity 2 1 2
begin
4 4 rational
1 1 0 0
1 0 -1 0
1 0 0 1
1 0 0 -1
and two redundant halfspaces were removed.
Redundant columns are closely related to
linearities. If we examine the V-representation of cube_ridge above we
can see that it is just a line segment in 3 dimensional space.
Further, columns 2 and 3 are multiples of column 1. If lrs is
applied to this file, the column redundancies give rise to two
linearities, so the output will appear as the H-representation given
above: geometrically the intersection of two planes (the linearities)
with two half-planes (defining the endpoints of the line segment).
In general, the representation of the
linearity space is not unique, however the one produced by lrs should
be the same as that produced by cdd.
Timing and Interrupts
lrs handles certain signals unless it is compiled with the
-DOMIT_SIGNALS option. It is possible to interrupt lrs and get
the latest cobasis, which can be used for restarting the program
(useful if the machine is going down!)
signal
operation
USR1
print current cobasis and continue
TERM
print current cobasis and terminate
INT
(ctrl-C)
ditto
HUP
ditto
lrs also provides timing information, unless compiled with the
option -DOMIT_TIMES.
Error Messages and Troubleshooting
The most common error occurs from an incorrect input file
specification, please check the section File
Formats carefully. In particular, lrs does not check the
type or number of input coefficients specified. After the line
m n rational
you must specify exactly m*n rational or
integer coefficients. They are read in free format , but
normally each input facet or vertex/ray is begun on a new line.
See note for cdd users.
The following error messages are produced by lrs . They
are arranged in alphabetic order.
Data type must be integer of rational
lrs does not handle
floating point data, change to integer or rational input.
Digits must be at most 2295 Change
MAX_DIGITS and recompile
The digits option was specified, but the number
of decimal digits is too large (the values shown here is for 64
bit machines). MAX_DIGITS (default 255) is the maximum
number of array locations used for extended precision arithmetic. This
value should be increased and lrs recompiled.
Input Polyhedron does not have full dimension
If input is a cone, change to
H-representation, or add the origin 1 0 0 ... 0
The input polyhedron does not have dimension
n-1. Either there is a mistake in the input, or it must be projected
onto a full dimensional subspace. cdd
has a function for doing this. The second message only appears
for V-representations - note that at least one vertex must
be supplied, or else the problem can be run as a H-representation.
Invalid Co-basis - does not have correct
rank
An attempt to restart from
an invalid cobasis has been made. Check that the indices are entered
exactly as they appear in the previous aborted run.
Maximize/minimize only valid for
H-representation
LP operations can only be performed on
H-representations.
No begin line
No data in file
No feasible solution
The input is an H-representation of an
infeasible system.
Starting cobasis indices must be distinct and
in range 1 .. m
The startingcobasis option
has been used, but the indices supplied were not valid: i.e. distinct
numbers between 1..m.
Trying to restart from infeasible dictionary
An attempt to restart from
an invalid cobasis has been made. Check that the indices are entered
exactly in the order appear in the previous aborted run.
Hints and Comments
H-
vs V- representation
lrs is programmed to manipulate
H-representations directly. A file presented as a V-representation is
processed by lifting it to a cone in one higher dimension, which is
treated internally as a H-representation. If the input file is a
polytope which contains the origin, then the user has two options.
Submit it as a V-representation and have it processed as just
described, or submit it as a H-representation, and interpret the output
as a list of facet inequalities rather than "vertices". Since this will
not be lifted, it will be processed in a different way by lrs.
Sometimes a degenerate V-representation may run more quickly as a
H-representation, and sometimes more slowly. To decide which
representation to use for a large problem, the user can run the estimates option and
choose the representation with fewest estimated bases.
Redundancy vs Degeneracy
For an H-representation, an input is redundant if some inequality can
be deleted without changing the polyhedron. It is degenerate if (in d
dimensions) at least one vertex lies on d+1 or more facets.
Similarly in a V-representation an input is redundant if some input
point is not a vertex of the convex hull. It is degenerate if
some facet contains d+1 or more input points. The
options printcobasis
and incidence give degeneracy
information. Degeneracy causes pivot or triangulation based
methods such as lrs to run slowly. Redundancy is one
cause of degeneracy, but it can be avoided by pre-processing the input
files. See section
Extreme Point Enumeration and Redundant Inequalities for
instructions
on how to do this. This pre-processing is unnecessary if it is known
that
the input is non-redundant.
Even with redundant input removed a polyhedron may be highly
degenerate. In directory ine/metric there
are many highly degenerate combinatorial polytopes. These are difficult
problems for all vertex enumeration/convex hull programs that use
pivoting, such as lrs. For example, the file ccc7.ine
is a cone with 63 facets in 21 dimensions. It has 38,780 extreme rays,
but computing these required the evaluation of 247,271,659 bases!
Memory considerations
The strong point of lrs is that it does
not save the output produced, so in theory it cannot run out of
memory. With cache size one all memory is allocated at the
beginning, so if lrs starts running it will not run out of
memory. It is possible however that the number of digits required to do
the calculations exceeds the amount specified on the digits option, or the
default. In practice, this problem will also arise early in the
computation. In any case, a message is printed and the calculation can
be restarted. In order to improve performance, some dictionaries should
be cached. The default of 10 can be overridden by the cacheoption. If the
dictionary is in the cache it does not need to be recomputed when
backtracking, reducing processing time by about 40%. Since the
cache is allocated dynamically,
a cache size that is too large can potentially use up large ammounts of
machine memory.
Geometric Rays
A minimum V-representation of a polyhedron is a minimum set of vertices
and rays such that each point in the polyhedron can be expressed as a
convex combination of vertices plus a non-negative combination of rays.
For the cube, if we delete the inequality
x_{3} <= 1, i.e.. the line 1 0 0 -1 from file cube.ine,
we get the output:
V-representation
***** 4 rational
1 1 1 -1
0 0 0 1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 -1
end
indicating the polyhedron is the convex combination of 4 vertices and 1
ray. With the geometric option, we
get the output:
V-representation
begin
***** 4 rational
1 1 1 -1
0 0 0 1 * 1 1 1 -1
1 -1 1 -1
0 0 0 1 * 1 -1 1 -1
1 1 -1 -1
0 0 0 1 * 1 1 -1 -1
1 -1 -1 -1
0 0 0 1 * 1 -1 -1 -1
end
This indicates that geometrically, the polyhedron has 4 parallel
extreme rays (0,0,t) , one incident to each vertex. With the geometric option, all rays will be
printed. Without
the option, lrs tries to print each ray once, but
in some cases duplicates will remain, see subsection Output
Duplication.
Output Duplication
For degenerate inputs, pivot based methods such as lrs may
generate the same output vertex/ray/facet many times. Unless the allbases option is specified, lrs
makes checks in order to remove duplicates. An output is only
printed when it occurs with a lexicographically minimum basis. This
removes all duplicate vertices, but rays/facets may still be output
more than once. This is due to the fact that duplicate geometric rays
cannot always be detected. A warning message is produced when
duplicates may occur in the output. They can be removed using the
program buffer.c. Two important types of input never produce
duplicate output: polytopes (i.e. bounded polyhedra) and cones (i.e.
polyhedra where the origin is the only vertex).
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. Debugging would have been almost impossible without the use
of his program cdd as
a benchmark. David Bremner implemented memory allocation, cacheing and
signals. Ambros Marzetta demonstrated the importance of cacheing and
lrslong is based on his earlier implementation of this as
prs_single. 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 and Andreas Enge helped debug the
volume
computation. Tallman Nkgau contributed fourier.
D. Avis, lrs: A Revised Implementation of the Reverse Search Vertex
Enumeration Algorithm,
http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps
In: Polytopes - Combinatorics and Computation, Ed. G.
Kalai and G. Ziegler, Birkhauser-Verlag (2000) 177-198.
D. Avis, "Computational Experience with the Reverse Search Vertex
Enumeration Algorithm," Optimization Methods and Software, (1998 (to
appear)).
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
In: Information Processing Letters, (2000) V. 73, pp. 137-143.
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. Avis, K. Fukuda and S. Picozzi, "On Canonical Representations of
Convex Polyhedra", Mathematical Software, ICMS 2002, Ed. A.
Cohen, X-S Gao, N. Takayama, World Scientific, pp.350-360 (2002)
http://cgm.cs.mcgill.ca/~avis/doc/avis/AFP02a.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. http://www.cs.unb.ca/profs/bremner/pd/