Optimization Online


Exact Methods for Discrete Gamma-Robust Min-Max Problems

Yasmine Beck(becky***at***uni-trier.de)
Ivana Ljubić(ljubic***at***essec.edu)
Martin Schmidt(martin.schmidt***at***uni-trier.de)

Abstract: Developing solution methods for mixed-integer bilevel problems is known to be a challenging task - even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty due to some kind of bounded rationality. We study mixed-integer min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a Gamma-robust approach, we present an extended formulation and a multi-scenario formulation to model this type of problem. For both settings, we provide a generic branch-and-cut framework. Specifically, we investigate interdiction problems with a monotone Gamma-robust follower and we derive problem-tailored cuts, which extend existing techniques that have been proposed for the deterministic case. For the Gamma-robust knapsack interdiction problem, we computationally evaluate and compare the performance of the proposed algorithms for both modeling approaches.

Keywords: Bilevel optimization, Robust optimization, Knapsack interdiction, Mixed-integer programming, Branch-and-Cut

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Robust Optimization


Download: [PDF]

Entry Submitted: 11/10/2021
Entry Accepted: 11/10/2021
Entry Last Modified: 11/10/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society