Thema der Dissertation:
Hybrid Discrete Optimization for Route Planning and Scheduling Thema der Disputation:
An Introduction to Logic-Based Benders Decomposition
Hybrid Discrete Optimization for Route Planning and Scheduling Thema der Disputation:
An Introduction to Logic-Based Benders Decomposition
Abstract: Benders decomposition (BD) is a standard approach in large-scale optimization. It serves to separate the original problem into a master problem and one, or possibly many, subproblems. These smaller, and hopefully easier, problems are then solved independently, communicating to each other via so-called Benders cuts.This core idea of BD appears appealing for a large class of optimization problems. In classical BD, however, Benders cuts are derived via duality theory, which limits the method’s applicability to linear programming subproblems. In this talk, we give an introduction to logicbased Benders decomposition (LBBD), a generalization of BD that overcomes this limitation by reinterpreting the use of duality theory in Benders’s original method as a form of logical inference. This allows LBBD to be applied to a broad class of general optimization problems. In particular, it admits subproblems formulated as mixed-integer programs or even constraint programs. LBBD achieves its generality by, in contrast to BD, putting the burden of cut design on its user. We will hence discuss common cutting strategies including (strengthened) no-good cuts and analytical cuts. Finally, we will compare LBBD to a selection of related techniques, such as generalized Benders decomposition and branch-and-check, and review applications in scheduling.
Zeit & Ort
25.11.2025 | 13:15
Seminarraum 2006
(Zuse Institut Berlin, Takustr. 7, 14195 Berlin)
&
WebEx