## 1 Introduction  
Let \(S=\{s_{ij}\}\) be a \(m\times n\) binary matrix. We say that \(S\) is a _segment_ if for each row \(i=1,\ldots,m\), the following _consecutive ones property_ holds [1]:  
\[\text{if}\;\;s_{ij}=s_{ij^{\prime}}=1\;\;\text{for}\;\;1\leq j<j^{\prime}\leq n \;\;\text{then}\;\;s_{ik}=1\;\;\forall\;j<k<j^{\prime} \tag{1}\]  
Given an \(m\times n\) nonnegative integer matrix \(A=\{a_{ij}\}\), the _Minimum Cardinality Segmentation Problem_ (MCSP) consists in finding 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 1,\ldots,K\), and \(K\) is minimum. For example, consider the following nonnegative integer matrix:  
\[A=\left( \begin{array}{cccccc}0&1&1&1&1&0\\ 1&1&2&2&2&1\\ 1&2&4&4&2&0\\ 1&1&2&2&1&0\\ 0&1&1&0&0&0\end{array} \right) \tag{2}\]  
then a possible decomposition of \(A\) into segments is [2]:  
\[A = 2\left( \begin{array}{cccccc}0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&1&1&1&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0\end{array} \right)+1\left( \begin{array}{cccccc}0&1&1&1&0&0\\ 0&0&1&1&1&0\\ 0&1&1&1&0&0\\ 0&0&1&1&0&0\\ 0&0&0&0&0&0\end{array} \right)+1\left( \begin{array}{cccccc}0&0&0&0&1&0\\ 1&1&1&1&1&1\\ 1&1&1&1&0&0\\ 1&1&1&1&1&0\\ 0&1&1&0&0&0\end{array} \right) \tag{3}\]  
The MCSP arises in intensity modulated radiation therapy, currently considered one of the most powerful tools to treat solid tumors (see [3; 4; 5; 6; 7]). In this application, the matrix \(A\) usually encodes the intensity of the particle beam that has to be emitted by a linear accelerator at each instant of a radiation therapy session (see Figure 1). As the linear accelerator can only emit, instant per instant, a particle beam having a fixed intensity value rather than those encoded in \(A\), the intensity matrix has to be decomposed into a set of segments, each encoding those elementary quantities of radiation, in order to deliver entry per entry the requested amount of radiation (see [7] for further details). The MCSP is known to be \(\mathcal{NP}\)-hard even if the matrix \(A\) has only one row [1] or one column [8]. It is worth noting that the two restrictions mainly differ from each other for the type of segments considered. Specifically, in the one row case the segments are binary vector rows satisfying the consecutive ones property; in the one column case segments are just binary column vectors. The \(\mathcal{NP}\)-hardness of the MCSP has justified the development of exact and approximate solution approaches aiming at solving larger and larger instances of the problem. These approaches have been recently reviewed in [7; 9; 10], and we refer the interested reader to these articles for further information. Here, we just focus on the exact solution approaches for the MCSP. The literature on the MCSP reports on a number of studies focused on a specific restriction of the problem characterized by having the highest entry value of the matrix \(A\), denoted as \(\left\|A\right\|_{\max}=\max\{a_{ij}\}\), bounded by a positive constant \(H\). This assumption is generally exploited e.g.,in [1, 11, 12, 13] to develop pseudo-polynomial exact solution algorithms for the considered restriction. A recent survey of these algorithms can be found in [7]. Surprisingly enough, however, in the last decade only a limited number of exact solution approaches have been proposed in the literature for the general problem. These approaches are restricted to the pseudo-polynomial solution algorithm described in [14], the Constraint Programming (CP) approaches described in [9, 15], and the Integer Linear Programming (ILP) approaches described in [16, 17, 18, 19]. Specifically, the algorithm proposed in [14] is based on an iterative process that exploits the pseudo-polynomial solution algorithm of [13] to solve at each step an instance of the MCSP characterized by having \(1\leq\left\|A\right\|_{\max}=\max\{a_{ij}\}\leq H\). The author shows that the algorithm is able to solve an instance of the general problem with an overal computational complexity \(O((mn)^{2H+3})\).