## 4 An Integer Linear Programming Formulation for the MCSP  
In this section, we develop an exponential-sized integer linear programming formulation for the MCSP. Unless not stated otherwise, throughout this section we will assume that \(A\) is a generic \(m\times n\) nonnegative integer matrix.  
Let \(D=(V,\mathcal{A})\) be the combined partition network associated to \(A\) and let \(\mathcal{P}_{i}\) be the set of all of the \(s-t\) paths whose internal vertices belong to the subnetwork \(D_{i}=(V_{i},\mathcal{A}_{i})\), for all \(i\in[m]\). We associate to each path \(p\in\mathcal{P}_{i}\), \(i\in[m]\), a length vector \(\ell(p)\) of dimension \(H=||A||_{\max}=\max\{a_{ij}\}\) obtained by summing over the lengths of the arcs belonging to \(p\):  
\[\ell(p):=\sum_{\alpha\in p}\ell(\alpha) \tag{32}\]  
where \(\{\ell(\alpha)\}\) are the length vectors defined in Section 3. Let \(\lambda_{p}^{i}\) be a decision variable equal to 1 if path \(p\in\mathcal{P}_{i}\), \(i\in[m]\), is considered in the optimal solution to the problem and 0 otherwise. Finally, let \(d_{w}\) be an integer variable equal to the number of segments with a coefficient \(w\) needed to decompose the matrix \(A\). Then, a possible integer linear programming formulation for the MCSP is:  
**Formulation 1**.: _- Integer Master Problem (IMP)_  
\[\min\sum_{w=1}^{H}d_{w} \tag{33a}\] \[s.t. d_{w}\geq\sum_{p\in\mathcal{P}_{i}}\ell_{w}(p)\;\lambda_{p}^{i} \quad\forall i\in[m]\,,\forall w\in[H]\] (33b) \[\sum_{p\in\mathcal{P}_{i}}\lambda_{p}^{i}=1 \quad\forall i\in[m]\] (33c) \[\lambda_{p}^{i}\in\{0,1\} \quad\forall i\in[m],\;\forall p\in\mathcal{P}_{i}\] (33d) \[d_{w}\in\mathbb{Z}_{+} \quad\forall w\in[H] \tag{33e}\]  
The objective function Equation (33a) accounts for the number of segments involved in the decomposition of the matrix \(A\). Constraints Equation (33b) impose that for each row \(i\in[m]\), the number of segments with coefficient \(w\) has to be greater than or equal to \(\max_{i\in[m]}\{\sum_{\alpha\in p_{i}}\ell_{w}(\alpha)\}\), which corresponds to the \(w\)-th component of the length vector associated to the \(s-t\) flow in \(D\). Constraints Equation (33c) impose to choose exactly one path in each partition network \(D_{i}\). Finally, constraints Equations (33d) and (33e) impose the integrality constraint on the considered variables. The validity of Formulation 1 is guaranteed by the transformation described in Section 3. It is worth noting that we need not to impose the integrality constraint on variables \(d_{w}\). In fact, it is easy to see that in an optimal solution to IMP, the integrality of variables \(\lambda_{p}^{i}\) together with Equation (33b) suffice to guarantee the integrality of variables \(d_{w}\). Formulation 1 includes an exponential number of (path) variables and a number of constraints that grows pseudo-polynomially in function of \(H\). A possible approach to solve it consists of using column generation and branch-and-price techniques [23].  
In order to study the pricing oracle, consider the following formulation:  
Then, determining the existence of a path violating Equation (35b) implies to check whether the shortest \(s-t\) path in \(D_{i}^{*}\) has an overall length shorter than \(\mu_{i}^{*}\), _i.e._, to check if it holds that  
\[\sum_{w=1}^{H}\pi_{i,w}^{*}\ell_{w}(\hat{p})<\mu_{i}^{*}. \tag{39}\]  
Since all length values are nonnegative, this task can be performed by using a standard implementation of [PERSON]'s algorithm [22].