Logic-based Benders decomposition

By John N. Hooker, Greger Ottosson. Synthesis Lectures on Operations Research and Applications, 2003

522 citations recorded by the source corpus.

Abstract. Benders decomposition uses a strategy of ``learning from one's mistakes.'' The aim of this paper is to extend this strategy to a much larger class of problems. The key is to generalize the linear programming dual used in the classical method to an ``inference dual.'' Solution of the inference dual takes the form of a logical deduction that yields Benders cuts. The dual is therefore very different from other generalized duals that have been proposed. The approach is illustrated by working out the details for propositional satisfiability and 0-1 programming problems. Computational tests are carried out for the latter, but the most promising contribution of logic-based Benders may be to provide a framework for combining optimization and constraint programming methods.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/994dcab401957bcf3d7fc8421e52087d441288e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Combinatorial Benders' Cuts for Mixed-Integer Linear Programming (2006, methodology): “Meanwhile, Hooker and Ottosson [22] used logic Benders’ cuts to solve SAT problems and 0-1 programming problems.”
The Benders decomposition algorithm: A literature review (2017, methodology): “Hooker and Ottosson (2003) and Hooker (2011) introduced an extension known as logic-based Benders decomposition (LBBD).”