Man Linux: Main Page and Category List

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 n lrs stores the latest  n dictionaries in the reverse search
       tree. This speeds up the backtracking step, but requires more memory.

       debug  startingbasis endingbasis Print 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] .

       incidence This 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.

       #incidence The same as printcobasis. Included for compatability with
       cdd.

       linearity  k  i1i2 i ... ik The 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.

       verbose Print 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