Cutting plane algorithm

Overview

For a hypergraph of \(n\) vertices and \(m\) hyperedges, the integer linear program above has \(m\) variables and \(\Theta(2^n)\) constraints (corresponding to the number of \(s,t\)-cuts). Thus for a large hypergraph, we cannot even feasibly write down the corresponding ILP, due to its exponentially-many constraints. Nevertheless, we can actually compute optimal solutions to this full ILP in practice, even for very large inputs, using an approach known as a cutting plane algorithm.

Method

Our cutting plane algorithm proceeds as follows
  1. Let \(I\) be an initial subset of the inequalities in the full ILP, and \(S := I\) be the current set of inequalities for the algorithm.
  2. Solve the ILP restricted to the inequalities in \(S\), and let \(x^\star\) be the optimal solution to this current ILP.
  3. Find the set of vertices \(R\) reachable from \(s\) along hyperedges \(e\) with \(x^\star_e = 1\).
  4. If \(t \not \in R\), find new inequalities \(C\) given by \(s,t\)-cuts that are violated by \(x^\star\) and add these to the set of inequalities \(S\), and go back to Step (2).
  5. Otherwise, \(t \in R\). Halt and output the current solution \(x^\star\).
This starts with an initial set \(I\) of cut inequalities, and adds inequalities to this set as it finds cuts that solutions to prior ILPs do not cross.

Initial constraints

The cutting plane algorithm is seeded with a set of initial cut constraints based on the estimated distance to each vertex from the source (calculated by a hyperpath heuristic Hhugin). In addition to these distance-based cuts, we also add cuts that capture connectivity, minimality, and ensure the target is produced. These initial constraints significantly reduce the running time of the cutting plane algorithm.

Publications

The cutting plane algorithm and initial constraints are explained in more detail in the following publication, which should be cited under noteworthy use of Mmunin
  • Spencer Krieger. Algorithmic inference of cellular reaction pathways and protein secondary structure. Department of Computer Science, The University of Arizona, July 2022. link
  • Spencer Krieger and John Kececioglu. “Computing shortest hyperpaths for pathway inference in cellular reaction networks.” Proceedings of the 27th International Conference on Research in Computational Molecular Biology (RECOMB), Springer LBNI 13976, 155-173, 2023. link

Source code

Source code for Mmunin along with documentation will be available on GitHub.