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 subproblem. Its effectiveness relies on the possibility of synthethising Benders cuts (or nogoods) that rule out not only one, but a large class of trial values for the master problem. In turns, this depends on the possibility of separating the subproblem into several subproblems, i.e., problems exhibiting strong intra-relationships and weak inter-relationships. The notion of separation is typically given informally, or relying on syntactical aspects. This paper formally addresses the notion of separability of the subproblem by giving a semantical definition and exploring it from the computational point of view. Several examples of separable problems are provided, including some proving that a semantical 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 problem of checking separability. © Springer-Verlag Berlin Heidelberg 2006.