Man Linux: Main Page and Category List

lrslib - Convert between represetations of convex polyhedra.

lrsinput.inelrsinput.ine|lrsbufferlrsfourierfile.ine[fileout]redundinput.ine

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).lrsis a C program that converts a H-representation of a polyhedron to its V-representation, and vice versa. These problems are known respectively at thevertexenumerationandconvexhullproblems. Fukuda'sFAQpage[1] contains a more detailed introduction to the problem, along with many useful tips for the new user.lrsbuffercan remove some duplicate output.redundfinds redundant inequalities in the input.

File formats were developed jointly with Komei Fukuda and are compatible withcdd[2]. The input forlrsis a H- or V- representation of a polytope. name {representation line} {options} {linearities[3]} begin m n rational {input matrix} end {options}nameis 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 "#".nameis a user supplied name for the polytope.representationlineis 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-representationThe 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-representationThe 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.Noteforcddusers:lrsuses essentially the same file format ascdd. Files prepared forcddshould work with little or no modification. Note that the V-representation corresponds to the "hull" option incdd. Options specific tocddcan be left in the input files and will be ignored bylrs. Note the input files forlrsare read in free format, after the linemnrational,lrswill look for exactly m*n rationals or integers separated by white space (blank, carriage return, tab etc.).lrswill not "drop" extra columns of input if n is less than the number of columns supplied.BasicOptionsAlmost all options are placedafterthe end statement, maintaining compatibility withcdd. Where this is not the case, it will be mentioned explicitly.allbasesThis option instructslrsto list each vertex (or facet) for each of its bases.OutputDuplication[4].[5] This option is often combined with printcobasis.boundxUse 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.cachenlrsstores the latest n dictionaries in the reverse search tree. This speeds up the backtracking step, but requires more memory.debugstartingbasisendingbasisPrint out cryptic but detailed trace, dictionaries etc. starting at #B=startingbasis and ending at #B=endingbasis.debug00gives a complete trace.digitsnplacedbeforethebeginstatementn 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).dualperturbIf 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.estimateskEstimate the output size. Used in conjunction with maxdepth - seeEstimation.[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 inHintsandComments[5] .incidenceThis option automatically switches onprintcobasis, 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 withcdd.linearityki1i2i...ikThe input contains k linearities in rowsi1i2i...ikof the input file are equations. SeeLinearities.[3]maxdepthkThe 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 - seeEstimation.[6]Note: For H-representations, rays at depth k will not be reported. For V-representations, facets at depth k will not be reported.maximizea0a1...an-1// H-representation only //minimizea0a1...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 andLinearProgramming[7]maxoutputnLimits number of output lines produced (either vertices+rays or facets) to nmindepthkBacktracking 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).printcobasisk;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 optionincidenceabove 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 theallbasesoption 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 optionincidenceabove for more information. To initiatelrsfrom this facet all 4 indices must be given in this order (omit the *).printslackNew 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.projectUsed bylrsfourier[8] only.restartV#R#B#depth{facet#sorvertex/ray#s} Modified in lrs4.0lrscan be restarted from any known cobasis. The calculation will proceed to normal termination. All of the information is contained in the output from aprintcobasisoption. Theorderoftheindicesisveryimportant,enter them exactly as they appear in the output from the previously aborted run.startingcobasisi1i2i...in-1This allows the user to specify a known cobasis for beginning the reverse search.i1i2i...in-1is 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,lrswill 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 sectionVolumeComputation.[9]voronoi// V-representation only - place immediately after end statement // Compute Voronoi diagram - see sectionVoronoiDiagrams.[10]

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