azove - Another Zero One Vertex Enumeration tool

0/1 Vertex Enumeration and Counting

azove is a tool designed for counting (without explicit enumeration) and enumeration of 0/1 vertices.
Given a polytope by a linear relaxation or facet description P = {x | Ax <= b}, all 0/1 points lying in P can be counted or enumerated. This is done by intersecting the polytope P with the unit-hypercube [0,1] ^d. The integral vertices (no fractional ones) of this intersection will be enumerated. If P is a 0/1 polytope, azove solves the vertex enumeration problem. In fact it can also solve the 0/1 knapsack problem and the 0/1 subset sum problem.

Downloads

There exist two versions of azove, 1.1 and 2.0, which are based on different approaches. You should probably try both for your problems. As a rule of thumb, the more constraints a problem has the more likely it is suited for version 2.0.
azove 1.1 can be downloaded here: azove-1.1.tar.gz
For the compilation of version 1.1 the CUDD (CU Decision Diagram Package) Library is needed. Version 2.4.1 of CUDD can be downloaded here: cudd-2.4.1.tar.gz
azove 2.0 can be downloaded here: azove-2.0.tar.gz
No external library for managing BDDs is needed for version 2.0.

Algorithms

azove uses BDDs (binary decision diagrams) as datastructure for the representation of 0/1 points. When the BDD for a given system of linear inequations Ax <= b was built, counting the 0/1 points can be done in linear time in the number of nodes of the BDD. Enumeration of all 0/1 points is done by traversing all paths of the graph representation of the BDD that lead from the root node to the leaf 1 node.
The algorithm used in version 1.1 is described in the paper 0/1 vertex and facet enumeration with BDDs which was accepted at the Workshop on Algorithm Engineering and Experiments (ALENEX'07), New Orleans, U.S.A., January 2007.
The algorithm implemented in version 2.0 is described in the paper On Threshold BDDs and the Optimal Variable Ordering Problem which was accepted at the First International Conference on Combinatorial Optimization and Applications (COCOA'07), Xi'an, China, August 2007.

Input

Input files have to be in the .ine format (H-representation) which is used by tools like lrs and cdd.
A file format description can be found in the lrs user guide and the cdd user guide.
Equations given with 'linearity' are supported. Only 'integer' is allowed as numbertype.

Examples

stein27.ine is an example file that was converted to .ine format from the stein27 instance which can be found in the MIPLIB 3.0. Its matrix A consists only of 0 and 1 entries (which is not necessary for azove!) and describes a polytope lying in the unit-hypercube with fractional and 0/1 vertices.
The invocation:
azove -c stein27.ine
counts the number of 0/1 vertices which is in this case 367525. With
azove stein27.ine
all 0/1 vertices will be enumerated. The output is given in .ext format.
OA:8-25.ine is another example file that was converted and can be found among the polymake examples of 0/1-polytopes. In contrast to stein27 its matrix A and the right-hand-side b consist of general integers. The polytope has 25 vertices.