Solving the proposed models with a commercial solver

Abstract and 1. Introduction

2. Mixed integer and constraint programming models

   2.1 Mixed-integer linear programming model

   2.2 Constraint Programming model

3. Constructive Heuristics

4. Benchmark instances

5. Numerical experiments

   5.1 Experiments with the constructive heuristics

   5.2 Solving the proposed models with a commercial solver

6. Conclusions and References

5.2 Solving the proposed models with a commercial solver

In this section, we apply an exact solver to the 330 instances considered and evaluate the quality of the solutions found within a given CPU time limit, depending on whether we provide the solution found by the constructive heuristics as an initial solution or not. Since there is no clear winner between the two constructive heuristics and their execution time is negligible, we run both and give the best of the two as initial solution to the exact solver. In the tables and figures, the solvers’ runs that receive as input a solution computed by one of the constructive heuristics are identified with the expression “warm start”.

Tables 5, 6, 7, 8, 9, and 10 show the results in detail when the warm start is not taken into account. Tables 5, 6, and 7 correspond to the small-sized instances with α equal to 0.1, 0.2, and 0.3, respectively; while Tables 8, 9, and 10 show the same thing for the large-sized instances. Tables 11–16 show the results when the warm start is taken into account. The tables show the information related to the resolution of the MILP and CP models. When a single number appears in the “makespan” column, it means that a provably optimal solution with that makespan value was found. When instead of a number an expression of the form [A, B] C% appears, it means that a feasible solution was found with value B for the makespan, value A for a lower bound on the makespan, and gap C equal to 100(B − A)/B. As measures of computational effort, for the MILP solver the tables show the number of iterations, the number of nodes explored in the branch-and-bound search tree, and the CPU time in seconds. For the CP solver, the tables show the number of branches and the CPU time in seconds. If no information is displayed for a particular instance, it means that the solver was unable to find a feasible solution within the specified CPU time limit. In Tables 11–16, which show results with warm start, the symbol † next to the optimal or best value found means that the exact method returned exactly the same solution computed with the constructive heuristic and given as initial solution. The information from Tables 11–16 is presented graphically in Figure 6.

Let’s look at the small-sized instances first. Without warm start, the exact methods found provably optimal solutions for 168 instances of the MILP model and 169 instances of the CP model (out of a total of 180 small-sized instances). In the remaining cases, the gaps for the MILP model instances were between 0.17% and 23.32%, while for the CP model instances the gaps were between 29.44% and 47.55%. It is worth noting that in the few cases without a proven optimal solution, there is a slight advantage in the best solution found for the CP model instances and a slight advantage in the lower bounds found for the MILP model instances. In the instances where a proven solution was found by solving both the MILP model and the CP model, the CP solver was on average 12.09% faster than the MILP solver. When the constructive heuristics solution is made available to the exact solvers, the number of proven optimal solutions found hardly changes (still the same number for MILP model instances and one less for CP model instances, not necessarily the same as those solved without the warm start). However, for MILP model instances where a proven optimal solution is found both with and without warm start, the use of warm start reduces the solution time by 32.52% in average. This reduction is 4.44% for the CP model solver. One way or another, whether using the MILP model or the CP model, with or without warm start, it was possible to find provably optimal solutions in 176 (out of 180) small-sized instances.

The analysis of the 150 large-sized instances is a little different. Without a warm start, the exact methods were able to find proven optimal solutions for only 7 instances of the MILP model and 5 instances of the CP model. In 70 MILP model instances it was possible to find feasible solutions with gaps between 13.94% and 90.47%, while feasible solutions with gaps between 9.30% and 86.10% were found in 145 instances of the CP model. In 73 instances of the MILP model, not a single feasible solution was found. In the 70 instances in which feasible solutions from both the MILP and CP models were found, the solutions found using the CP model were on average 68.85% better. It was after observing these results that the idea arose to develop constructive heuristics to test the warm start and consider a set of smaller instances.

When the solution of the constructive heuristics is fed to the exact solver, 6 provably optimal solutions and 144 feasible solutions are obtained with gaps between 5.65% and 64.36% for MILP model instances. For the CP model instances, the same number of provably optimal and feasible solutions are found, with gaps between 15.43% and 81.06% for the feasible ones. In those instances where a proven optimal solution is found without and with warm start, warm start increases the computational cost of solving the MILP and CP models by 9.69% and 25.99%, respectively. On the other hand, in the MILP model instances in which a feasible solution was found without the use of warm start, the use of warm start improved the quality of the feasible solution found by 49.46%. For the CP model instances, this improvement was 11.53%. In the 144 instances in which feasible solutions from both the MILP and CP models were found, the solutions found using the CP model were on average 6.82% better. The question remains as to whether the exact methods are able to improve the solution provided by the constructive heuristics or whether the statistics improve only because the solvers return the solution they received as input. In the case of the MILP model instances, the initial solution is improved in 33 problems, while in the CP model instances the initial solution is improved in 134 problems. Without a warm start, in the instances where it is possible to find a provably optimal solution for both the MILP model and the CP model (5 instances), the cost of solving the CP models is 70.81% lower. In the case where provably optimal solutions are found in both cases using warm start (6 instances), the cost of solving the CP models is 41.86% lower. In short, it is challenging to find a proven optimal solution for large-sized instances, solving CP model instances costs less, CP models provide better quality feasible solutions when it is not possible to find a provably optimal solution, and solving MILP models provides better quality lower bounds. One way or another, whether using the MILP model or the CP model, with or without warm start, it was possible to find provably optimal solutions in only 7 large-sized instances and feasible solutions in all the remaining 143 large-sized instances.