Exact and heuristic methods for tearing

Many of the implemented algorithms are described in the following academic papers:

• An exact method for the minimum feedback arc set problem
• Decomposition methods for solving nonlinear systems of equations (submitted)
• Ordering matrices to bordered lower triangular form with minimal border width (submitted)

See also Reproducing the results of the academic papers below.

The code is a work in progress

Some of the code will be contributed back to NetworkX wherever it is appropriate. The remaining part of the code will be released as a Python package on PyPI. In the meantime, the rpc_api.py is a good place to start looking. (rpc stands for remote procedure call; it can be called from Java or C++ through the json_io.py). The API in rpc_api.py takes a sparse matrix in coordinate format and returns the row and column permutation vectors.

Documentation of the demo application demo.py is available at sdopt-tearing.readthedocs.io.

While reading the code, please keep in mind that the code is a work in progress.

Reproducing the results of the minimum feedback arc set paper

The results of the paper An exact method for the minimum feedback arc set problem can be reproduced as follows.

Algorithms

• The grb_lop.py module implements the Integer programming formulation with triangle inequalities of Section 3.1. The grb_ prefix refers to Gurobi, the lop part to the linear ordering problem since these constraints were developed for solving that problem.
• The grb_set_cover.py module implements the Integer programming formulation as minimum set cover of Section 3.2.
• The grb_lazy.py provides the implementation of the proposed method, An integer programming approach with lazy constraint generation of Section 4.
• The procedure called Safely removing edges in Appendix A is implemented in grb_simplifier.py.

Input graphs

The test graphs are given in plain text files. The *.edges file gives the edge list of the graph; the *.mfes file gives the minimum feedback edge set. The *.cycles file gives those cycles that are sufficient to include in the cycle matrix in order to prove the optimality of the minimum feedback edge set, and the *.lp encodes the corresponding integer linear program (a minimum set cover problem) in CPLEX LP file format. The *.mst file gives the optimal solution vector of this integer program, and can be used as a starting point as well.

The cycles in the *.cycles file are given one per line, and each line gives the node list of one cycle. For example the line
1 6 8 encodes the cycle of the edges (1, 6), (6, 8), (8, 1).

The graphs used for benchmarking are given in the following files.

• Section 5.1. The easy test graphs for cross-checking correctness are given in the Python module benchmarks.py.
• Section 5.2. The sparse random graphs are given in benchmark_mfes/erdos_renyi.zip. The seeds 61 and 78 were skipped since they yielded random graphs with more than one strongly connected components for some of the ns.
• Section 5.3. The random tournaments for testing the worst-case behavior are given in benchmark_mfes/tournament.zip.
• Section 5.4. The challenging sparse graphs are given in benchmark_mfes/de_Bruijn.zip and in benchmark_mfes/Imase_Itoh.zip. The self-loops, if any, have been removed.

Reproducing the results of the paper on optimal tearing

The algorithms are documented in the academic paper Ordering matrices to bordered lower triangular form with minimal border width.

• The heap_md.py module implements a greedy heuristic for ordering to lower Hessenberg form.
• The ilp_tear.py module implements optimal tearing with integer programming.
• The bb4_tear.py module provides the custom branch and bound algorithm for optimal tearing.
• The names of selected test problems from the COCONUT Benchmark are under data/benchmark_tearing/. The results of the 12 runs are plotted in the following PDF files (but only for those problems that have at most 500 non-zero entries):
  Ordering the Jacobian of the equality constraints (33.8 MB) and
  Ordering the Jacobian of the first-order optimality conditions (49.3 MB).

The tests for checking correctness are in the test_<module name>.py modules. Cross-checking the ILP-based and the custom branch and bound algorithm is implemented in test_bb_ilp.py. Running these tests require Hypothesis, the QuickCheck for Python. (I am a big fan of property-based testing.)

Dependencies

The demo application has been tested with Python 2.7 and 3.5. The six, networkx, sympy, and namedlist packages are necessary; matplotlib, pydot (or pydot-ng), and pygraphviz are recommended but not required. However, if matplotlib is installed, then pydot (or pydot-ng) and pygraphviz are also required to run the demo.py application.

Computing the bipartite matching can easily become the bottleneck. In that case, MC21 from the Harwell Subroutine Library (HSL) is recommended. The wrapper code can be found under data/mc21/ with compilation instructions.

If you wish to run the exact algorithms based on integer programming, you will also need Gurobi. If you do not have Gurobi installed, the demo.py application will detect its absence, and simply skips those steps that would require the integer programming solver. The algorithms that use Gurobi have only been tested with Python 2.7.

Installing on Windows with PyGraphviz

Only Python 2.7 was tested on Mar 08, 2016. Python 2.7 and the dependencies were installed with Miniconda (released on Dec 17, 2015). Then graphviz was installed with the graphviz-2.38.msi installer. After installation the bin directory of graphviz was added to the PATH. Next, pygraphviz was installed from Unofficial Windows Binaries for Python Extension Packages as pip install pygraphviz-1.3.1-cp27-none-win32.whl. The matplotlib and pydot-ng packages were installed only after pygraphviz. The demo application works as expected.