1LRS(1)                              lrs 7.2                             LRS(1)
2
3
4

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
13       redund [input-file] [output-file]
14
15       fel [input-file] [output-file]
16
17       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
23       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
27       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
34       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
41       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
47       hvref/xvref produce a cross reference list between H- and V-
48       representations.  See UTILITIES.
49
50       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
53       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
57

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
63        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
73       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
77       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
82   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
88       b + a_1 x_1 + ... + a_d x_d >=  0
89
90       b + a_1 x_1 + ... + a_d x_d =  0
91
92       is input as the line:
93
94       b  a_1 ... a_d
95
96       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
100   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
105       1   v_1   v_1  ... v_d
106
107       Each ray is given in the form:
108
109       0   r_1   r_2...   r_d
110
111       where r_1  ...   r_d  is a point on the ray.
112
113       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
119       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
125

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
131       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
134       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
139       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
143       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
148       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
155       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
162       estimates k
163       Estimate the output size. Used in conjunction with maxdepth.  See:
164       Estimation[3]
165
166       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
177       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
191       geometric   (H-representation  or voronoi option only) Each ray is
192       printed together with the vertex with which it is incident.
193
194       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
202       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
207       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
212       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
219       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
225       maxoutput n
226       Limits number of output lines produced (either vertices+rays or facets)
227       to n
228
229       mindepth k
230       Backtracking will be terminated at depth k.
231
232       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
243       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
255       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
268       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
274       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
279       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
283       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
290       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
296       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
301       verbose Print slightly more detailed information about the run.
302
303       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
307       voronoi (V-representation  only - place immediately after end
308       statement)
309       Compute Voronoi diagram - see Voronoi Diagrams[6]
310

ARITHMETIC

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
321       Various arithmetic versions are available and can be built from the
322       makefile:
323
324       lrs1   Fixed length 64 bit integer arithmetic, terminates on overflow.
325
326       lrs2   Fixed length 128 bit integer arithmetic, terminates on overflow.
327
328       lrsmp  Built in extended precision integer arithmetic, uses digits
329       option above.
330
331       lrsgmp  GNU MP which must be installed first from https://gmplib.org/.
332
333       lrsflint  FLINT hybrid arithmetic which must be installed first from
334       http://www.flintlib.org/
335
336

EXAMPLES

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
343        % 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
356        % lrs cube.ine
357
358        *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
375       (2) Compute the extreme points of a set of 10 points in R^3
376
377        % 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
393        % redund c.ext
394
395        *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
413

UTILITIES

415       hvref/xref   Cross reference listing between V- and H-representations
416       (new in v7.1)
417
418       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
423       1. Add  printcobasis and incidence options to cube.ine
424
425       % lrs cube.ine cube.ext
426       % xref cube.ext
427
428       2. Edit the output file  cube.ext.x to insert a second line that
429       contains two integers
430
431       rows maxindex
432
433       where rows >= # output lines in cube.ext.x
434             maxindex >= # input lines in cube.ine
435
436       or just use 0 0 and run hvref, the output will tell you which values to
437       use.
438
439       % hvref cube.ext.x
440
441
442

NOTES

444        1. FAQ page
445           https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
446
447        2. cdd
448           https://inf.ethz.ch/personal/fukudak/cdd_home/
449
450        3. Estimation.
451           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation
452
453        4. Linear Programming
454           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming
455
456        5. Volume Computation.
457           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation
458
459       6.  Voronoi Diagrams.
460           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams
461
462       7.  redund: extreme point enumeration and eliminating redundant
463           inequalities
464           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#redund
465
466       8.  User's guide for lrslib
467           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html
468

AUTHOR

470       David Avis <avis at cs dot mcgill dot ca >
471

SEE ALSO

473       mplrs(1), lrslib(1), lrsnash(1)
474
475
476
477July 2020                          2020.7.28                            LRS(1)
Impressum