Vertex Enumeration for 0-1 Polytopes
news
purpose
algorithm
author
warranty
example
future
Credits
news
purpose
algorithm
author
warranty
example
future
Credits
The linear description of P is provided in CPLEX' LP format where the problem type (LP, MIP) as well as the objective function are irrelevant. Variable bounds are assumed to define the respective unit hypercube and need not be stated explicitely. The output is in PORTA POI or POLYMAKE format in order to facilitate the subsequent generation of the convex hull of all 0-1 vertices, i.e. the desired facets of the integral polytope under consideration. POLYMAKE also allows for a great variety of analyzing the polytope. zerOne itself is not made for listing facets!
Basically, any CPLEX LP file is a valid input to zerOne but not all valid input is reasonable. You should be aware that polyhedra not entirely contained in the unit hypercube will be intersected with it, thus possibly producing new vertices! Only 0-1 vertices of the polytope will be listed. Although they may possibly be present, no vertices with fractional or integral coordinates different from zero or one will be in the output. By default, variable names in the LP file are expected to be x1, x2, ... If you have a different consecutive numbering use option -n. In case of arbitrary variable names use option -a. The PORTA POI output or the POLYMAKE output, respectively, is precisely in the original format you should be familiar with. Variables are consecutively numbered starting at one. A table reflecting the `translation' from input to output variable naming is printed using option -t. All output is directed to standard out.
Note: The dimension stated in the output equals the number of variables used in the input. You cannot deduce the dimension of the polytope.
This is the official web page. All updates and fixes will be announced here. You can also subscribe to the zerOne mailing list by sending an email to majordomo@mo.math.nat.tu-bs.de with the following lines in the body of the mail:
subscribe zerone
end
It should be noted again that zerOne is neither capable of computing the convex hull of a given set of vertices nor made for listing all vertices of the input polyhedron.
This program is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose. See the GNU General Public License for more details.
Given the input
max
x1+x2+x3+x4
st
+x2-x3-x4 <= 0
- x1 +x3-x4 <= 0
+ x1 -x3-x4 <= 0
-2x1+x2+x3-x4 <= 0
+x4 <= 1
+x3 <= 1
- x1+x2+x3 <= 1
-x3 <= 0
- x1 <= 0
-x2 <= 0
+x2 <= 1
+ x1 <= 1
+ x1-x2+x3+x4 <= 2
end
|
the output is on stdout (PORTA left column, POLYMAKE right column)
DIM = 4 AMBIENT_DIM
4
CONV_SECTION VERTICES
( 1) 0 0 0 0 1 0 0 0 0
( 2) 0 0 0 1 1 0 0 0 1
( 3) 0 0 1 1 1 0 0 1 1
( 4) 0 1 0 1 1 0 1 0 1
( 5) 1 0 0 1 1 1 0 0 1
( 6) 1 0 1 0 1 1 0 1 0
( 7) 1 1 0 1 1 1 1 0 1
( 8) 1 1 1 0 1 1 1 1 0
( 9) 1 1 1 1 1 1 1 1 1
END N_VERTICES
9
|