1LRS(1) lrs 7.2 LRS(1)
2
6 lrs - Convert between representations of convex polyhedra, remove
7 redundant inequalities, convex hull computation, volume, triangulation,
8 solution to linear programs in exact precision.
9
11 lrs [input-file] [output-file]
12 redund [input-file] [output-file]
14 fel [input-file] [output-file]
16 hvref/xvref [input-file]
18
20 These programs are part of and must be compiled with lrslib which is a
21 C library. All computations are done in exact arithmetic.
22 A polyhedron can be described by a list of inequalities
24 (H-representation) or as by a list of its vertices and extreme rays
25 (V-representation).
26 lrs converts an H-representation of a polyhedron to its
28 V-representation and vice versa, known respectively as the vertex
29 enumeration and facet enumeration problems (see Example (1) below).
30 For V-representations the volume can be computed and a triangulation
31 produced. lrs can also be used to solve a linear program, remove
32 linearities from a system, and extract a subset of columns.
33 redund removes redundant inequalities in an input H-representation and
35 outputs the remaining inequalities. For a V-representation it outputs
36 all extreme points and extreme rays, often called the convex hull
37 problem. Both outputs can be piped directly into lrs. redund is a
38 link to lrs which performs these functions via the redund and
39 redund_list options. See Example (2) below.
40 fel projects an input H-representation onto a given set of variables
42 using Fourier-Motzkin elimination. For a V-representation it extracts
43 the specified columns. The output is non-redundant and can be can be
44 piped directly into lrs. fel is a link to lrs which performs these
45 functions via the eliminate and project options.
46 hvref/xvref produce a cross reference list between H- and V-
48 representations. See UTILITIES.
49 mplrs is Skip Jordan's parallel wrapper based on MPI for lrs/redund
51 using the same input and output formats. See: man mplrs
52 Fukuda's FAQ page[1] contains a more detailed introduction to the
54 problem, along with many useful tips for the new user. User's guide
55 for lsrslib[8]
56
59 File formats were developed jointly with Komei Fukuda and are
60 compatible with cdd/cddlib[2].
61 The input for lrs/redund is an H- or V-representation of a polyhedron.
62 name
64 H-representation [or V-representation]
65 {options}
66 {linearities}
67 begin
68 m n rational [or integer]
69 {input matrix}
70 end
71 {options}
72 name is a user supplied name for the polyhedron. Comments may appear
74 before the begin or after the end and should begin with a special
75 character such as "*".
76 If the representation is not specified H-representation is assumed.
78 The input coefficients are read in free format, and are not checked for
79 type. Coefficients are separated by white space. m is the number of
80 rows and n the number of columns of the input matrix.
81 H-representation
83 m is the number of input rows, each being an inequality or equation.
84 n is the number of input columns and d=n-1 is the dimension of the
85 input.
86 An inequality or equation of the form:
87 b + a_1 x_1 + ... + a_d x_d >= 0
89 b + a_1 x_1 + ... + a_d x_d = 0
91 is input as the line:
93 b a_1 ... a_d
95 The coefficients can be entered as integers or rationals in the format
97 x/y. To distinguish an equation a linearity option must be supplied
98 before the begin line (see below).
99 V-representation
101 m is the number of input rows, each being a vertex, ray or line.
102 n is the number of input columns and d=n-1 is dimension of the input.
103 Each vertex is given in the form:
104 1 v_1 v_1 ... v_d
106 Each ray is given in the form:
108 0 r_1 r_2... r_d
110 where r_1 ... r_d is a point on the ray.
112 There must be at least one vertex in each file. For bounded polyhedra
114 there will be no rays entered. The coefficients can be entered as
115 integers or rationals in the format x/y. An input line can be
116 specified as a ray and then included in the linearity option (see
117 below).
118 Note for cdd users: Note the input files for lrs are read in free
120 format. lrs will look for exactly m*n rationals or integers separated
121 by white space (blank, carriage return, tab etc.). lrs will not "drop"
122 extra columns of input if n is less than the number of columns
123 supplied.
124
127 Almost all options are placed after the end statement, maintaining
128 compatibility with cdd. Where this is not the case, it will be
129 mentioned explicitly.
130 allbases This option instructs lrs to list each vertex (or facet) for
132 each of its bases. This option is often combined with printcobasis.
133 bound x (H-representation only). Either the maximize or minimize
135 option should be selected. x is an integer or rational. For
136 maximization (resp. minimization) the reverse search tree is truncated
137 whenever the current objective value is less (resp. more) than x.
138 cache n (default n=50)
140 lrs stores the latest n dictionaries in the reverse search tree. This
141 speeds up the backtracking step, but requires more memory.
142 debug startingcobasis endingcobasis
144 Print out cryptic but detailed trace, dictionaries etc. starting at
145 #B=startingcobasis and ending at #B=endingcobasis. debug 0 0 gives a
146 complete trace.
147 digits n (lrsmp arithmetic only - placed before the begin statement)
149 n is the maximum number of decimal digits to be used. If this is
150 exceeded the program terminates with a message and can usually be
151 restarted with the restart option. The default is set to 100 digits.
152 At the end of a run a message is given informing the user of the
153 maximum integer size encountered.
154 dualperturb If lrs is executed with the maximize or minimize option,
156 the reverse search tree is rooted at an optimum vertex for this
157 function. If there are multiple optimum vertices, the output will
158 often not be complete. This option gives a small perturbation to the
159 objective to avoid this. A warning message is given if the starting
160 dictionary is dual degenerate.
161 estimates k
163 Estimate the output size. Used in conjunction with maxdepth. See:
164 Estimation[3]
165 eliminate k i_1 i_2 ... i_k (new in v7.2)
167 (H-representation) Eliminates k variables in an H-representation
168 corresponding to cols i_1 .. i_k by projection onto the remaining
169 variables using the Fourier-Motzkin method. Variables are eliminated
170 in the order given and redundancy is removed after each iteration.
171 (V-representation) Delete the k given columns from the input matrix and
172 remove redundancies (cf. extract where redundancies are not removed).
173 Column indices are between 1 and n-1 and column zero cannot be
174 eliminated. The output as a valid lrs input file. See also project
175 and extract
176 extract [ k i_1 i_2 ... i_k ] (new in v7.1)
178 (H-representation) A preprocessing step to remove linearities (if any)
179 in an H-representation and resize the A matrix. The output as a valid
180 lrs input file. The resulting file will not contain any equations but
181 may not be full dimensional as there may be additional linearities in
182 the remaining inequalities. Options in the input file are stripped.
183 The user can specify the k columns i_1 i_2 ... i_k to retain otherwise
184 if k=0 the columns are considered in the order 1,2,..n-1. Linear
185 dependent columns are skipped and additional indices are taken from
186 1,2,...,n-1 as necessary. If there are no linearities in the input
187 file the given columns are retained and the other ones are deleted.
188 (V-representation) Extract the given columns from the input file
189 outputing a valid lrs input file. Options are stripped.
190 geometric (H-representation or voronoi option only) Each ray is
192 printed together with the vertex with which it is incident.
193 incidence This option automatically switches on printcobasis. For
195 input H-representation, indices of all input inequalities that contain
196 the vertex/ray that is about to be output. For input V-representation,
197 indices of all input vertices/rays that lie on the facet that is about
198 to be output. A starred index indicates that this vertex is also in
199 the cobasis, but is not contained in the facet. It arises due to the
200 lifting operation used with input V-representations.
201 linearity k i_1 i_2 ... i_k
203 (H-representation) The k rows i_1 i_2 ... i_k of the input file
204 represent equations. (V-representation) The k rows, which should have
205 a zero in column 1, represent lines in space (rather than rays).
206 lponly Solve the LP given by the input H-representation with objective
208 function specified by the maximize or minimize options and terminate.
209 Use with verbose option to get dual variables. See: Linear
210 Programming[4]
211 maxdepth k
213 The search will be truncated at depth k. All bases with depth less than
214 or equal to k will be computed. k is a non-negative integer, and this
215 option is used for estimates - see Estimation[3] Note: For
216 H-representations, rays at depth k will not be reported. For
217 V-representations, facets at depth k will not be reported.
218 maximize b a_1 ... a_{n-1} (H-representation only)
220 minimize b a_1 ... a_{n-1} (H-representation only)
221 The starting vertex maximizes (or minimizes) the function b + a_1 x_1+
222 ... + a_{n-1} x_{n-1}.
223 The dualperturb option may be needed to avoid dual degeneracy.
224 maxoutput n
226 Limits number of output lines produced (either vertices+rays or facets)
227 to n
228 mindepth k
230 Backtracking will be terminated at depth k.
231 nonnegative (This option must come before the begin statement -
233 H-representation only) Bug: Can only be used if the origin is a
234 vertex of the polyhedron For problems where the input is an
235 H-representation of the form b+Ax>=0, x>=0 (ie. all variables
236 non-negative, all constraints inequalities) it is not necessary to give
237 the non-negative constraints explicitly if the nonnegative option is
238 used. This option cannot be used for V-representations, or with the
239 linearity option (in which case the linearities will be treated as
240 inequalities). This option may be used with redund , but the implied
241 nonnegativity constraints are not tested themselves for redundancy.
242 project k i_1 i_2 ... i_k (new in v7.2)
244 (H-representation) Project the polyhedron onto the k variables
245 corresponding to cols i_1 .. i_k using the Fourier-Motzkin method.
246 Column indices are between 1 and n-1 and column zero is automatically
247 retained. Variables not contained in the list are eliminated in
248 increasing order and redundancy is removed after each iteration.
249 (V-representation) Extract the k given columns from the input matrix
250 and remove redundancies. Column indices are between 1 and n-1 and
251 column zero is automatically extracted (cf. extract where redundancies
252 are not removed).
253 The output as a valid lrs input file. See also eliminate and extract
254 printcobasis k
256 Every k-th cobasis is printed. If k is omitted, the cobasis is printed
257 for each vertex/ray/facet that is output. For a long run it is useful
258 to print the cobasis occasionally so that the program can be restarted
259 if necessary. H-representation: the cobasis is a list the indices of
260 the inequalities from the input file that define the current vertex or
261 ray. For rays the cobasis is the cobasis of the vertex from which the
262 ray emanates. One of the indices is starred, this indicates the
263 inequality to be dropped from the cobasis to define the ray. If the
264 allbases option is used, all cobases will be printed.
265 V-representation: the cobasis is a list of the input vertices/rays that
266 define the current facet. See option incidence for more information.
267 printslack (H-representation only) A list of the indices of the input
269 inequalities that are satisfied strictly for the current vertex, ie.
270 corresponding slack variable is positive. If nonnegative is set, the
271 list will also include indices n+i for each decision variable x_i which
272 is positive.
273 redund start end (new in v7.1)
275 Check input lines with line numbers from start to end and remove any
276 redundant lines.
277 redund 0 0 will check all input lines. See redund[7]
278 redund_list k i_1 i_2 ... i_k (new in v7.1)
280 Check the k input line numbers with indices i_1 i_2 ... i_k and remove
281 any redundant lines. See redund[7]
282 restart V# R# B# depth {facet #s or vertex/ray #s}
284 lrs can be restarted from any known cobasis. The calculation will
285 proceed to normal termination. All of the information is contained in
286 the output from a printcobasis option. The order of the indices is
287 very important, enter them exactly as they appear in the output from
288 the previously terminated run.
289 startingcobasis i_1 i_2 ... i_{n-1}
291 lrs will start from the given cobasis which which is a list of the
292 inequalities (for H-representation) or vertices/rays (for
293 V-representation) that define it. If it is invalid, or this option is
294 not specified, lrs will find its own starting cobasis.
295 truncate The reverse search tree is truncated(pruned) whenever a new
297 vertex is encountered. Note: This does note necessarily produce the set
298 of all vertices adjacent to the optimum vertex in the polyhedron, but
299 just a subset of them.
300 verbose Print slightly more detailed information about the run.
302 volume (V-representation only) Compute the volume and, if the verbose
304 option is also included, output a triangulation. See Volume
305 Computation[5]
306 voronoi (V-representation only - place immediately after end
308 statement)
309 Compute Voronoi diagram - see Voronoi Diagrams[6]
310
312 From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow
313 checking, starting in 64bit integers, moving to 128bit (if available)
314 and then GMP. Overflow checking is conservative to improve
315 performance: eg. with 64 bit arithmetic, a*b triggers overflow if
316 either a or b is at least 2^31, and a+b triggers an overflow if either
317 a or b is at least 2^62. Typically problems that can be solved in
318 64bits run 3-4 times faster than with GMP and inputs solvable in
319 128bits run twice as fast as GMP.
320 Various arithmetic versions are available and can be built from the
322 makefile:
323 lrs1 Fixed length 64 bit integer arithmetic, terminates on overflow.
325 lrs2 Fixed length 128 bit integer arithmetic, terminates on overflow.
327 lrsmp Built in extended precision integer arithmetic, uses digits
329 option above.
330 lrsgmp GNU MP which must be installed first from https://gmplib.org/.
332 lrsflint FLINT hybrid arithmetic which must be installed first from
334 http://www.flintlib.org/
335
338 (1) Convert the H-representation of a cube given cube by 6 the six
339 inequalities
340 -1 <= x_i <= 1 , i=1,2,3 into its V-representation consisting of 8
341 vertices.
342 % cat cube.ine
344 cube.ine
345 H-representation
346 begin
347 6 4 rational
348 1 1 0 0
349 1 0 1 0
350 1 0 0 1
351 1 -1 0 0
352 1 0 0 -1
353 1 0 -1 0
354 end
355 % lrs cube.ine
357 *lrs:lrslib v.6.3 2018.4.11(64bit,lrslong.h,overflow checking)
359 *Input taken from file cube.ine
360 cube.ine
361 V-representation
362 begin
363 ***** 4 rational
364 1 1 1 1
365 1 -1 1 1
366 1 1 -1 1
367 1 -1 -1 1
368 1 1 1 -1
369 1 -1 1 -1
370 1 1 -1 -1
371 1 -1 -1 -1
372 end
373 *Totals: vertices=8 rays=0 bases=8 integer_vertices=8
374 (2) Compute the extreme points of a set of 10 points in R^3
376 % cat c.ext
378 V-representation
379 begin
380 10 4 rational
381 1 1 1 1
382 1 0 1 1
383 1 1/2 0 1/3
384 1 1 1 0
385 1 0 1 0
386 1 1 0 0
387 1 0 0 0
388 1 0 1/3 1/4
389 1 1 0 1
390 1 0 0 1
391 end
392 % redund c.ext
394 *redund:lrslib v.7.2 2020.6.8(64bit,lrslong.h,hybrid arithmetic)
396 *Input taken from c.ext
397 V-representation
398 begin
399 8 4 rational
400 1 1 1 1
401 1 0 1 1
402 1 1 1 0
403 1 0 1 0
404 1 1 0 0
405 1 0 0 0
406 1 1 0 1
407 1 0 0 1
408 end
409 *Input had 10 rows and 4 columns
410 * 2 redundant row(s) found:
411 3 8
412
415 hvref/xref Cross reference listing between V- and H-representations
416 (new in v7.1)
417 In the example below we start from an H-representation of cube.ine but
419 the same steps apply to the V-representation cube.ext. It is
420 recommended to first remove any redundancies from the input file using
421 redund.
422 1. Add printcobasis and incidence options to cube.ine
424 % lrs cube.ine cube.ext
426 % xref cube.ext
427 2. Edit the output file cube.ext.x to insert a second line that
429 contains two integers
430 rows maxindex
432 where rows >= # output lines in cube.ext.x
434 maxindex >= # input lines in cube.ine
435 or just use 0 0 and run hvref, the output will tell you which values to
437 use.
438 % hvref cube.ext.x
440
444 1. FAQ page
445 https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
446 2. cdd
448 https://inf.ethz.ch/personal/fukudak/cdd_home/
449 3. Estimation.
451 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation
452 4. Linear Programming
454 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming
455 5. Volume Computation.
457 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation
458 6. Voronoi Diagrams.
460 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams
461 7. redund: extreme point enumeration and eliminating redundant
463 inequalities
464 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#redund
465 8. User's guide for lrslib
467 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html
468
470 David Avis <avis at cs dot mcgill dot ca >
471
473 mplrs(1), lrslib(1), lrsnash(1)
474July 2020 2020.7.28 LRS(1)