Provided by: lrslib_0.51-2_amd64 bug

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.

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

       lrsbuffer can remove some duplicate output.  redund finds redundant inequalities in the
       input.

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}

       name is a user supplied name for the polytope.  Comments may appear before the begin or
       after the end, and to avoid interpretation as an option, should begin with a special
       character such as "*" or "#".

       name is a user supplied name for the polytope.  representation line is either
       "H-representation" or "V-representation". If is omitted, 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
       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 //

       If used with lrs the starting vertex maximizes (or minimizes) the function  a0 + a1x1+ ...
       + an-1 xn-1.The dualperturb option may be needed to avoid dual degeneracy.See Nash
       Equilibria and  Linear Programming[7]

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

       mindepth k  Backtracking will be terminated at depth k, for k a non-negative integer. This
       can be used for running reverse search on subtrees as separate processes, e.g. in a
       distributed computing environment.

       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. To test everything it
       is necessary to enter the nonnegativity constraints explicitly in the input file. (In Ver
       4.1, the origin must be a vertex).

       printcobasis  k;Modified in lrs 4.0 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: If the input is an H-representation the cobasis is a list the indices of
       the inequalities from the input file that define the current vertex or ray. See option
       incidence above for more information. For rays, a cobasis is also printed. In this case
       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. Alternatively, if the allbasesoption is used, all cobases will be printed out.
       V-representation: If the input is a V-representation, the cobasis is a list of the input
       vertices /rays that define the current facet. See option incidence above for more
       information. To initiate lrs from this facet all 4 indices must be given in this order
       (omit the *).

       printslack New in Ver 4.2 ; // Use with H-representation // lrs prints 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 xi which is positive.  project Used by
       lrsfourier[8] only.

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

       startingcobasis i1i2i ... in-1 This allows the user to specify a known cobasis for
       beginning the reverse search.  i1i2i ... in-1 is a list of the inequalities (for
       H-representation) or vertices/rays (for V-representation) that define a cobasis. If it is
       invalid, or this option is not specified, lrs will find its own starting cobasis.  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.

       verbosePrint slightly more detailed information about the run.

       volume // V-representation  only // Compute volume - see section Volume Computation.[9]

       voronoi // V-representation  only - place immediately after end statement // Compute
       Voronoi diagram - see section Voronoi Diagrams.[10]

NOTES

        1. FAQ page
           http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

        2. cdd
           http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

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

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

        5.
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

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

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

        8. lrsfourier
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

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

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