0/1 Vertex Enumeration Code: zerOne 1.81

Marco Luebbecke marco at mo.math.nat.tu-bs.de
Thu Aug 26 11:04:45 PDT 1999

	           zerOne 1.81     NOW AVAILABLE  

Given the linear description P = {x | Ax <= b} of an arbitrary
polytope P contained in the unit hypercube {0 <= x <= 1}, zerOne lists
all vertices with all coordinates equal to zero or one. This is a
frequent (sub-)task when designing models or analyzing the associated
(integral) polytopes in combinatorial optimization and is usually done
by listing all vertices and filtering out the integral ones.

The linear description of the polytope P is provided in CPLEX' LP
format. The output is in PORTA's POI or POLYMAKE format in order to
facilitate the subsequent generation of the convex hull of all 0-1
vertices. zerOne itself is not made for listing facets!
Since zerOne is a special purpose implementation it is much faster
than general codes. The major benefit, however, is its memory usage
being independent of the output vertices. This remedies a drawback
inserting algorithms like the Double Description Method usually suffer

For further information on algorithm, input/output, and download
please check the zerOne web page at


Best regards,
Marco E. Luebbecke

Department of Mathematical Optimization          Phone: +49 531 391 7560
Braunschweig University of Technology              Fax: +49 531 391 7559
Pockelsstrasse 14		             Email: m.luebbecke at tu-bs.de
D-38106 Braunschweig, Germany       WWW: http://www.math.tu-bs.de/~marco

The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.

More information about the Compgeom-announce mailing list