0/1 vertex and facet enumeration with BDDs

In polyhedral studies of 0/1 polytopes two prominent problems exist. One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points. Another one is the convex hull problem: Given a set of 0/1 points in dimension d, enumerate the facets of the corresponding polytope. We present two new approaches for both problems. The novelty of our algorithms is the incorporation of binary decision diagrams (BDDs), a datastructure which has become very popular and effective in hardware verification and computational logic. Our computational results show the strength of our methods. We introduce our new tool azove which is currently the fastest software for counting and enumerating 0/1 points in a polytope.

Published in:
Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics, 158 - 165

 Record created 2008-05-13, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)