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.