Benders decomposition is a well-known procedure for solving a combinatorial optimization problem by deﬁning 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 efﬁciency. 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 deﬁnition 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.
On the separability of subproblems in Benders decompositions / Marco, Cadoli; Patrizi, Fabio. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 171:1(2009), pp. 27-43. [10.1007/s10479-008-0383-5]
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||On the separability of subproblems in Benders decompositions|
|Data di pubblicazione:||2009|
|Citazione:||On the separability of subproblems in Benders decompositions / Marco, Cadoli; Patrizi, Fabio. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - STAMPA. - 171:1(2009), pp. 27-43. [10.1007/s10479-008-0383-5]|
|Appartiene alla tipologia:||01a Articolo in rivista|