## 2 The One Row Restriction of the MCSP as a Network Optimization Problem
\begin{array}{cc}0&1\\ 1&0\end{array} \right) \tag{28}\]  
It is worth noting that the matrices \(A_{w}\) in general are not segments. However, it is possible to prove that each matrix \(A_{w}\) can be in turn decomposed into a sum of segments, in such a way that the resulting decomposition is optimal for the MCSP. To this end, we introduce the following auxiliary problem:  
**The Beam-On Time Problem (Botp). **_Given a nonnegative integer matrix \(A\), find a decomposition \(A=\sum_{t=1}^{K}u_{t}S_{t}\) such that \(u_{t}\in\mathbb{Z}_{+}\), \(S_{t}\) is a segment, for all \(t\in[K]\), and \(\sum_{t=1}^{K}u_{t}\) is minimum._  
The BOTP is polynomially solvable via the algorithms described in [1, 20] and differs from the MCSP for the fact that it searches from among all the possible decompositions of the matrix \(A\) the one for which the sum of the coefficients is minimal. Given a decomposition of \(A\) as in Equation (27), let us decompose \(A_{w}\), for each \(w\in[H]\), into a nonnegative integer linear combination of segments minimizing the BOTP. Then, Equation (27) can be rewritten as  
\[A = \sum_{w=1}^{H}w\cdot A_{w}=\sum_{w=1}^{H}w\cdot\left(\sum_{t:u_{t}= w}S_{t}\right)=\sum_{t=1}^{K}u_{t}S_{t} \tag{29}\]  
where \(K=\sum_{w=1}^{H}|\{t:u_{t}=w\}|\). The minimality of \(K\) in this new decomposition (_i.e._, the optimality of Equation (29) for the MCSP) is then proved by the following proposition:  
**Proposition 1**. : _Let \(K\) be the optimal value to the MCSP. Then, the following equality holds:_  
\[K=\sum_{w=1}^{H}BOT(A_{w})\]  
_where \(BOT(A_{w})\) denotes the minimum sum of \(\sum_{t=1}^{K}u_{t}\) in the decomposition of \(A_{w}\)._  
Proof. : Let \(\beta_{w}\) denote \(|\{t:u_{t}=w\}|\), _i.e._, the sum of the coefficients in the decomposition of \(A_{w}=\sum_{t:u_{t}=w}S_{t}\), for all \(w\in[H]\). Then, it holds that \(\beta_{w}\geq BOT(A_{w})\), for all \(w\in[H]\). Hence, we have that  
\[K=\sum_{w=1}^{H}\beta_{w}\geq\sum_{w=1}^{H}BOT(A_{w}) \tag{30}\]  
To prove that in Equation (30) the strict equality holds, assume by contradiction that for some \(\hat{w}\in[H]\), \(\beta_{\hat{w}}>BOT(A_{\hat{w}})\). Then, it is possible to obtain a smaller value of \(\beta_{\hat{w}}\) by replacing \(\sum_{t:u_{t}=\hat{w}}S_{t}\) with the decomposition provided by the optimal solution of the BOTP with input \(A_{\hat{w}}\). However, \(\beta_{\hat{w}}\) is defined as the optimal solution to the BOTP with input \(A_{\hat{w}}\), hence this would contradict its optimality. Thus, the statement follows. As an example, by using the decomposition algorithm for the BOTP described in [1,20] on the matrices \(A_{w}\) in Equation (28), we obtain the following decomposition for Equation (23)  
\[A=\left( \begin{array}{cc}2&3\\ 3&1\end{array} \right)=1\left( \begin{array}{cc}2&1\\ 1&1\end{array} \right)+2\left( \begin{array}{cc}0&1\\ 1&0\end{array} \right)=\left( \begin{array}{cc}1&0\\ 1&1\end{array} \right)+\left( \begin{array}{cc}1&1\\ 0&0\end{array} \right)+2\left( \begin{array}{cc}0&1\\ 1&0\end{array} \right) \tag{31}\]  
which is optimal due to Proposition 1. The transformation of the MCSP into a network optimization problem and the result provided by Proposition 1 constitute the fundation for the ILP formulation that will be presented in the next section.