## 1 Introduction
However, as shown in the computational experiments performed in [9], the algorithm proves to be very slow in practice. The CP approach described in [15] was not initially conceived to solve the MCSP. In fact, the authors consider an objective function that minimizes at the same time a linear weighted combination of the number of segments involved in the decomposition and the sum of the coefficients used in the decomposition. As shown in [10], this approach can be adapted to solve the MCSP. However, the performances (in terms of solution times) so obtained are poorer than those relative to the CP approach described in [9]. Specifically, the authors of [9] first use an heuristic to find an initial feasible solution to the problem. Then, they attempt to find either a solution that uses less segments or to prove that the current solution is optimal. The certificate of optimality of the proposed algorithm is based on the use of an exhaustive search on the space of segments and coefficients compatible with the decomposition. As far as we are aware, this approach currently constitutes the fastest exact solution algorithm for the MCSP. The ILP formulations described in the literature are usually characterized by worse performances than the constraint programming approach presented in [9]. The earliest ILP formulation was presented in [16] and is characterized by a polynomial number of variables and constraints. Specifically, provided an upper bound on the overall number of segments is used, the authors introduce a variable for each entry  
Figure 1: An example of discretization of the particle beam emitted by a linear accelerator (from [2]). The matrix on the right encodes the discretized intensity values of the radiation field shown on the left. of each segment in the decomposition of the matrix \(A\). This choice gives rise to multiple drawbacks: it may lead to very large formulations, it does not cut out the numerous equivalent (symmetric) solutions to the problem, and it is characterized by very poor performances in terms of solution times and size of the instances of the MCSP that can be analyzed [9, 10]. The mixed integer linear programming formulation presented in [19] arises from an adaptation of the formulation used for a version Cutting Stock Problem [10]. As for [16], the formulation contains a polynomial number of variables and constraints and requires an upper bound on the overall number of segments used. As shown in [10], the formulation is characterized by better performances than the one presented in [16]. However, it proves unable to solve instances of the MCSP containing more than seven rows and seven columns. The polynomial-sized formulation presented in [18] has a strength point the fact that does not explicitly attempt at reconstructing the segments of the decomposition. This fact allows for both the reduction of the number of involved variables and a break in the symmetry introduced by the search of equivalent sets of segments. However, computational experiments carried out in [10] have shown that the linear relaxation of this formulation is usually very poor. This fact in turn leads to very long solution times [10]. A similar idea was used in [17]. In particular, the proposed polynomial-sized formulation minimizes the number of segments required in the decomposition of the matrix \(A\), without explicitly computing them. This last step is possible in a subsequent moment via a post-processing of the optimal solution. However, also in this case, the formulation is characterized by poor computational performances when compared to the constraint programming approach described in [9], mainly due to the poor lower bounds provided by the linear relaxation. Starting from the results described in [PERSON]'s Ph.D. thesis [20], in this article we investigate the problem of providing tighter lower bounds to the MCSP.