Home

This project is about an implementation of an algorithm that tests a matrix property called total unimodularity, which means that each subdeterminant is either -1, +1 or zero. It also tests for related properties like (strong) unimodularity and (strong) k-modularity which is related to the Dantzig property. For more about the theory of testing, take a look at the page about the implemented algorithm.

The current version is 1.2d. There are different types of releases:

• The default version which needs boost. It builds a binary and a C++ library: unimodularity-library-1.2d.tar.gz
• The noboost version doesn’t need boost but only builds the binary: unimodularity-library-noboost-1.2d.tar.gz
• There is a Polymake extension: unimodularity-library-Polymake-1.2d.tar.gz

The file format for the matrices looks as in the following example of a 3 × 6 matrix.

3 6

1 0 0 1 1 0

0 1 0 1 0 1

0 0 1 0 1 1

There are different ways to call the binary:

• The simplest way is `./src/unimodularity-test FILE_NAME`. It shows some progress and answers the question, whether the given matrix has the properties.
• If you want certificates for the result, you can add the ‘-c’ parameter. With that, a violating submatrix or a decomposition tree are printed for the total unimodularity test, according to the result.
• To control the verbosity, you can use ‘-v’ (which is useful for logging the output to a file or viewing in a pager) or ‘-q’ to omit the output completely.