## 2 The One Row Restriction of the MCSP as a Network Optimization Problem  
In this section, we consider a restriction of the MCSP to the case in which the matrix \(A\) is a row vector. By following an approach similar to [15, 20], we transform this restriction into a combinatorial optimization problem consisting of finding a shortest path in a particular weighted directed network. The insights provided by this transformation will prove useful both to extend the transformation to general matrices and to develop an ILP formulation for the general case of the MCSP. Before proceeding, we first introduce some notation and definitions similar to those already used in [2, 9, 20] and that will prove useful throughout the article. Let \(q\) be a positive integer. We define a partition of \(q\) as a possible way of writing it as a sum of positive integers, _i.e._,  
\[q=\sum_{j=1}^{r}\beta_{j} \tag{4}\]  
for some \(r,\beta_{j}\in\mathbb{Z}_{+}\) (see [21]). For example, if we consider \(q=4\) and we set \(r=3\) and \(\beta_{1}=\beta_{2}=1\) and \(\beta_{3}=2\) then a possible partition of 4 is \(1+1+2\). We call Equation (4) the extended form of this particular partition of \(q\). Interestingly, we also observe that an alternative way to partition \(q\) consists in writing it as a nonnegative integer linear combination of nonnegative integers, _i.e._,  
\[q=\sum_{j=1}^{s}\gamma_{j}\beta_{j} \tag{5}\]  
for some \(s,\beta_{j},\gamma_{j}\in\mathbb{Z}_{+}\). For example, if we set \(s=2\), \(\beta_{1}=1\), \(\beta_{2}=2\), \(\gamma_{1}=2\), \(\gamma_{2}=1\), then an alternative way to encode the considered partition is \((2\cdot 1)+(1\cdot 2)\). We call Equation (5) the compact form of this particular partition of \(q\). The definition of a partition of a positive integer proves useful to investigate the one row restriction of the MCSP. In particular, it is worth noting that any decomposition of a row vector \(A\) into a sum of positive integers implicitly implies partitioning the entries of \(A\). Then, a possible approach to solve the considered restriction consists in finding from among all of the possible partitions of each entry of \(A\) the ones that, appropriately combined, lead to the searched optimal decomposition. To this end, we denote \(H=||A||_{\max}=\max\{a_{ij}\}\), \([K]\) as the set \(\{1,\ldots,K\}\), for some positive integer \(K\), and we associate to the row vector \(A\) a particular weighted directed network \(D=(V,\mathcal{A})\), called partition network, built as follows. Given an entry \(a_{j}\) of \(A\) and a generic partition of \(a_{j}\), let \(q_{w}\) be the number of terms equal to \(w\) in the extended form of the considered partition or, equivalently, the coefficient associated to the term \(w\) in its compact form. Let \(V\) be the set of vertices including a source vertex \(s\), a sink vertex \(t\) and a vertex for each partition of each entry of \(A\):  
\[V := \{s\}\cup\{t\} \tag{6}\] \[\cup\left\{(j;q_{1},\ldots,q_{H}):\ \forall j\in[n],\ \forall(q_{1}, \ldots,q_{H})\in\mathbb{Z}_{+}^{H}\ \text{s.t.}\ \sum_{w=1}^{H}q_{w}\cdot w=a_{j}\right\} \tag{7}\]Let \(\mathcal{A}\) be the set of arcs of \(D\) defined as follows:  
\[\mathcal{A} := \{(s,(1;q_{1},\ldots,q_{H})):\ (1;q_{1},\ldots,q_{H})\in V\} \tag{8}\] \[\cup\{((j;q_{1},\ldots,q_{H}),(j+1;q^{\prime}_{1},\ldots,q^{\prime }_{H})):\ j\in[n-1]\] (9) \[(j;q_{1},\ldots,q_{H}),(j+1;q^{\prime}_{1},\ldots,q^{\prime}_{H} )\in V\}\] (10) \[\cup\{((n;q_{1},\ldots,q_{H}),t):\ (n;q_{1},\ldots,q_{H})\in V\} \tag{11}\]  
Note that the construction of the partition network \(D\) is such that a decomposition of \(A\) corresponds to a path from the source to the sink in \(D\). In particular, traversing a vertex \((j,q_{1},\ldots,q_{H})\) means that in the decomposition there are exactly \(q_{w}\) segments with a coefficient equal to \(w\) and a 1 in position \(j\), for all \(w\in[H]\).