'\" t .\" Title: LRSLIB .\" Author: [FIXME: author] [see http://docbook.sf.net/el/author] .\" Generator: DocBook XSL Stylesheets v1.78.1 .\" Date: 03/20/2016 .\" Manual: lrslib 0.42b .\" Source: July 2009 .\" Language: English .\" .TH "LRSLIB" "1" "03/20/2016" "July 2009" "lrslib 0\&.42b" .\" ----------------------------------------------------------------- .\" * Define some portability stuff .\" ----------------------------------------------------------------- .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .\" http://bugs.debian.org/507673 .\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" ----------------------------------------------------------------- .\" * set default formatting .\" ----------------------------------------------------------------- .\" disable hyphenation .nh .\" disable justification (adjust text to left margin only) .ad l .\" ----------------------------------------------------------------- .\" * MAIN CONTENT STARTS HERE * .\" ----------------------------------------------------------------- .SH "NAME" lrslib \- Convert between represetations of convex polyhedra\&. .SH "SYNOPSIS" .HP \w'\fBlrs\ input\&.ine\fR\ 'u \fBlrs input\&.ine\fR .HP \w'\fBlrs\ input\&.ine\ |\ lrsbuffer\fR\ 'u \fBlrs input\&.ine | lrsbuffer\fR .HP \w'\fBlrsfourier\ file\&.ine\ [fileout]\fR\ 'u \fBlrsfourier file\&.ine [fileout]\fR .HP \w'\fBredund\ input\&.ine\fR\ 'u \fBredund input\&.ine\fR .SH "DESCRIPTION" .PP A polyhedron can be described by a list of inequalities (\fIH\-representation)\fR or as by a list of its vertices and extreme rays (\fIV\-representation)\fR\&. \fIlrs\fR 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 \fIvertex enumeration\fR and \fIconvex hull problems\fR\&. .sp .if n \{\ .RS 4 .\} .nf .fi .if n \{\ .RE .\} .sp Fukuda\*(Aqs \m[blue]\fBFAQ page\fR\m[]\&\s-2\u[1]\d\s+2 \ \& contains a more detailed introduction to the problem, along with many useful tips for the new user\&. .PP \fIlrsbuffer\fR can remove some duplicate output\&. \fIredund\fR finds redundant inequalities in the input\&. .SH "FILE FORMATS" .PP File formats were developed jointly with Komei Fukuda and are compatible with \m[blue]\fBcdd\fR\m[]\&\s-2\u[2]\d\s+2\&. .PP The input for \fIlrs\fR is a H\- or V\- representation of a polytope\&. .sp .if n \{\ .RS 4 .\} .nf name {representation line} {options} {\m[blue]\fBlinearities\fR\m[]\&\s-2\u[3]\d\s+2} begin m n rational {input matrix} end {options} .fi .if n \{\ .RE .\} .sp \fIname\fR 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 "#"\&. .PP \fIname\fR is a user supplied name for the polytope\&.\ \& \fIrepresentation line\fR 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\&. .SS "H\-representation" .PP 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 .PP a0 + a1x1+ \&.\&.\&. + an\-1 xn\-1 >=\ \& 0\&. .PP This inequality is input as the line .PP a0 a1\&.\&.\&. an\-1 .PP The coefficients can be entered as integers or rationals in the format x/y\&. .SS "V\-representation" .PP 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 .PP 1\ \&\ \& v0\ \&\ \& v 1\&.\&.\&.\ \&\ \& vn\-1 \ \& .PP Each ray is given in the form .PP 0\ \&\ \& r0\ \&\ \& r 1\&.\&.\&.\ \&\ \& rn\-1 .PP where r0\ \&\ \& r 1\&.\&.\&.\ \&\ \& rn\-1is a point on the ray\&. .PP 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\&. .PP \fBNote for cdd users\fR: \fIlrs\fR uses essentially the same file format as \fIcdd\fR\&. Files prepared for \fIcdd\fR should work with little or no modification\&. Note that\ \& the V\-representation corresponds to the "hull" option in \fIcdd\fR\&. Options specific to \fIcdd\fR can be left in the input files and will be ignored by \fIlrs\fR\&.\ \& Note the input files for \fIlrs\fR are read in free format, after the line \fBm n rational\fR, \fIlrs\fR will look for exactly m*n rationals or integers separated by white space (blank,\ \& carriage return, tab etc\&.)\&. \fIlrs\fR will not "drop" extra columns of input if n is less than the number of columns supplied\&. .SS "Basic Options" .PP Almost all options are placed \fBafter\fR the end statement, maintaining compatibility with \fIcdd\fR\&. Where this is not the case, it will be mentioned explicitly\&. .PP \fBallbases\fR This option instructs \fIlrs\fR to list each vertex (or facet) for each of its bases\&. \m[blue]\fBOutput Duplication\fR\m[]\&\s-2\u[4]\d\s+2\m[blue]\fB\&.\fR\m[]\&\s-2\u[5]\d\s+2 This option is often combined with printcobasis\&. .PP \fBbound\ \& x \fR 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\&. .PP \fBcache n\fR\fIlrs\fR stores the latest\ \& n dictionaries in the reverse search tree\&. This speeds up the backtracking step, but requires more memory\&. .PP \fBdebug\ \& startingbasis endingbasis\fRPrint out cryptic but detailed trace, dictionaries etc\&. starting at #B=startingbasis and ending at #B=endingbasis\&. \fBdebug 0 0\fR gives a complete trace\&. .PP \fBdigits n\fR\fI placed before the begin statement\fR 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)\&. .PP \fBdualperturb\fR 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\&. .PP \fBestimates k\fR Estimate the output size\&. Used in conjunction with maxdepth \- see \m[blue]\fBEstimation\&.\fR\m[]\&\s-2\u[6]\d\s+2 \ \& .PP \fBgeometric\ \&\ \&\fR // 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 \m[blue]\fBHints and Comments\fR\m[]\&\s-2\u[5]\d\s+2 \&. .PP \fBincidence\fRThis option automatically switches on \fBprintcobasis\fR , 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\&. .PP \fB#incidence\fRThe same as printcobasis\&. Included for compatability with \fIcdd\&.\fR .PP \fBlinearity\ \& k\ \& i\fR\fB1\fR\fBi\fR\fB2\fR\fB i \&.\&.\&. i\fR\fBk\fRThe input contains k linearities in rows \fBi\fR\fB1\fR\fBi\fR\fB2\fR\fBi \&.\&.\&. i\fR\fBk\fRof the input file are equations\&. See \m[blue]\fBLinearities\&.\fR\m[]\&\s-2\u[3]\d\s+2 .PP \fBmaxdepth k\fR 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 \m[blue]\fBEstimation\&.\fR\m[]\&\s-2\u[6]\d\s+2\fBNote\fR: For H\-representations, rays at depth k will not be reported\&. For V\-representations, facets at depth k will not be reported\&. .PP \fBmaximize\ \&\fR\fBa\fR\fB0\fR\fB a\fR\fB1\fR\fB\&.\&.\&. a\fR\fBn\-1\fR\ \& // H\-representation\ \& only // .PP \fBminimize\ \&\ \&\fR\fBa\fR\fB0\fR\fB a\fR\fB1\fR\fB\&.\&.\&. a\fR\fBn\-1\fR // 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\ \& \m[blue]\fBLinear Programming\fR\m[]\&\s-2\u[7]\d\s+2 .PP \fI maxoutput n\fR Limits number of output lines produced (either vertices+rays or facets) to n .PP \fBmindepth k\fR \ \&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\&. .PP \fBnonnegative\fR // 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)\&. .PP \fBprintcobasis\ \& k;\fRModified in lrs 4\&.0 Every k\*(Aqth 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\&. \fBH\-representation:\ \&\fRIf 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\ \& \fBincidence\fR 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 \fBallbases\fRoption is used, all cobases will be printed out\&. \fBV\-representation\fR: If the input is a V\-representation, the cobasis is a list of the input vertices /rays that define the current facet\&. See option \fBincidence\fR above for more information\&. To initiate \fIlrs\fR from this facet all 4 indices must be given in this order (omit the *)\&. .PP \fBprintslack\fR 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\&. \fBproject\fR Used by \m[blue]\fBlrsfourier\fR\m[]\&\s-2\u[8]\d\s+2 only\&. .PP \fBrestart\ \& V# R# B# depth {facet #s or vertex/ray #s\fR} Modified in lrs4\&.0 \fIlrs\fR 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 \fBprintcobasis\fR option\&.\ \& The \fBorder of the indices is very important,\fR enter them exactly as they appear in the output from the previously aborted run\&. .PP Note that if some cobasic index is followed by a "*",\ \& then the index only, without the "*", is included in the restart line\&. \fBCaution:\fR When restarting, output from the restart dictionary may be duplicated, and the final totals of number of vertices/rays/facets may reflect this\&. .PP \fBstartingcobasis i\fR\fB1\fR\fBi\fR\fB2\fR\fBi \&.\&.\&. i\fR\fBn\-1\fR This allows the user to specify a known cobasis for beginning the reverse search\&. \fBi\fR\fB1\fR\fBi\fR\fB2\fR\fBi \&.\&.\&. i\fR\fBn\-1\fR\fB\fR 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, \fIlrs\fR 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\&. .PP \fBverbose\fRPrint slightly more detailed information about the run\&. .PP \fBvolume\fR // V\-representation\ \& only // Compute volume \- see section \m[blue]\fBVolume Computation\&.\fR\m[]\&\s-2\u[9]\d\s+2 .PP \fBvoronoi\fR // V\-representation\ \& only \- place immediately after end statement // Compute Voronoi diagram \- see section \m[blue]\fBVoronoi Diagrams\&.\fR\m[]\&\s-2\u[10]\d\s+2 .SH "NOTES" .IP " 1." 4 FAQ page .RS 4 \%http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html .RE .IP " 2." 4 cdd .RS 4 \%http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html .RE .IP " 3." 4 linearities .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities .RE .IP " 4." 4 Output Duplication .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplication .RE .IP " 5." 4 . .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments .RE .IP " 6." 4 Estimation. .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation .RE .IP " 7." 4 Linear Programming .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming .RE .IP " 8." 4 lrsfourier .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier .RE .IP " 9." 4 Volume Computation. .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation .RE .IP "10." 4 Voronoi Diagrams. .RS 4 \%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams .RE