table of contents
other versions
- jessie 0.43-1
- jessie-backports 0.51-2~bpo8+1
- stretch 0.51-2+b1
- testing 0.62-2
- unstable 0.62-2
LRSLIB(1) | lrslib 0.42b | LRSLIB(1) |
NAME¶
lrslib - Convert between represetations of convex polyhedra.SYNOPSIS¶
lrs
input.ine
lrs
input.ine | lrsbuffer
lrsfourier
file.ine [fileout]
redund
input.ine
DESCRIPTION¶
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.FILE FORMATS¶
File formats were developed jointly with Komei Fukuda and are compatible with cdd[2]. The input for lrs is a H- or V- representation of a polytope.name {representation line} {options} { linearities[3]} begin m n rational {input matrix} end {options}
H-representation¶
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 a0 + a1x1+ ... + an-1 xn-1 >= 0. This inequality is input as the line a0 a1... an-1 The coefficients can be entered as integers or rationals in the format x/y.V-representation¶
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 v0 v 1... vn-1 Each ray is given in the form 0 r0 r 1... rn-1 where r0 r 1... rn-1is 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. 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¶
Almost all options are placed after the end statement, maintaining compatibility with cdd. Where this is not the case, it will be mentioned explicitly. allbases This option instructs lrs to list each vertex (or facet) for each of its bases. Output Duplication[4].[5] This option is often combined with printcobasis. bound x 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 nlrs stores the latest n dictionaries in the reverse search tree. This speeds up the backtracking step, but requires more memory. debug startingbasis endingbasisPrint 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). 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.[6] geometric // H-representation or voronoi option only // With this option, each ray is printed together with the vertex with which it is incident. For more information see Geometric Rays in Hints and Comments[5] . incidenceThis option automatically switches on printcobasis , so see below for a description of this option first. Can be used with printcobasis n. (Ver 4.2b) .PP 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. .PP For input V-representation, indices of all input vertices/rays that lie on the facet that is about to be output. A starred indexindicates 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. #incidenceThe same as printcobasis. Included for compatability with cdd. linearity k i1i2 i ... ikThe input contains k linearities in rows i1i2i ... ikof the input file are equations. See Linearities.[3] 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.[6]Note: For H-representations, rays at depth k will not be reported. For V-representations, facets at depth k will not be reported. maximize a0 a1... an-1 // H-representation only // minimize a0 a1... an-1 // H-representation only //NOTES¶
- 1.
- FAQ page
- 2.
- cdd
- 3.
- linearities
- 4.
- Output Duplication
- 5.
- 6.
- Estimation.
- 7.
- Linear Programming
- 8.
- lrsfourier
- 9.
- Volume Computation.
- 10.
- Voronoi Diagrams.
08/11/2013 | July 2009 |