A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
From MaRDI portal
Publication:670656
DOI10.1007/S10898-018-0679-1zbMATH Open1417.90106arXiv1707.06196OpenAlexW3162651815MaRDI QIDQ670656FDOQ670656
Dajun Yue, Fengqi You, Jiyao Gao, Bo Zeng
Publication date: 18 March 2019
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: We propose an extended variant of the reformulation and decomposition algorithm for solving a special class of mixed-integer bilevel linear programs (MIBLPs) where continuous and integer variables are involved in both upper- and lower-level problems. In particular, we consider MIBLPs with upper-level constraints that involve lower-level variables. We assume that the inducible region is nonempty and all variables are bounded. By using the reformulation and decomposition scheme, an MIBLP is first converted into its equivalent single-level formulation, then computed by a column-and-constraint generation based decomposition algorithm. The solution procedure is enhanced by a projection strategy that does not require the relatively complete response property. To ensure its performance, we prove that our new method converges to the global optimal solution in a finite number of iterations. A large-scale computational study on random instances and instances of hierarchical supply chain planning are presented to demonstrate the effectiveness of the algorithm.
Full work available at URL: https://arxiv.org/abs/1707.06196
global optimizationprojectionhierarchical supply chain planningmixed integer bilevel linear programreformulation and decomposition methodsingle-level reformulation
Cites Work
- Complementarity problems in GAMS and the PATH solver
- Practical bilevel optimization. Algorithms and applications
- Bilevel and multilevel programming: A bibliography review
- Foundations of bilevel programming
- Global optimization of mixed-integer bilevel programming problems
- Title not available (Why is that?)
- Pessimistic Bilevel Optimization
- Global solution of bilevel programs with a nonconvex inner program
- Infinitely constrained optimization problems
- Links between linear bilevel and mixed 0-1 programming problems
- On generalized semi-infinite optimization and bilevel optimization
- Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints
- Global solution of nonlinear mixed-integer bilevel programs
- Resolution method for mixed integer bi-level linear problems based on decomposition technique
- Mathematical Programs with Optimization Problems in the Constraints
- Parametric global optimisation for bilevel programming
- Generalized semi-infinite optimization: A first order optimality condition and examples
- Global solution of semi-infinite programs
- New formulations and valid inequalities for a bilevel pricing problem
- The Mixed Integer Linear Bilevel Programming Problem
- An algorithm for the mixed-integer nonlinear bilevel programming problem
- Metaheuristics for bi-level optimization
- Algorithms for solving the mixed integer two-level linear programming problem
- Solving two-stage robust optimization problems using a column-and-constraint generation method
- Discrete linear bilevel programming problem
- On linear programs with linear complementarity constraints
- Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. I: theoretical development
- Parametric integer programming algorithm for bilevel mixed integer programs
- A class of algorithms for mixed-integer bilevel min-max optimization
- An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions
- New product introduction against a predator: A bilevel mixed-integer programming approach
- Title not available (Why is that?)
- The nonlinear bilevel programming problem:formulations,regularity and optimality conditions
- Solving minimax problems by interval methods
- Bilevel programming and the separation problem
- Linear bilevel programming with upper level constraints depending on the lower level solution
- The Adaptive Convexification Algorithm: A Feasible Point Method for Semi-Infinite Programming
- A nonconvex max-min problem
- Global optimization of generalized semi-infinite programs via restriction of the right hand side
- Capacitated plant selection in a decentralized manufacturing environment: a bilevel optimization approach
- Double penalty method for bilevel optimization problems
- Capacity planning with competitive decision-makers: trilevel MILP formulation, degeneracy, and solution approaches
- A mixed-integer bilevel programming approach for a competitive prioritized set covering problem
- Adjustable robust optimization models for a nonlinear two-period system
- Intersection Cuts for Bilevel Optimization
- A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
- A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem
Cited In (20)
- A framework for generalized Benders' decomposition and its application to multilevel optimization
- A single-level reformulation of mixed integer bilevel programming problems
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
- An exact method for binary fortification games
- An enhanced branch-and-bound algorithm for bilevel integer linear programming
- Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints
- Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography
- Interdicting restructuring networks with applications in illicit trafficking
- SOCP-based disjunctive cuts for a class of integer nonlinear bilevel programs
- Bilevel programming solution algorithms for optimal price-bidding of energy producers in multi-period day-ahead electricity markets with non-convexities
- A survey on mixed-integer programming techniques in bilevel optimization
- Bilevel optimization for joint scheduling of production and energy systems
- Mixed-integer bilevel representability
- Bilevel Integer Programs with Stochastic Right-Hand Sides
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- Managing Product Transitions: A Bilevel Programming Approach
- An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities
- An exact solution algorithm for integer bilevel programming with application in energy market optimization
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
Uses Software
This page was built for publication: A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670656)
