Artikel
Refined cut selection for benders decomposition: applied to network capacity expansion problems
In this paper, we present a new perspective on cut generation in the context of Benders decomposition. The approach, which is based on the relation between the alternative polyhedron and the reverse polar set, helps us to improve established cut selection procedures for Benders cuts, like the one suggested by Fischetti et al. (Math Program Ser B 124(1–2):175–182, 2010). Our modified version of that criterion produces cuts which are always supporting and, unless in rare special cases, facet-defining. We discuss our approach in relation to the state of the art in cut generation for Benders decomposition. In particular, we refer to Pareto-optimality and facet-defining cuts and observe that each of these criteria can be matched to a particular subset of parametrizations for our cut generation framework. As a consequence, our framework covers the method to generate facet-defining cuts proposed by Conforti and Wolsey (Math Program Ser A 178:1–20, 2018) as a special case. We conclude the paper with a computational evaluation of the proposed cut selection method. For this, we use different instances of a capacity expansion problem for the european power system.
- Sprache
-
Englisch
- Erschienen in
-
Journal: Mathematical Methods of Operations Research ; ISSN: 1432-5217 ; Volume: 94 ; Year: 2021 ; Issue: 3 ; Pages: 383-412 ; Berlin, Heidelberg: Springer
- Klassifikation
-
Wirtschaft
- Thema
-
Benders decomposition
Decomposition methods
Cutting planes
Reverse polar set
Alternative polyhedron
Pareto optimal cuts
Facet defining cuts
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Brandenberg, René
Stursberg, Paul
- Ereignis
-
Veröffentlichung
- (wer)
-
Springer
- (wo)
-
Berlin, Heidelberg
- (wann)
-
2021
- DOI
-
doi:10.1007/s00186-021-00756-8
- Letzte Aktualisierung
-
10.03.2025, 11:45 MEZ
Datenpartner
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Artikel
Beteiligte
- Brandenberg, René
- Stursberg, Paul
- Springer
Entstanden
- 2021
Ähnliche Objekte (12)
Refined cut selection for benders decomposition: applied to network capacity expansion problems
Singular value decomposition versus sparse grids: Refined complexity estimates
Evaluating EYM amplitudes in four dimensions by refined graphic expansion
Generalized Ward identities and refined topological expansion of Toda conformal blocks
Decomposition of Feynman integrals on the maximal cut by intersection numbers
Computational Evaluation of Cut-Strengthening Techniques in Logic-Based Benders’ Decomposition
On refined Chern–Simons and refined ABJ matrix models
Refined probabilistic abstraction
A volumetric locking-free polygonal finite element formulation applied to locally refined Voronoi meshes
On decomposition and multiobjective-based column and disjunctive cut generation for MINLP
Asymptotic expansion of β matrix models in the multi-cut regime
Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms
Refined cut selection for benders decomposition: applied to network capacity expansion problems
Singular value decomposition versus sparse grids: Refined complexity estimates
Evaluating EYM amplitudes in four dimensions by refined graphic expansion
Generalized Ward identities and refined topological expansion of Toda conformal blocks
Decomposition of Feynman integrals on the maximal cut by intersection numbers
Computational Evaluation of Cut-Strengthening Techniques in Logic-Based Benders’ Decomposition
On refined Chern–Simons and refined ABJ matrix models
Refined probabilistic abstraction
A volumetric locking-free polygonal finite element formulation applied to locally refined Voronoi meshes
On decomposition and multiobjective-based column and disjunctive cut generation for MINLP
Asymptotic expansion of β matrix models in the multi-cut regime
Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms
Refined cut selection for benders decomposition: applied to network capacity expansion problems
Singular value decomposition versus sparse grids: Refined complexity estimates
Evaluating EYM amplitudes in four dimensions by refined graphic expansion
Generalized Ward identities and refined topological expansion of Toda conformal blocks
Decomposition of Feynman integrals on the maximal cut by intersection numbers
Computational Evaluation of Cut-Strengthening Techniques in Logic-Based Benders’ Decomposition
On refined Chern–Simons and refined ABJ matrix models
Refined probabilistic abstraction
A volumetric locking-free polygonal finite element formulation applied to locally refined Voronoi meshes
On decomposition and multiobjective-based column and disjunctive cut generation for MINLP
Asymptotic expansion of β matrix models in the multi-cut regime