Logic-Based Benders Decomposition: An Opportunity
for Logic Programming Applications (Invited talk)
Marco Gavanelli
Department of Engineering, University of Ferrara, Italy


                                      Abstract
                                      In 1962 J. F. Benders proposed a decomposition technique to solve large Mixed-Integer Linear Program-
                                      ming (MILP) problems; the idea was to split the whole MILP into a Master Problem (MP) and one (or more)
                                      independent sub-problems (SPs), that are solved independently, in an iterative fashion. Since the solution
                                      time is usually superlinear, splitting the problem provides a strong improvement. On the other hand,
                                      Benders’ decomposition is tailored for MILP approaches, as it relies on the well-known duality theory of
                                      Linear Programming. More recently, J. Hooker proposed an extension of Benders’ decomposition to a
                                      more general case, that does not rely necessarily on a duality theory: the so called Logic Based Benders
                                      Decomposition (LBBD). LBBD opened the way to the application of decomposition techniques to other
                                      constrained optimization approaches, notably to those based on constraint programming, and nowadays
                                      the applications are uncountable, including inventory management, scheduling, logic circuit verification,
                                      vehicle routing, facility location, space packing, supply chain management just no name a few.
                                          In this talk, we argue that the use of Benders decomposition can provide a considerable speedup to
                                      logic programming solutions of real-life applications, without sacrificing completeness or optimality.




CILC’23: 38th Italian Conference on Computational Logic, June 21–23, 2023, Udine, Italy
$ marco.gavanelli@unife.it (M. Gavanelli)
 0000-0001-7433-5899 (M. Gavanelli)
                                    © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
 CEUR
 Workshop
 Proceedings
               http://ceur-ws.org
               ISSN 1613-0073
                                    CEUR Workshop Proceedings (CEUR-WS.org)