Provided by: lrslib_0.71b-2.1build2_amd64 bug

NAME

       lrs  -   Convert between representations of convex polyhedra, remove redundant inequalities, convex hull
       computation, volume, triangulation, solution to linear programs in exact precision.

SYNOPSIS


       lrs [input-file] [output-file]

       redund [input-file] [output-file]

       fel [input-file] [output-file]

       hvref/xvref [input-file]

DESCRIPTION

       These programs are part of and must be compiled with lrslib which is a C library.  All computations are
       done in exact arithmetic.

       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 converts an H-representation of a polyhedron to its V-representation and vice versa, known
       respectively as the vertex enumeration and facet enumeration problems (see Example (1) below).  For V-
       representations the volume can be computed and a triangulation produced.  lrs can also be used to solve a
       linear program, remove linearities from a system, and extract a subset of columns.

       redund removes redundant inequalities in an input H-representation and outputs the remaining
       inequalities.  For a V-representation it outputs all extreme points and extreme rays, often called the
       convex hull problem.  Both outputs can be piped directly into lrs.  redund is a link to lrs which
       performs these functions via the redund and redund_list options. See Example (2) below.

       fel projects an input H-representation onto a given set of variables using Fourier-Motzkin elimination.
       For a V-representation it extracts the specified columns.  The output is non-redundant and can be can be
       piped directly into lrs.  fel is a link to lrs which performs these functions via the eliminate and
       project options.

       hvref/xvref produce a cross reference list between H- and V-representations.  See UTILITIES.

       mplrs is Skip Jordan's parallel wrapper based on MPI for lrs/redund using the same input and output
       formats.  See: man mplrs

       Fukuda's FAQ page[1] contains a more detailed introduction to the problem, along with many useful tips
       for the new user.  User's guide for lsrslib[8]

FILE FORMATS

       File formats were developed jointly with Komei Fukuda and are compatible with cdd/cddlib[2].
       The input for lrs/redund is an H- or V-representation of a polyhedron.

        name
        H-representation [or V-representation]
        {options}
        {linearities}
        begin
         m n rational [or integer]
        {input matrix}
        end
        {options}

       name is a user supplied name for the polyhedron.  Comments may appear before the begin or after the end
       and should begin with a special character such as "*".

       If the representation is not specified H-representation is assumed.  The input coefficients are read in
       free format, and are not checked for type. Coefficients are separated by white space. m is the number of
       rows and n the number of columns of the input matrix.

   H-representation
       m is the number of input rows, each being an inequality or equation.
       n is the number of input columns and d=n-1 is the dimension of the input.
       An inequality or equation of the form:

       b + a_1 x_1 + ... + a_d x_d >=  0

       b + a_1 x_1 + ... + a_d x_d =  0

       is input as the line:

       b  a_1 ... a_d

       The coefficients can be entered as integers or rationals in the format x/y.  To distinguish an equation a
       linearity option must be supplied before the begin line (see below).

   V-representation
       m is the number of input rows, each being a vertex, ray or line.
       n is the number of input columns and d=n-1 is dimension of the input.
       Each vertex is given in the form:

       1   v_1   v_1  ... v_d

       Each ray is given in the form:

       0   r_1   r_2...   r_d

       where r_1  ...   r_d  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.  An input line can be specified
       as a ray and then included in the linearity option (see below).

       Note for cdd users: Note the input files for lrs are read in free format.  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.

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.  This option is
       often combined with printcobasis.

       bound  x (H-representation only). 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     (default n=50)
       lrs stores the latest  n dictionaries in the reverse search tree. This speeds up the backtracking step,
       but requires more memory.

       debug  startingcobasis endingcobasis
       Print out cryptic but detailed trace, dictionaries etc. starting at #B=startingcobasis and ending at
       #B=endingcobasis. debug 0 0 gives a complete trace.

       digits n  (lrsmp arithmetic only - 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 and can usually be restarted with the restart option. The default is set to 100 digits.  At the
       end of a run a message is given informing the user of the maximum integer size encountered.

       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 multiple 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[3]

       eliminate  k   i_1 i_2 ... i_k            (new in v7.2)
       (H-representation) Eliminates k variables in an H-representation corresponding to cols i_1 .. i_k by
       projection onto the remaining variables using the Fourier-Motzkin method.  Variables are eliminated in
       the order given and redundancy is removed after each iteration.
       (V-representation) Delete the k given columns from the input matrix and remove redundancies (cf. extract
       where redundancies are not removed).
       Column indices are between 1 and n-1 and column zero cannot be eliminated.  The output as a valid lrs
       input file.  See also project and extract

       extract [ k   i_1 i_2 ... i_k ]           (new in v7.1)
       (H-representation) A preprocessing step to remove linearities (if any) in an H-representation and resize
       the A matrix.  The output as a valid lrs input file. The resulting file will not contain any equations
       but may not be full dimensional as there may be additional linearities in the remaining inequalities.
       Options in the input file are stripped.  The user can specify the k columns i_1 i_2 ... i_k to retain
       otherwise if k=0 the columns are considered in the order 1,2,..n-1.  Linear dependent columns are skipped
       and additional indices are taken from 1,2,...,n-1 as necessary.  If there are no linearities in the input
       file the given columns are retained and the other ones are deleted.
       (V-representation) Extract the given columns from the input file outputing a valid lrs input file.
       Options are stripped.

       geometric   (H-representation  or voronoi option only) Each ray is printed together with the vertex with
       which it is incident.

       incidence This option automatically switches on printcobasis.  For input H-representation, indices of all
       input inequalities that contain the vertex/ray that is about to be output.  For input V-representation,
       indices of all input vertices/rays that lie on the facet that is about to be output. A starred index
       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.

       linearity  k  i_1  i_2  ...  i_k
       (H-representation) The k rows  i_1  i_2  ...  i_k   of the input file represent  equations.  (V-
       representation) The k rows, which should have a zero in column 1, represent lines in space (rather than
       rays).

       lponly Solve the LP given by the input H-representation with objective function specified by the maximize
       or minimize options and terminate. Use with verbose option to get dual variables. See: Linear
       Programming[4]

       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[3] Note: For
       H-representations, rays at depth k will not be reported. For V-representations, facets at depth k will
       not be reported.

       maximize   b  a_1 ... a_{n-1}   (H-representation  only)
       minimize   b  a_1 ... a_{n-1}   (H-representation  only)
       The starting vertex maximizes (or minimizes) the function  b + a_1 x_1+ ... + a_{n-1} x_{n-1}.
       The dualperturb option may be needed to avoid dual degeneracy.

       maxoutput n
       Limits number of output lines produced (either vertices+rays or facets) to n

       mindepth k
       Backtracking will be terminated at depth k.

       nonnegative (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.

       project  k   i_1 i_2 ... i_k            (new in v7.2)
       (H-representation) Project the polyhedron onto the k variables corresponding to cols i_1 .. i_k using the
       Fourier-Motzkin method. Column  indices are between 1 and n-1 and column zero is automatically retained.
       Variables not contained in the list are eliminated in increasing order and redundancy is removed after
       each iteration.
       (V-representation) Extract the k given columns from the input matrix and remove redundancies. Column
       indices are between 1 and n-1 and column zero is automatically extracted (cf. extract where redundancies
       are not removed).
       The output as a valid lrs input file.  See also eliminate and extract

       printcobasis k
       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: the cobasis is a list the indices of the inequalities from the
       input file that define the current vertex or ray.  For rays 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.  If the allbases option is used, all cobases will be printed.
       V-representation: the cobasis is a list of the input vertices/rays that define the current facet.  See
       option incidence for more information.

       printslack (H-representation only) 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.

       redund start end                       (new in v7.1)
       Check input lines with line numbers from start to end and remove any redundant lines.
       redund 0 0  will check all input lines.  See redund[7]

       redund_list k   i_1 i_2 ... i_k            (new in v7.1)
       Check the k input line numbers with indices i_1 i_2 ... i_k and remove any redundant lines. See redund[7]

       restart  V# R# B# depth {facet #s or vertex/ray #s}
       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 terminated run.

       startingcobasis i_1  i_2  ...  i_{n-1}
       lrs will start from the given cobasis which  which is a list of the inequalities (for H-representation)
       or vertices/rays (for V-representation) that define it. If it is invalid, or this option is not
       specified, lrs will find its own starting cobasis.

       truncate   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) Compute the volume and, if the verbose option is also included, output a
       triangulation. See Volume Computation[5]

       voronoi (V-representation  only - place immediately after end statement)
       Compute Voronoi diagram - see Voronoi Diagrams[6]

ARITHMETIC

       From version 7.1 lrs/redund/mplrs use hybrid arithmetic with overflow checking, starting in 64bit
       integers, moving to 128bit (if available) and then GMP.  Overflow checking is conservative to improve
       performance: eg. with 64 bit arithmetic, a*b triggers overflow if either a or b is at least 2^31, and a+b
       triggers an overflow if either a or b is at least 2^62.  Typically problems that can be solved in 64bits
       run 3-4 times faster than with GMP and inputs solvable in 128bits run twice as fast as GMP.

       Various arithmetic versions are available and can be built from the makefile:

       lrs1   Fixed length 64 bit integer arithmetic, terminates on overflow.

       lrs2   Fixed length 128 bit integer arithmetic, terminates on overflow.

       lrsmp  Built in extended precision integer arithmetic, uses digits option above.

       lrsgmp  GNU MP which must be installed first from https://gmplib.org/.

       lrsflint  FLINT hybrid arithmetic which must be installed first from http://www.flintlib.org/

EXAMPLES

       (1) Convert the H-representation of a cube given cube by 6 the six inequalities
       -1 <= x_i <= 1 , i=1,2,3 into its V-representation consisting of 8 vertices.

        % cat cube.ine
        cube.ine
        H-representation
        begin
        6 4 rational
        1  1  0  0
        1  0  1  0
        1  0  0  1
        1 -1  0  0
        1  0  0 -1
        1  0 -1  0
        end

        % lrs cube.ine

        *lrs:lrslib v.6.3 2018.4.11(64bit,lrslong.h,overflow checking)
        *Input taken from file cube.ine
        cube.ine
        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
        *Totals: vertices=8 rays=0 bases=8 integer_vertices=8

       (2) Compute the extreme points of a set of 10 points in R^3

        % cat c.ext
        V-representation
        begin
        10 4 rational
        1  1  1  1
        1  0  1  1
        1 1/2 0 1/3
        1  1  1  0
        1  0  1  0
        1  1  0  0
        1  0  0  0
        1  0 1/3 1/4
        1  1  0  1
        1  0  0  1
        end

        % redund c.ext

        *redund:lrslib v.7.2 2020.6.8(64bit,lrslong.h,hybrid arithmetic)
        *Input taken from  c.ext
        V-representation
        begin
        8 4 rational
        1  1  1  1
        1  0  1  1
        1  1  1  0
        1  0  1  0
        1  1  0  0
        1  0  0  0
        1  1  0  1
        1  0  0  1
        end
        *Input had 10 rows and 4 columns
        * 2 redundant row(s) found:
        3 8

UTILITIES

       hvref/xref   Cross reference listing between V- and H-representations  (new in v7.1)

       In the example below we start from an H-representation of cube.ine but the same steps apply to the V-
       representation cube.ext.  It is recommended to first remove any redundancies from the input file using
       redund.

       1. Add  printcobasis and incidence options to cube.ine

       % lrs cube.ine cube.ext
       % xref cube.ext

       2. Edit the output file  cube.ext.x to insert a second line that contains two integers

       rows maxindex

       where rows >= # output lines in cube.ext.x
             maxindex >= # input lines in cube.ine

       or just use 0 0 and run hvref, the output will tell you which values to use.

       % hvref cube.ext.x

NOTES

        1. FAQ page
           https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html

        2. cdd
           https://inf.ethz.ch/personal/fukudak/cdd_home/

        3. Estimation.
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

        4. Linear Programming
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming

        5. Volume Computation.
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

       6.  Voronoi Diagrams.
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams

       7.  redund: extreme point enumeration and eliminating redundant inequalities
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#redund

       8.  User's guide for lrslib
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html

AUTHOR

       David Avis <avis at cs dot mcgill dot ca >

SEE ALSO

       mplrs(1), lrslib(1), lrsnash(1)

July 2020                                           2020.7.28                                             LRS(1)