Exact Methods through Decomposition: Insights from Logic-Based Benders Decomposition

Abstract

Decomposition techniques for integer programs have played a central role in developing state-of-the-art exact methods for some of the most challenging optimization problems. Among these, branch-price-and-cut and Benders decomposition are widely recognized as fundamental tools, instrumental in solving a broad spectrum of complex problems.

Benders decomposition, introduced in 1962, is a powerful method whose key idea can be viewed as a form of logical inference. This insight motivates logic-based Benders decomposition (LBBD), in which the subproblem need not be linear but may be any optimization problem. LBBD generalizes the classical approach and has enabled a wide range of applications. The term “logic-based” highlights the role of inference in the method’s design rather than a requirement for formal logic in the problem structure.

In this talk, we briefly review two primary types of decomposition: price (or constraint) decomposition and resource (or variable) decomposition. We then focus on variable decomposition and the LBBD framework, illustrating how it leverages problem structure to enhance computational efficiency and solution quality. The discussion also addresses practical aspects of implementation, including best practices and common pitfalls. Finally, we demonstrate the effectiveness of LBBD in solving challenging routing, scheduling, and packing problems, and conclude with key insights and directions for future research.

Reference
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4:238–252.

Hooker JN (2000) Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley, New York.

Speaker

Prof. Baldacci is a Professor of Operations Research at the College of Science and Engineering, Hamad Bin Khalifa University, Doha, Qatar. He holds a PhD in Operations Research from Imperial College, University of London, United Kingdom.

Previously, he was an Associate Professor of Operations Research at the College of Science and Engineering, Hamad Bin Khalifa University (2022–2025), an Associate Professor of Operations Research at the University of Bologna, Italy (2012–2022), an Assistant Professor at the University of Bologna, Italy (2005–2012), an Assistant Professor at the University of Modena and Reggio Emilia, Italy (2001–2005), and a Postdoctoral Research Associate at the Centre for Quantitative Finance, Imperial College London, United Kingdom (2000–2001).

His research lies at the intersection of Advanced Analytics, Operations Research, and Data-Driven Optimization, with a strong focus on transportation and logistics applications. It spans the theoretical development, design, implementation, and evaluation of algorithms for optimization problems. He specializes in both exact methods and heuristic or metaheuristic approaches. In recent years, his work has expanded to include stochastic and distributionally robust optimization, large-scale linear programming with column-dependent rows, and dynamic discretization discovery techniques.

Prof. Baldacci has over 25 years of teaching experience across all levels (BSc, MSc, and PhD) and has supervised numerous undergraduate, graduate, and doctoral students.

He serves on the editorial boards of Operations Research and Transportation Science. He has published over 100 papers in leading journals, including approximately 30 papers in the INFORMS Journal on Computing, Mathematical Programming, Operations Research, and Transportation Science.