1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
|
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; Linux 2.2.12 i386) [Netscape]">
<title>User's Guide for lrs</title>
</head>
<body text="#000000" bgcolor="#FFFFFF" link="#0000EF" vlink="#55188A" alink="#FF0000">
<ul>
<h1>
lrslib programmer's guide Version 4.1</h1>
</ul>
June 20, 2001
Copyright(C) 2001 <a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.html">
lrs home page</a>
<br> David Avis
avis@cs.mcgill.ca <a href="http://cgm.cs.mcgill.ca/~avis">
http://cgm.cs.mcgill.ca/~avis</a>
<br>
<li>
<a href="#Introduction">Introduction</a></li>
<li>
<a href="#Installation Section">Installation</a></li>
<li>
<a href="#Demos">Demos</a></li>
<li>
<a href="http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html">User's
Manual</a></li>
<li>
<a href="#Acknowledgements">Acknowledgements and References</a></li>
<h3>
<hr WIDTH="100%"><a NAME="Introduction"></a>Introduction</h3>
lrslib consists of the following main components
<p><font color="#990000">Libraries:</font>
<p> lrslib: A callable library of functions implementing
lrs and redund
<br> lrsmp: An extended precision arithmetic package
for lrslib
<br> lrslong: A fixed precision integer package for lrslib
<br> lrsgmp: An interface for lrslib to the<a href="http://www.swox.com/gmp">
GNU MP</a> arithmetic package.
<p><font color="#990000">Main Drivers:</font>
<br> lrs.c:
Transform H-representation to V-representation or vice versa
<br> redund.c
Remove redundancies from H or V-representation
<p><font color="#990000">Demo drivers:</font>
<br> vedemo.c
Generate vertices of a set of hypercubes
<br> chdemo.c
Generate facets from a set of generated cyclic polytopes
<br> lpdemo.c
Solve a series of lp problems on generated cubes
<p><font color="#990000">Utilities:</font>
<br> buffer.c
Remove duplicates output (parallel geometric rays in unbounded non-pointed
polyhedra)
<p>The demo drivers use an "<i>lp-solve</i>" like procedures to construct
the input matrix (and objective function if needed). These programs should
be easily modifiable to solve similar problems for other polyhedra. Normally
all that is necessary is for the user to modify the procedure used to generate
the polyhedron: <i>makecube</i> in the case of <i>vedemo</i> and <i>makecyclic</i>
in the case of <i>chdemo</i>.
<p>For the moment, the only documentation I can offer for the main drivers
and library procedures are the comments in the individual programs. Consult
the User's manual for usage instructions.
<p>These programs can be distributed freely under the GNU GENERAL PUBLIC
LICENSE. Please read the file COPYING carefully before using. Please
inform the author of any interesting applications for which <i>lrs</i>
was helpful.
<h3>
<hr WIDTH="100%"><a NAME="Installation Section"></a>Installation</h3>
From <a href="http://cgm.cs.mcgill.ca/~avis/C/lrs.html">lrs home page</a>,
click on "Download" and retrieve the file lrslib-041.tar.gz
<br> Unpack with:
<br> % gunzip lrslib-041.tar.gz
<br> % tar xvf lrslib-041.tar
<p> Go to the new directory
<br> % cd lrslib-041
<br>
<h4>
Installation with built in arithmetic libraries.</h4>
make binaries by typing
<br> % make all
(most 32 bit unix machines)
<br> or
<br> % make all64
(64 bit integer machines such as DEC Alpha)
<br> or
<br> % make nosigs
( 32 bit machines without signals/timing routines)
<p> Test the program by typing:
lrs cube.ine
<br>
redund cubetop.ine
<p><b>Install demos.</b>
<p><b> </b>%make demo
<p> Test the programs by typing: vedemo,
chdemo, lpdemo or lpdemo1
<h4>
Installation with GNU MP library</h4>
To use the GNU MP library, it is necessary to first install it and record
its location. The
<br>default makefile assumes: /usr/local/include and /usr/local/lib for
headers and binaries
<br>respectively. Edit the gmp: section of "makefile" appropriately.
<p> make binaries by typing
<br> % make gmp
<p> Test the programs by typing: glrs
cube.ine
<br>
gredund cube.ine
<h3>
<hr WIDTH="100%"></h3>
<h3>
<a NAME="Demos"></a>Demos</h3>
Demo drivers that are designed for user modification are included with
this release:
<p>vedemo.c
vertex enumeration
<br>chdemo.c
facet enumeration
<br>lpdemo.c
linear programming
<hr WIDTH="100%">
<p><b>Main components of all demos</b>
<p>The main components of each demo are similar, and concern problem set
up, memory allocation and memory cleanup:
<p><font color="#990000"> long</font> <font color="#990000">lrs_init
(char *name); /* initialize lrslib and arithmetic
package for prog "name" */</font>
<blockquote>
<br><font color="#000000">This procedure is called once at the beginning
of the driver, and does basic setup functions. "name" will be output with
some information about version numer or lrslib and which arithmetic package
is used. FALSE is returned in case of failure.</font></blockquote>
<p><br><font color="#990000">lrs_dat *lrs_alloc_dat (char *name);
/* allocate for lrs_dat structure "name"
*/</font>
<br>
<blockquote><font color="#000000">This procedure produces a structure of
type lrs_dat (usually saved in variable Q) which has basically static information
about the problem. This includes a large number of flags and a few arrays
for indices. All flags are set at default values (see lrslib.h) but can
be overridden after the function has been called. A NULL pointer is returned
in case of failure. It is called once for each problem to be solved.</font></blockquote>
<p><br><font color="#990000">lrs_dic *lrs_alloc_dic (lrs_dat * Q);
/* allocate for lrs_dic structure corr. to Q */</font>
<br>
<blockquote><font color="#000000">This procedure produces a structure of
type lrs_dic (usually saved in variable P) which has basically dynamic
information about the problem. This includes mainly the dictionary matrix,
basic and cobasic indices and their row and column locations. For vertex
or facet enumeration additional lrs_dic structures are created automatically
and cached, to speed up backtracking. A NULL pointer is returned in case
of failure.</font></blockquote>
<p><br><font color="#990000">void lrs_free_dic ( lrs_dic *P, lrs_dat *Q);</font>
<blockquote><font color="#000000">Free the space allocated for lrs_dic
structures. This includes all cached structures. This procedure must be
called before lrs_free_dat. It should be called before starting a new problem.</font></blockquote>
<p><br><font color="#990000">void lrs_free_dat ( lrs_dat *Q);</font>
<blockquote><font color="#000000">Free the space allocated for lrs_dat
structure. It should be called before starting a new problem.</font></blockquote>
<font color="#990000">void lrs_close (char *name); /*
close lrs lib program "name"
*/</font>
<blockquote><font color="#000000">Final clean up. This is called once at
the end of the run.</font>
<hr WIDTH="100%"></blockquote>
<b><font color="#000000">Building the data matrix</font></b>
<p><font color="#000000">For an H-representation, the data for the problem
b+Ax >= 0 is entered row by row. This is illustrated in program </font><font color="#990000">makecube(lrs_dic
P, lrs_dat Q) </font><font color="#000000">(in vedemo.c).The procedure
for entering a row of data is:</font>
<p><font color="#990000">void lrs_set_row(lrs_dic *P, lrs_dat *Q, long
row, long num[], long den[], long ineq);</font>
<br>
<blockquote><font color="#000000">Here </font><font color="#990000">row</font><font color="#000000">
is the row number of the current row in the matrix, a long integer from
1 to </font><font color="#990000">Q->m</font><font color="#000000">. The
long arrays </font><font color="#990000">num[] </font><font color="#000000">and
</font><font color="#990000">den[]</font><font color="#000000">
contain the numerator and denominator coeficients, and have length </font><font color="#990000">Q->n</font><font color="#000000">.
The long integer </font><font color="#990000">ineq</font><font color="#000000">
is replaced by either </font><font color="#990000">GE</font><font color="#000000">
(TRUE) or </font><font color="#990000">EQ</font><font color="#000000">
(FALSE) to represent an inequality or equation respectively.</font></blockquote>
<font color="#000000">A V-representation is built in a similar way, as
illustrated in </font><font color="#990000">makecyclic(lrs_dic P, lrs_dat
Q) </font><font color="#000000">(in chdemo.c). This also makes use
of lrs_set_row. For a vertex, </font><font color="#990000">num[0]=1L</font><font color="#000000">,
and for an extreme ray or linearity </font><font color="#990000">num[0]=0L</font><font color="#000000">.
(In both cases </font><font color="#990000">den[0]=1L</font><font color="#000000">).
</font><font color="#990000">ineq</font><font color="#000000">
is TRUE for a vertex or extreme ray, and FALSE for a linearity.</font>
<p><font color="#000000">If an objective function is required (eg., linear
programming) it can be set up using:</font>
<p><font color="#990000">void lrs_set_obj(lrs_dic *P, lrs_dat *Q, long
num[], long den[], long max);</font>
<blockquote><font color="#000000">The long arrays </font><font color="#990000">num,
den</font><font color="#000000"> hold the objective function coeficients.
num[0] is a constant term. The long integer </font><font color="#990000">max</font><font color="#000000">
has values </font><font color="#990000">MAXIMIZE</font><font color="#000000">(TRUE)
or </font><font color="#990000">MINIMIZE(</font><font color="#000000">FALSE).</font></blockquote>
<font color="#000000">There are two additional procedures that perform
the same functions, but where the coefficients are given in lrs_mp format:</font>
<p><font color="#990000">void lrs_set_row_mp(lrs_dic *P, lrs_dat *Q, long
row, lrs_mp_vector num, lrs_mp_vector den, long ineq);</font>
<p><font color="#990000">void lrs_set_obj_mp(lrs_dic *P, lrs_dat *Q, lrs_mp_vector
num, lrs_mp_vector den, long max);</font>
<blockquote>
<hr WIDTH="100%"></blockquote>
<p><br><b><font color="#000000">Reverse search: vedemo and chdemo</font></b>
<p><font color="#000000">After constructing the input data, reverse search
is used to generate all vertices/rays(vedemo) or facets(chdemo). Unless
the tree search will be customized in some way, there is no need to change
this part of the demo programs. To</font>
<br><font color="#000000">begin a starting basis is found using:</font>
<p><font color="#990000">long lrs_getfirstbasis (lrs_dic ** P, lrs_dat
* Q, lrs_mp_matrix * Lin, long no_output);</font>
<blockquote><font color="#000000">If there are redundant columns in the
input data, a linearity space is computed and stored in matrix Lin. The
procedure returns</font></blockquote>
<font color="#990000">long lrs_getnextbasis (lrs_dic **P, lrs_dat * Q,
long prune);</font>
<blockquote><font color="#000000">This procedure returns FALSE when there
are no more bases to find. The variable prune can be set to TRUE to cause
the reverse search to prune the tree at the current vertex, ie. to backtrack
rather than going deeper in the tree.</font>
<hr WIDTH="100%"></blockquote>
<b><font color="#000000">Output extraction</font></b>
<p><font color="#000000">A dictionary potentially represents one vertex
and several extreme rays (vertex enumeration) or several facets (facet
enumeration). Due to degeneracy, the same vertex/ray/facet may be generated
several times. The procedure</font>
<p><font color="#990000">long lrs_getsolution (lrs_dic * P, lrs_dat * Q,
lrs_mp_vector output, long col);</font>
<p><font color="#000000">checks each column col of the dictionary to see
if it contains some output, and if so returns TRUE with </font><font color="#990000">output[]
</font><font color="#000000">containing
the respective integer coefficients. To avoid duplication, only the lexicographically
minimum representation of a given output is extracted by lrs_getsolution.
The output coefficients need to be divided by </font><font color="#990000">P->det</font><font color="#000000">
to get the correct rational output. This is done by the procedure</font>
<p><font color="#990000">void lrs_printoutput (lrs_dat * Q, lrs_mp_vector
output);</font>
<blockquote>
<hr WIDTH="100%"></blockquote>
<b><font color="#000000">Linear Programming</font></b>
<p><font color="#000000">The program lpdemo.c solves a set of linear programs
on hypercubes, using makecube to construct the constraint matrices. Once
the dictionary has been generated, a single call to</font>
<p><font color="#990000">long lrs_solvelp (lrs_dic * P, lrs_dat * Q, long
maximize);</font>
<p><font color="#000000">solves the linear program.</font>
<br>
<hr WIDTH="100%">
<h3>
<a NAME="Acknowledgements"></a>Acknowledgements and References</h3>
I would like to thank many people for helping with this implementation
project. Komei Fukuda encouraged me from the start, collaborated in designing
the file formats, and provided many suggestions for improving the code.
David Bremner implemented memory allocation, caching and signals. Jerry
Quinn coded the integer divide routine. Bug reports were provided by many
users, for which I thank them. In particular Gerardo Garbulsky's extensive
use of earlier versions suggested many refinements, Ambros Marzetta demonstrated
the importance of caching and Andreas Enge helped debug the volume computation.
Oleg Pikhurko convinced me of the need for the lp-solve like procedures
described in the Demos section.
<p>D. Avis, "lrs: A Revised Implementation of the Reverse Search
Vertex Enumeration Algorithm," In: Polytopes - Combinatorics and Computation,
G. Kalai & G. Ziegler eds., Birkhauser-Verlag, DMV Seminar Band 29,
pp. 177-198 (2000).
<br><a href="http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps">http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps</a>
<p>D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration
Algorithm," Optimization Methods and Software, Vol. 10, pp.107-124
(1998)
<br><a href="http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps">http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps</a>
<p>D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?,"
Computational Geometry: Theory and Applications, Vol 7,pp.265-301(1997).
<a href="http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps">http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps</a>
<p>D. Avis and L. Devroye, "Estimating the Number of Vertices of a Polyhedron,"
pp. 179-190 in Snapshots of Computational and Discrete Geometry, ed. D.
Avis and P. Bose, School of Computer Science, McGill University (1994).
<a href="http://cgm.cs.mcgill.ca/~avis/doc/avis/AD94a.ps">http://cgm.cs.mcgill.ca/~avis/doc/avis/AD94a.ps</a>
<p>D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex
Enumeration of Arrangements and Polyhedra," Discrete and Computational
Geometry, Vol. 8, pp. 295-313 (1992). <a href="http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps">http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps</a>
<p>D. Bremner, K. Fukuda and A. Marzetta, Primal-Dual Methods for Vertex
and Facet Enumeration, 13th ACM
<br>Symposium on Computational Geometry SCG 1997, 49-56.
</body>
</html>
|
