This is the command lrslib that can be run in the OnWorks free hosting provider using one of our multiple free online workstations such as Ubuntu Online, Fedora Online, Windows online emulator or MAC OS online emulator

**PROGRAM:**

**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**

**...**

**ik**of 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

**allbases**option 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

Use lrslib online using onworks.net services