Checking Up on Branch-and-Check
- J. Christopher Beck, University of Toronto
||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
Last updated: November 7, 2009.