Unimodularity Library

The Unimodularity Library is a software library written in C++ that implements an efficient algorithm for testing total unimodularity, based on Seymour's decomposition theorem [1] for regular matroids. The algorithm runs in O( (n+m)^5 ) time and is a simplified version of the cubic algorithm of [2]. The algorithm can also test for the related properties of unimodularity and strong unimodularity.

The Unimodularity Library is published under the Boost Software License [3].

News (Changes, Bugfixes)

Version 1.2b (10/12/2012):
  • Fixed compilation error on Mac OS. Thanks to Yvon Sauvageau for reporting the problem.
Version 1.2 (04/13/2012):
  • Users of the Polymake extension can now analyze the matroid decomposition.
  • Updated package documentation (including the experiments' documentation).
  • This is the official version corresponding to our article in Mathematical Programming Computation.
Version 1.1 (02/09/2012):
  • A bug in the graphicness test in versions before 1.1 may cause a graphic matrix to be not recognized as such. Thanks to Paulo Seijas for reporting the problem.
  • Marc Pfetsch provided an update to make the extension compatible with Polymake version 2.11.
Version 1.0 (06/13/2011):
  • Released version 1.0 (the publication version).

Downloading and Installation of Unimodularity Library

  1. Get the files unimodularity-library-1.2b.tar.gz, which depends on the Boost Software Library (version 1.43.0 or later) [4]. If you don't have boost installed, get unimodularity-library-noboost-1.2b.tar.gz.
  2. Read the README file for instructions or simply try 
    ./configure
make
make install
    to install the software. The main binary is called unimodulary-test; it can be found in the src/ directory prior to installing.
  3. In publications, please cite the library as follows: 
    M. Walter and K. Truemper, Implementation of a Unimodularity Test. To be published by Springer, Mathematical Programming Computation, volume 5, number 1, 2013.
    Here is the bibtex entry.

Use of the Library

  1. For a first test of the program, create a file with the matrix: 
    5 4

1 0 0 1
1 1 0 0
0 1 1 0
0 0 1 1
1 1 1 1
    Then invoke unimodulary-test with the file name as the only argument. If you find out that your matrix is not t.u. and want to search for a violator, you should add the -c option.
  2. To use the library in C++, you need to create a boost::numeric::ublas::matrix<int> object and call the is_totally_unimodular function. There are different versions of this function if you want to obtain certificates for the answer.
    3. As an alternative, use the unimodularity extension for the Polymake system.

Experiments in the article "Implementation of a Unimodularity Test"

To repeat our experiments, fetch the test matrices article-experiments.tar.gz and follow the instructions in the README file.

References

[1] P. D. Seymour. Decomposition of regular matroids. J. Comb. Theory, Ser. B 28, 305-359, 1980.
[2] K. Truemper. A decomposition theory for matroids. V. Testing of matrix total unimodularity, J. Comb. Theory, Ser. B 49, 241-281, 1990.
[3] http://www.boost.org/LICENSE_1_0.txt