Algorithmic procedure. The cut insertion procedure of the Combinatorial Benders Algorithm (CBA) is sketched in Figure 2. Commercial solvers enable the user to interrupt the MP branch-and-cut process at various nodes to launch predefined routines for different purposes. In our algorithm, this practical tool is used to launch the SP(αˆ) model whenever the value ZR(αˆ) of a feasible integer solution αˆ is lower than the incumbent value Zinc, as described by Algorithm 1. The solution method for the SP is summarized below by Algorithm 2. add MP Active nodes Explored nodes Tested node SP check update Figure 2: Single-tree Combinatorial Benders Algorithm (cut-insertion process) The addition of the combinatorial cut (17) to the MP formulation excludes candidate αˆ from the feasible space, whether it is optimal for MDPC or not. The branch-and-cut procedure continues searching for the best feasible solution until there are no candidates left. When the solver stops, the optimality criterion is satisfied: the relaxed value ZR(αˆ) of any solution αˆ is above the incumbent value, which is therefore optimal (Zinc = Zopt). The lower bound obtained along the process is associated with the MP formulation. Therefore, it is never larger than the optimal value of the MP, which is itself a lower bound for the MDPC model. The sub-problem SP to be solved by Algorithm 1 is a MILP that must be solved repeatedly and may take a considerable amount of time to solve. In order to facilitate its solution, as suggested in Section 6.2.2, we decompose it per period, and we solve each sub-problem SP(αˆt), for t ∈ T . This process can be further accelerated as follows. For the contract plan αˆ and a period t, consider the assignment αˆt, that is, the restriction of αˆ to period t. It may very well happen (and in fact, it frequently happens in practice) that αˆt = αt for another contract plan α which was considered in Algorithm 1: Single-tree Benders Subroutine (Feasible αˆ ) Input:
