1lrs(1) lrs 7.2 lrs(1)
2 Name
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 Synopsis
11 lrs [input-file] [output-file]
12 redund [input-file] [output-file]
14 fel [input-file] [output-file]
16 hvref/xvref [input-file]
18 Description
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 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 File formats
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 Options
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 and seed.
164 See: 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 is 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 maxcobases k
213 The search will be truncated after k cobases have been generated.
214 maxdepth k
217 The search will be truncated at depth k. All bases with depth less than
218 or equal to k will be computed. k is a non-negative integer, and this
219 option is used for estimates - see Estimation[3] Note: For
220 H-representations, rays at depth k will not be reported. For
221 V-representations, facets at depth k will not be reported.
222 maximize b a_1 ... a_{n-1}
224 minimize b a_1 ... a_{n-1}
225 (H-representation) The starting vertex maximizes (or minimizes) the
226 function b + a_1 x_1+ ... + a_{n-1} x_{n-1}.
227 The dualperturb option may be needed to avoid dual degeneracy. Often
228 used with lponly.
229 (V-representation, v.7.2) The input file row numbers
230 maximizing(minimizing) the function are output along with the optimum
231 value. Using verbose the optimizing lines are also printed. With
232 minimization a facet gives an optimum value of zero, a negative value
233 indicates infeasibility and a positive value indicates strong
234 redundancy.
235 maxoutput n
237 Limits number of output lines produced (either vertices+rays or facets)
238 to n
239 mindepth k
241 Backtracking will be terminated at depth k.
242 nonnegative (This option must come before the begin statement -
244 H-representation only) Bug: Can only be used if the origin is a
245 vertex of the polyhedron For problems where the input is an
246 H-representation of the form b+Ax>=0, x>=0 (ie. all variables
247 non-negative, all constraints inequalities) it is not necessary to give
248 the non-negative constraints explicitly if the nonnegative option is
249 used. This option cannot be used for V-representations, or with the
250 linearity option (in which case the linearities will be treated as
251 inequalities). This option may be used with redund , but the implied
252 nonnegativity constraints are not tested themselves for redundancy.
253 project k i_1 i_2 ... i_k (new in v7.2)
255 (H-representation) Project the polyhedron onto the k variables
256 corresponding to cols i_1 .. i_k using the Fourier-Motzkin method.
257 Column indices are between 1 and n-1 and column zero is automatically
258 retained. Variables not contained in the list are eliminated using a
259 heuristic which chooses the column which minimizes the product of the
260 number of positive and negative entries. Redundancy is removed after
261 each iteration using linear programming.
262 (V-representation) Extract the k given columns from the input matrix
263 and remove redundancies. Column indices are between 1 and n-1 and
264 column zero is automatically extracted (cf. extract where redundancies
265 are not removed).
266 The output as a valid lrs input file. See also eliminate and extract
267 printcobasis k
269 Every k-th cobasis is printed. If k is omitted, the cobasis is printed
270 for each vertex/ray/facet that is output. For a long run it is useful
271 to print the cobasis occasionally so that the program can be restarted
272 if necessary. H-representation: the cobasis is a list the indices of
273 the inequalities from the input file that define the current vertex or
274 ray. For rays the cobasis is the cobasis of the vertex from which the
275 ray emanates. One of the indices is starred, this indicates the
276 inequality to be dropped from the cobasis to define the ray. If the
277 allbases option is used, all cobases will be printed.
278 V-representation: the cobasis is a list of the input vertices/rays that
279 define the current facet. See option incidence for more information.
280 printslack (H-representation only) A list of the indices of the input
282 inequalities that are satisfied strictly for the current vertex, ie.
283 corresponding slack variable is positive. If nonnegative is set, the
284 list will also include indices n+i for each decision variable x_i which
285 is positive.
286 redund start end (new in v7.1)
288 Check input lines with line numbers from start to end and remove any
289 redundant lines.
290 redund 0 0 will check all input lines. See redund[7]
291 redund_list k i_1 i_2 ... i_k (new in v7.1)
293 Check the k input line numbers with indices i_1 i_2 ... i_k and remove
294 any redundant lines. See redund[7]
295 restart V# R# B# depth {facet #s or vertex/ray #s}
297 lrs can be restarted from any known cobasis. The calculation will
298 proceed to normal termination. All of the information is contained in
299 the output from a printcobasis option. The order of the indices is
300 very important, enter them exactly as they appear in the output from
301 the previously terminated run.
302 seed k
304 Set the random number generator seed=k. Used with estimates.
305 startingcobasis i_1 i_2 ... i_{n-1}
307 lrs will start from the given cobasis which which is a list of the
308 inequalities (for H-representation) or vertices/rays (for
309 V-representation) that define it. If it is invalid, or this option is
310 not specified, lrs will find its own starting cobasis.
311 truncate The reverse search tree is truncated(pruned) whenever a new
313 vertex is encountered. Note: This does note necessarily produce the set
314 of all vertices adjacent to the optimum vertex in the polyhedron, but
315 just a subset of them.
316 verbose Print slightly more detailed information about the run.
318 volume (V-representation only) Compute the volume and, if the verbose
320 option is also included, output a triangulation. See Volume
321 Computation[5]
322 voronoi (V-representation only - place immediately after end
324 statement)
325 Compute Voronoi diagram - see Voronoi Diagrams[6]
326 Arithmetic
328 From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow
329 checking, starting in 64bit integers, moving to 128bit (if available)
330 and then GMP. Overflow checking is conservative to improve
331 performance: eg. with 64 bit arithmetic, a*b triggers overflow if
332 either a or b is at least 2^31, and a+b triggers an overflow if either
333 a or b is at least 2^62. Typically problems that can be solved in
334 64bits run 3-4 times faster than with GMP and inputs solvable in
335 128bits run twice as fast as GMP.
336 Various arithmetic versions are available and can be built from the
338 makefile:
339 lrs1 Fixed length 64 bit integer arithmetic, terminates on overflow.
341 lrs2 Fixed length 128 bit integer arithmetic, terminates on overflow.
343 lrsmp Built in extended precision integer arithmetic, uses digits
345 option above.
346 lrsgmp GNU MP which must be installed first from https://gmplib.org/.
348 lrsflint FLINT hybrid arithmetic which must be installed first from
350 http://www.flintlib.org/
351 Examples
354 (1) Convert the H-representation of a cube given cube by 6 the six
355 inequalities
356 -1 <= x_i <= 1 , i=1,2,3 into its V-representation consisting of 8
357 vertices.
358 % cat cube.ine
360 cube.ine
361 H-representation
362 begin
363 6 4 rational
364 1 1 0 0
365 1 0 1 0
366 1 0 0 1
367 1 -1 0 0
368 1 0 0 -1
369 1 0 -1 0
370 end
371 % lrs cube.ine
373 *lrs:lrslib v.6.3 2018.4.11(64bit,lrslong.h,overflow checking)
375 *Input taken from file cube.ine
376 cube.ine
377 V-representation
378 begin
379 ***** 4 rational
380 1 1 1 1
381 1 -1 1 1
382 1 1 -1 1
383 1 -1 -1 1
384 1 1 1 -1
385 1 -1 1 -1
386 1 1 -1 -1
387 1 -1 -1 -1
388 end
389 *Totals: vertices=8 rays=0 bases=8 integer_vertices=8
390 (2) Compute the extreme points of a set of 10 points in R^3
392 % cat c.ext
394 V-representation
395 begin
396 10 4 rational
397 1 1 1 1
398 1 0 1 1
399 1 1/2 0 1/3
400 1 1 1 0
401 1 0 1 0
402 1 1 0 0
403 1 0 0 0
404 1 0 1/3 1/4
405 1 1 0 1
406 1 0 0 1
407 end
408 % redund c.ext
410 *redund:lrslib v.7.2 2020.6.8(64bit,lrslong.h,hybrid arithmetic)
412 *Input taken from c.ext
413 V-representation
414 begin
415 8 4 rational
416 1 1 1 1
417 1 0 1 1
418 1 1 1 0
419 1 0 1 0
420 1 1 0 0
421 1 0 0 0
422 1 1 0 1
423 1 0 0 1
424 end
425 *Input had 10 rows and 4 columns
426 * 2 redundant row(s) found:
427 3 8
428 Utilities
431 hvref/xref Cross reference listing between V- and H-representations
432 (new in v7.1)
433 In the example below we start from an H-representation of cube.ine but
435 the same steps apply to the V-representation cube.ext. It is
436 recommended to first remove any redundancies from the input file using
437 redund.
438 1. Add printcobasis and incidence options to cube.ine
440 % lrs cube.ine cube.ext
442 % xref cube.ext
443 2. Edit the output file cube.ext.x to insert a second line that
445 contains two integers
446 rows maxindex
448 where rows >= # output lines in cube.ext.x
450 maxindex >= # input lines in cube.ine
451 or just use 0 0 and run hvref, the output will tell you which values to
453 use.
454 % hvref cube.ext.x
456 Notes
460 1. FAQ page
461 https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
462 2. cdd
464 https://inf.ethz.ch/personal/fukudak/cdd_home/
465 3. Estimation.
467 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation
468 4. Linear Programming
470 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming
471 5. Volume Computation.
473 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation
474 6. Voronoi Diagrams.
476 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams
477 7. redund: extreme point enumeration and eliminating redundant
479 inequalities
480 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#redund
481 8. User's guide for lrslib
483 http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html
484 Author
486 David Avis <avis at cs dot mcgill dot ca >
487 See also
489 mplrs(1), lrslib(5), lrsnash(1)
490January 2022 2022.1.18 lrs(1)