A class of algorithms for mixed-integer bilevel min-max optimization

DOI10.1007/s10898-015-0274-7zbMath1380.90197OpenAlexW2062530151MaRDI QIDQ330266

J. Cole Smith, Jean-Philippe P. Richard, Yen Tang

Publication date: 25 October 2016

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-015-0274-7

zbMATH Keywords

algorithmsbilevel programminginteger programinginterdiction problems

Mathematics Subject Classification ID

Mixed integer programming (90C11) Minimax problems in mathematical programming (90C47) Hierarchical games (including Stackelberg games) (91A65)

Related Items

Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets ⋮ Bilevel Integer Programs with Stochastic Right-Hand Sides ⋮ Min-Max Optimal Design of Two-Armed Trials with Side Information ⋮ On unbounded and binary parameters in multi-parametric programming: applications to mixed-integer bilevel optimization and duality theory ⋮ Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem ⋮ A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints ⋮ Why there is no need to use a big-\(M\) in linear bilevel optimization: a computational study of two ready-to-use approaches ⋮ Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds ⋮ On designing networks resilient to clique blockers ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ An exact approach for the bilevel knapsack problem with interdiction constraints and extensions ⋮ An exact method for binary fortification games ⋮ On Bilevel Optimization with Inexact Follower ⋮ Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function ⋮ Interdiction Games and Monotonicity, with Application to Knapsack Problems ⋮ The maximum clique interdiction problem ⋮ A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs ⋮ Improved \(x\)-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks ⋮ A dynamic reformulation heuristic for generalized interdiction problems ⋮ On a class of bilevel linear mixed-integer programs in adversarial settings ⋮ An enhanced branch-and-bound algorithm for bilevel integer linear programming ⋮ A branch-and-cut algorithm for the edge interdiction clique problem ⋮ A survey of network interdiction models and algorithms ⋮ Outer approximation for global optimization of mixed-integer quadratic bilevel problems ⋮ Provable training set debugging for linear regression ⋮ Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty ⋮ Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method ⋮ Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography

Cites Work

• Unnamed Item
• Unnamed Item
• Approaches to sensitivity analysis in linear programming
• A dynamic programming algorithm for the bilevel Knapsack problem
• The k most vital arcs in the shortest path problem
• Most vital links and nodes in weighted networks
• Foundations of bilevel programming
• Deterministic network interdiction
• Finding the most vital arcs in a network
• Discrete linear bilevel programming problem
• One-level reformulation of the bilevel Knapsack problem using dynamic programming
• Exact solution approach for a class of nonlinear bilevel knapsack problems
• On the continuity of the value of a linear program and of related polyhedral-valued multifunctions
• On two-level optimization
• New Branch-and-Bound Rules for Linear Bilevel Programming
• Finding the n Most Vital Links in Flow Networks
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Maximizing the minimum source-sink path subject to a budget constraint
• A problem in network interdiction
• Minimum vertex blocker clique problem
• Shortest-path network interdiction
• A Complexity and Approximability Study of the Bilevel Knapsack Problem
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Two-Level Linear Programming
• The Mixed Integer Linear Bilevel Programming Problem
• Nonlinear Programming
• The Theory of Max-Min, with Applications
• Removing Arcs from a Network
• Bilevel programming with knapsack constraints