On the separability of subproblems in Benders decompositions

Benders decomposition is a well-known procedure for solving a combinatorial optimization problem by defining it in terms of a master problem and a slave problem. Its effectiveness relies, among other factors, on the possibility of synthesizing Benders cuts that rule out not only one, but a large class of trial values for the master problem. In turn, for the class of problems we consider (i.e., optimization plus constraint satisfaction) the possibility of separating the slave problem into several subproblems—i.e., problems exhibiting strong intra-relationships and weak inter-relationships—can be exploited for improving searching procedures efficiency. The notion of separation is typically given informally, or relying on syntactical aspects. This paper formally addresses the notion of slave problem separability by giving a semantic definition and exploring it from the computational point of view. Several examples of separable problems are provided, including some proving that a semantic notion of separability is much more helpful than a syntactic one. We show that separability can be formally characterized as equivalence of logical formulae, and prove the undecidability of the separability check problem. Finally, we show how there are cases where automated tools can still be used for checking subproblem separability. Copyright Springer Science+Business Media, LLC 2009