Operations Research 2025
Abstract Submission

71. Automated Logic-Based Benders Decomposition

Invited abstract in session WC-2: Bilevel Optimization, stream Discrete and Combinatorial Optimization.

Wednesday, 13:30-15:00
Room: H4

Authors (first author is the speaker)

1. Vladimir Stadnichuk
Lehrstuhl für Operations Managemnt, RWTH Aachen
2. Grit Walther
School of Business and Economics, Chair of Operations Management, RWTH Aachen University
3. Arie Koster
Lehrstuhl II für Mathematik, RWTH Aachen University

Abstract

We study Logic-Based Benders Decomposition (LBBD) for two-stage optimization problems, a generalization of traditional Benders decomposition to non-convexity in the second stage. Our focus is on two-stage problems with binary linking variables in the first stage and mixed-integer variables in the second stage, a setting where LBBD has been successfully applied to various applications. However, unlike conventional Benders decomposition, which benefits from automation within modern Mixed-Integer Programming (MIP) solvers, LBBD typically demands an intricate theoretical analysis to derive appropriate cut coefficients. This necessity presents significant barriers to practitioners aiming to utilize LBBD without extensive theoretical specialization. Against this background, we propose a novel framework capable of automatically generating Logic-Based Benders cuts using only the MIP formulations of both problem stages as input. Our methodology combines Benders, Lagrangian, and Dantzig-Wolfe decomposition techniques to project out the second-stage variables and generate LBBD cuts within a cutting-plane algorithm. We provide a comprehensive implementation of this framework in the Julia programming language, demonstrating that our approach can easily be implemented in state-of-the-art MIP solvers that support cutting-plane methods. Furthermore, our implementation includes multiple acceleration techniques, incorporating both newly-developed enhancements specifically tailored for our framework and established methods from existing decomposition literature. We also present some preliminary computational results.

Keywords

Status: accepted

Back to the list of papers