Overview
We formulate Shortest Hyperpaths as an integer linear program (ILP) based on a characterization of the problem in terms of superpaths.
We solve this ILP with a cutting plane algorithm that starts with an initial set of constraints that are a subset of those in the full ILP,
and iteratively adds violated constraints until a hyperpath is returned, which will always be provably optimal.
Variables
The variables of our ILP encode the hyperedges in a superpath \(F\). For every hyperedge \(e \in E\), there is a variable \(x_e\), which takes on integer values \(x_e \in \{0,1\}\). An assignment of values to these variables encodes a superpath \(F\) by \(x_e = 1\) iff \(e \in F\). We represent the collection of all variables in the ILP by a vector \(x = (x_e)e \in E\), where \(x \in \{0,1\}^{|E|}\).
Constraints
The constraints consist of one constraint for each \(s,t\)-cut, encoded by ensuring the indicator variables for edges crossing the cut sum to a value greater than 1.
Publications
The ILP formulation of the shortest hyperpath problem is 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.