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


		       SOFTWARE ANNOUNCEMENT
	     VERTEX ENUMERATION CODE FOR 0/1 POLYTOPES
	           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
from.

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

	http://www.math.tu-bs.de/mo/research/zerone.html


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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
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