max planck institut

informatik

informatik

**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

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.

**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 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.

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.

Copyright (C) 2006, 2007 by Markus Behle