Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem

DOI10.1007/S12532-023-00244-6zbMath1527.90133OpenAlexW4383721625MaRDI QIDQ6062886

Martin Schmidt, Ivana Ljubić, Yasmine Beck

Publication date: 2 December 2023

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-023-00244-6

zbMATH Keywords

robust optimizationbranch-and-cutmixed-integer programmingbilevel optimizationknapsack interdiction

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Fuzzy and other nonstochastic uncertainty mathematical programming (90C70)

Cites Work

• Minimum edge blocker dominating set problem
• 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
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Construction of a real-world bilevel linear programming model of the highway network design problem
• Minimum cost edge blocker clique problem
• Valid inequalities for mixed integer linear programs
• Blockers and transversals
• Partitioning procedures for solving mixed-variables programming problems
• Robust discrete optimization and network flows
• Foundations of bilevel programming
• A dynamic reformulation heuristic for generalized interdiction problems
• Bilevel road pricing: theoretical analysis and optimality conditions
• On the use of intersection cuts for bilevel optimization
• Bilevel programming in traffic planning: Models, methods and challenge
• A branch-and-cut algorithm for the edge interdiction clique problem
• On the complexity of robust bilevel optimization with uncertain follower's objective
• A robust approach for modeling limited observability in bilevel optimization
• The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation
• Complexity of near-optimal robust versions of multilevel optimization problems
• A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty
• A survey of network interdiction models and algorithms
• Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints
• A multilevel model of the European entry-exit gas market
• A note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problems
• Generalized Benders decomposition
• Stochastic Network Interdiction
• A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing
• Introduction to Stochastic Programming
• Distributionally Robust Optimization and Its Tractable Approximations
• Theory and Applications of Robust Optimization
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Intersection Cuts for Bilevel Optimization
• Bilevel Knapsack with Interdiction Constraints
• The Price of Robustness
• A Representation and Economic Interpretation of a Two-Level Programming Problem
• New Branch-and-Bound Rules for Linear Bilevel Programming
• A problem in network interdiction
• A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs
• Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs
• Reduction of the bilevel stochastic optimization problem with quantile objective function to a mixed‐integer problem
• Minimum vertex blocker clique problem
• Shortest-path network interdiction
• A Complexity and Approximability Study of the Bilevel Knapsack Problem
• A Bilevel Stochastic Programming Problem with Random Parameters in the Follower’s Objective Function
• Bilevel Linear Optimization Under Uncertainty
• A Unified Framework for Multistage Mixed Integer Linear Optimization
• Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
• On Bilevel Optimization with Inexact Follower
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• The Mixed Integer Linear Bilevel Programming Problem
• Risk-Averse Models in Bilevel Stochastic Linear Programming
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• A survey on bilevel optimization under uncertainty
• Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds
• A survey on mixed-integer programming techniques in bilevel optimization

This page was built for publication: Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem