1719. Implementing a generic Logic-Based Benders Decomposition in SCIP
Invited abstract in session WD-43: Algorithms and Applications, stream Software for Optimization.
Wednesday, 14:30-16:00Room: Newlyn GR.07
Authors (first author is the speaker)
| 1. | Sachin Rajendran
|
| Department of Mathematics, Linköping University | |
| 2. | Elina Rönnberg
|
| Department of Mathematics / Optimization, Linköping University | |
| 3. | Stephen Maher
|
| GAMS Software GmbH |
Abstract
Logic-Based Benders Decomposition (LBBD) is a powerful approach for solving discrete optimization problems with certain structures. While LBBD is often tailored for specific problem types, our goal is to develop a generic purpose LBBD framework within SCIP — a leading solver for Constraint Integer Programming (CIP). A key advantage of implementing in SCIP is the ability to use CIP-solving features, which combine Constraint Programming (CP), Mixed Integer Programming, and Satisfiability techniques. As opposed to CIP, which approaches constraints individually, LBBD treats the CP subproblem as a whole, thus we can leverage strong CP solvers for the subproblems.
Currently, SCIP offers some built-in components that can support LBBD, but extensions are necessary to create a fully functional and flexible LBBD framework. Existing features in SCIP, such as the classical Benders decomposition framework and constraint handlers, can be leveraged for LBBD implementation. In our current work, we target problems with implication structures and feasibility subproblems. For these we implement acceleration techniques such as cut strengthening and identifying irreducible infeasible subsystems. For future work we aim to utilize research on LBBD and develop a full-featured generic LBBD solver in SCIP.
Keywords
- Programming, Mixed-Integer
- Programming, Constraint
- Scheduling
Status: accepted
Back to the list of papers