## 4 Computational Experiments
### Results  
An aggregated summary of the results is presented in Table 1. The average optimality gap across all the instances for which all the models were able to find a feasible/optimal solution is reported under _Average optimality gap_. The average solution time among all the instances that were solved to optimality by all the models can be found under _Average solution time_. The detailed results of each model can be found instead in Tables 2-4, where the following data are reported for each instance. The name and size can be found in the columns with these names. The best-known bounds found in [38] are reported in the column _Best-Known_[38], where \(LB\) shows the best lower bound, and \(UB\) the best-known solution. For each model, the following columns are displayed. The lower and upper bound can be found in the column with these names. The optimality gap, computed as \(\frac{UB-LB}{UB}\), is reported in the column _Gap_. The solution time in seconds, which is reported only for those instances that are closed in the given time, can be found in the column _Time_. Entries in bold indicate new best-known lower or upper bounds. Finally, the name of the instances for which optimality is proven for the first time in this work is highlighted in bold across the tables. on the _Reduced_ model also runs out of memory on one instance. When considering the CP solver, the _Complete_ model shows an optimality gap of 0.159 on average (with a 22.8% improvement), with an optimality gap of 0.157 on average across all the instances. However, the largest instances, with size larger than 200 or with a very dense precedence graph, are not solved, since the model runs out of memory due to the large number of constraints (19). When solving the _Reduced_ model, the CP solver achieves an optimality gap of 0.122 on average (with a 40.7% improvement), with an optimality gap of 0.286 averaged across all the instances. In terms of solution time, and comparing the instances that are optimally solved by all models (27 instances), using the MILP solver takes the _Complete_ model to a solution time of 690.8 s on average, while the _Reduced_ takes 270.8 s on average (with a 60.8% improvement). When the CP solver is used, the _Complete_ model has a solution time of 166.4 s on average (with a 75.9% improvement), while solving the _Reduced_ model takes 36.4 s on average (with a 94.7% improvement). Cross-comparing a same model when treated by the two different solvers, it emerges that generally the CP models outperform the MILP models on instances with medium to high density precedence graphs. In terms of solution costs, the _Reduced_ model solved by an MILP solver finds new best-known lower bounds for 24 out of 88 instances (27.3%) compared to the 2 retrieved by the _Complete_ model solved by the same solver. Furthermore, the _Reduced_ model finds new best-known upper bounds for 15 (17.1%) compared to the 1 only found by the _Complete_ model. This indicates that the strength of the linear relaxation of the model is not drastically affected after removing a subset of the variables and constraints from the model. Furthermore, this shows that the _Reduced_ model is generally easier to solve by the MILP solver adopted, and therefore the solver is able to find new bounds more frequently compared to solving the _Complete_ model. When considering the CP solver, the _Reduced_ model finds new best-known lower bounds for 32 (36.4%), while the _Complete_ model finds new lower bounds for 13 (14.8%). For new best-known upper bounds, solving the _Reduced_ model leads to new 54 new bests (61.4%), while solving the _Complete_ model leads to 10 new bests (11.4%). This indicates that the _Reduced_ model is generally more effective to solve by the CP solver when compared to the _Complete_ model. Moreover, the use of the CP solver led to seven newly proven optimal solutions. In general, using the MILP solver seems to produce better lower bounds, while the CP solver is better at finding lower cost solutions.