Logic-Based Benders Cuts

Effective logic-based cuts are essential to the success of logic-based Benders decomposition, and this chapter shows how they can be designed to exploit problem structure. The most popular cuts used in practice are strengthened nogood cuts and analytical cuts. Nogood cuts are based on optimal values returned from the Benders subproblem, and several algorithms that strengthen them are presented. Analytical cuts are derived from an analysis of subproblem structure. The chapter presents a class of generic analytical cuts, followed by in-depth studies of domain-specific cuts for scheduling, vehicle routing, and packing problems, as demonstrations of how strong cuts can be fashioned. It concludes by showing how cuts can be obtained directly from a proof of optimality when it is available from the subproblem solver.