abstract

Logic-based Benders' decomposition is a problem decomposition technique that lends itself to hybrid problem solving approaches to hard combinatorial problems. At a high-level, Benders' defines a master problem and set of subproblems and the solution approach alternates between solving the master problem and the sub-problems until convergence to a globally optimal solution. Branch-and-Check is a variation of logic-based Benders' decomposition where the sub-problems are solved more frequently, for example, whenever a feasible, rather than optimal, master problem solution is found. While logic-based Benders' has been receiving increasing interest in the Constraint Programming community, there does not appear to have been a detailed study of Branch-and-Check. We undertake such a study using four problems: three scheduling problems and a facility location problem. We demonstrate that while Branch-and-Check often results in a small improvement over Benders', it can also perform very poorly. Further analysis demonstrates why this is the case and provides a straight-forward fix. The deeper question arises from the recognition that the four test problems behave in three different ways when being solved by Benders' or Branch-and-Check and that these differences are important to understanding how the performance of the two techniques can be improved.