Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.