Basic Theory

This chapter develops the elementary theory of logic-based Benders decomposition (LBBD), beginning with the essential concept of inference duality. It formally states the LBBD algorithm and proves finite convergence when certain variables have finite domains, a condition normally satisfied in practice. It shows how classical Benders decomposition is a special case, and suggests some alternative perspectives on LBBD that provide additional insight. It then details how to exploit the common situation in which the Benders subproblem decouples into smaller problems. The chapter concludes with some practical guidelines for implementing an efficient LBBD algorothm.