Extracting Alternative Solutions from Benders Decomposition
Preprint
Abstract
We show how to extract alternative solutions for optimization problems solved by Benders Decomposition. In practice, alternative solutions provide useful insights for complex applications; some solvers do support generation of alternative solutions but none appear to support such generation when using Benders Decomposition. We propose a new post-processing method that extracts multiple optimal and near-optimal solutions using the cut-pool generated during Benders Decomposition. Further, we provide a geometric framework for understanding how the adaptive approximation in Benders Decomposition relates to alternative solutions. We demonstrate this technique on stochastic programming and interdiction modeling, and we highlight use cases that require the ability to enumerate all optimal solutions.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Measuring exploration: evaluation of modelling to generate alternatives methods in capacity expansion modelsEnvironmental Research: Energy, 2024
- Modeling all alternative solutions for highly renewable energy systemsEnergy, 2021
- PEBBL: an object-oriented framework for scalable parallel branch and boundMathematical Programming Computation, 2015
- Economic Foundations of Symmetric Programming2010
- Shortest‐path network interdictionNetworks, 2002
- Recursive MILP model for finding all the alternate optima in LP models for metabolic networksComputers & Chemical Engineering, 2000
- MGA: a decision support system for complex, incompletely defined problemsIEEE Transactions on Systems, Man, and Cybernetics, 1990
- Canonical Cuts on the Unit HypercubeSIAM Journal on Applied Mathematics, 1972
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic ProgrammingSIAM Journal on Applied Mathematics, 1969
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962