A framework for generalized Benders' decomposition and its application to multilevel optimization

DOI10.1007/S10107-021-01763-7zbMATH Open1506.90165arXiv2104.06496OpenAlexW4210506818MaRDI QIDQ2097644FDOQ2097644

Authors: Suresh Bolusani, Ted K. Ralphs 

Publication date: 14 November 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We describe a framework for reformulating and solving optimization problems that generalizes the well-known framework originally introduced by Benders. We discuss details of the application of the procedures to several classes of optimization problems that fall under the umbrella of multilevel/multistage mixed integer linear optimization problems. The application of this abstract framework to this broad class of problems provides new insights and a broader interpretation of the core ideas, especially as they relate to duality and the value functions of optimization problems that arise in this context.

Full work available at URL: https://arxiv.org/abs/2104.06496

Recommendations

• A unified framework for multistage mixed integer linear optimization
• Extension of the generalized benders' decomposition
• The Benders dual decomposition method
• Open problems on Benders decomposition algorithm
• scientific article; zbMATH DE number 4106600

zbMATH Keywords

bilevel optimizationdualityvalue functionmixed integer optimizationBenders' decomposition

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11) Duality theory (optimization) (49N15) Algorithmic game theory and complexity (91A68)

Cites Work

• Mixed-integer nonlinear optimization
• Partitioning procedures for solving mixed-variables programming problems
• Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming
• The polynomial hierarchy and a simple model for competitive analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization.
• Logic-based Benders decomposition
• Resolution method for mixed integer bi-level linear problems based on decomposition technique
• Generalized Benders decomposition
• Title not available (Why is that?)
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• Mathematical Programs with Optimization Problems in the Constraints
• Valid inequalities for mixed integer linear programs
• Removing Arcs from a Network
• Parametric global optimisation for bilevel programming
• Disjunctive Programming
• The polynomial-time hierarchy
• The Mixed Integer Linear Bilevel Programming Problem
• Cutting-plane theory: Algebraic methods
• Minimal inequalities
• Algorithms for solving the mixed integer two-level linear programming problem
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Minimal Inequalities and Subadditive Duality
• Discrete linear bilevel programming problem
• Parametric integer programming algorithm for bilevel mixed integer programs
• An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions
• Integer programming duality: Price functions and sensitivity analysis
• Title not available (Why is that?)
• The value function of an integer program
• Constructive characterizations of the value-function of a mixed-integer program. I
• The value function of a mixed integer program. II
• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• Enhanced exact algorithms for discrete bilevel linear problems
• The value function of a mixed integer program: I
• Duality for mixed-integer linear programs
• A mixed-integer bilevel programming approach for a competitive prioritized set covering problem
• A new general-purpose algorithm for mixed-integer bilevel linear programs
• A value-function-based exact approach for the bilevel mixed-integer programming problem
• A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
• Title not available (Why is that?)
• The Benders decomposition algorithm: a literature review
• A closed-form representation of mixed-integer program value functions
• Polyhedral techniques in combinatorial optimization I: Theory
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• Bilevel knapsack with interdiction constraints
• The Watermelon Algorithm for The Bilevel Integer Linear Programming Problem
• On the use of intersection cuts for bilevel optimization
• Technical note -- There's no free lunch: on the hardness of choosing a correct big-\(M\) in bilevel optimization
• A unified framework for multistage mixed integer linear optimization
• A survey on mixed-integer programming techniques in bilevel optimization

Cited In (7)

• Special issue: Global solution of integer, stochastic and nonconvex optimization problems
• Multi-stage Benders Decomposition for Optimizing Multicore Architectures
• Progressively strengthening and tuning MIP solvers for reoptimization
• The MIP workshop 2023 computational competition on reoptimization
• A unified framework for multistage mixed integer linear optimization
• Rejection-proof mechanisms for multi-agent kidney exchange
• Generalized Benders decomposition for one class of MINLPs with vector conic constraint

This page was built for publication: A framework for generalized Benders' decomposition and its application to multilevel optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097644)