## 2 Problem Definition
### MP-Based Improvement Search  
Once the QACO-based solution construction and exploration have been completed, we use the best feasible solution found as a basis for finding other solutions associated with higher objective values. To this end, we run a large neighborhood search in an exact way. In this case, the adjective \"exact\" means that we formulate the search by means of Mathematical Programming (MP) techniques and we optimally solve the resulting optimization problem through state-of-the-art optimization software like CPLEX. The rationale for inspiring such an approach is that even though a powerful MP solver cannot optimally solve a large and complex problem, it may instead rapidly and efficiently solve suitable sub-problems. In our case, we identify and solve the sub-problems relying on the _Relaxation Induced Neighborhood Search_ (RINS) proposed in [47]: given a feasible solution to an optimization problem, RINS searches for better solutions in a neighborhood defined considering a linear relaxation of the problem. More formally and referring to our problem BLP-ESPLR, supposing that:  
* \(\tilde{x}_{ds\ell}\) is a feasible solution of BLP-ESPLR (i.e., a binary solution satisfying all the constraints (2)-(4));
* \(x_{ds\ell}^{LR}\) is the optimal solution of the linear relaxation of the problem (1)-(5) (i.e., a relaxed version BLP-ESPLR obtained by replacing the integrality requirement of each variable \(x_{ds\ell}\in\{0,1\}\) with its continuous relaxation \(0\leq x_{ds\ell}\leq 1\)). Then, for a chosen constant \(\rho\in(0,1)\), the neighborhood \(\mathcal{N}(\tilde{x})\) of the feasible solution \(\tilde{x}_{ds\ell}\) is defined as the set of feasible solutions of the sub-problem of BLP-ESPLR in which:  
* if \(\tilde{x}_{ds\ell}=0\ \ \wedge\ \ x_{ds\ell}^{LR}\leq\rho\quad\text{then}\quad x _{ds\ell}=0\)
* if \(\tilde{x}_{ds\ell}=1\ \ \wedge\ \ x_{ds\ell}^{LR}\geq 1-\rho\quad\text{then}\quad x _{ds\ell}=1\)
* else \(x_{ds\ell}\in\{0,1\}\). In other words, a subset of the decision variables of the subproblem have the value fixed and such fixing happens if the value of a decision variable is sufficiently similar in both the feasible solution \(\tilde{x}\) and in the optimal solution \(x^{LR}\) of the linear relaxation. As discussed in [47], such similarity of values in the integral and relaxed problem provides a good indication that the variable is likely to have that value in feasible solutions of high quality. More in detail, if we denote by \(I^{1}\) and \(I^{0}\) the set of indices of variables fixed to \(1\) and \(0\), respectively, according to the rules above, the subproblem for a feasible solution \(\tilde{x}\) can be written as:  
\[\max \sum_{d\in D}\sum_{s\in S(d)}\sum_{\ell\in L(d,s)}v_{ds\ell}\cdot x _{ds\ell} \text{(BLP-ESPLR(\tilde{x}))}\] \[\text{LB}_{ds}^{\text{TOT}}\leq\sum_{\ell\in L(d,s)}n_{\ell} \cdot x_{ds\ell}\leq\text{UB}_{ds}^{\text{TOT}} \forall d\in D,s\in S(d)\] \[\sum_{\ell\in L(d,s)}c_{ds\ell}\cdot x_{ds\ell}\leq\text{UB}_{ds }^{c} \forall d\in D,s\in S(d)\] \[\text{LB}_{d}^{\gamma}\leq\sum_{s\in S(d)}\ \sum_{\ell\in L(d,s):\ \gamma(\ell)= \gamma}x_{ds\ell}\leq\text{UB}_{d}^{\gamma} \forall d\in D,\gamma\in\Gamma\] \[x_{ds\ell}=1 \forall(d,s,\ell)\in I^{1} \tag{10}\] \[x_{ds\ell}=0 \forall(d,s,\ell)\in I^{0}\] (11) \[x_{ds\ell}\in\{0,1\} \forall d\in D,s\in S(d),\ell\in L(d,s)\]  
in which constraints (10) model the fixing of variables to \(1\) and (11) model the fixing of variables to \(0\). We indicate this subproblem by BLP-ESPLR(\(\tilde{x}\)), pointing out that it is defined on the basis of an incumbent feasible solution \(\tilde{x}\). Following the fixing of variables, the resulting sub-problem is solved by software like CPLEX with the aim of being optimally solved and hopefully finding a better solution. We note that an optimal solution to the subproblem clearly constitutes a feasible solution for the original complete problem. The exact search in the neighborhood is typically conducted within a time limit.