The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective

DOI10.1007/S10898-021-01117-9zbMATH Open1495.90147arXiv1903.02810OpenAlexW4205717391MaRDI QIDQ2154452FDOQ2154452

Authors: Christoph Buchheim, Dorothee Henke 

Publication date: 19 July 2022

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

Abstract: We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower's problem. More precisely, adopting the robust optimization approach and assuming that the follower's profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower's reaction from the leader's perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader's objective function.

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

Recommendations

• The stochastic bilevel continuous knapsack problem with uncertain follower's objective
• The bilevel knapsack problem with stochastic right-hand sides
• A Stackelberg knapsack game with weight control
• An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
• Improved approximation algorithms for a bilevel knapsack problem

zbMATH Keywords

bilevel optimizationrobust optimizationinterval order

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Robustness in mathematical programming (90C17)

Cites Work

• Title not available (Why is that?)
• An overview of bilevel optimization
• The Price of Robustness
• New Branch-and-Bound Rules for Linear Bilevel Programming
• Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints
• Pessimistic bilevel optimization
• Robust discrete optimization and its applications
• A Representation and Economic Interpretation of a Two-Level Programming Problem
• Bilevel programming problems. Theory, algorithms and applications to energy networks
• A dynamic programming algorithm for the bilevel Knapsack problem
• Existence, uniqueness, and computation of robust Nash equilibria in a class of multi-leader-follower games
• Discrete-variable extremum problems
• Finding the upper envelope of n line segments in O(n log n) time
• Bilevel programming with knapsack constraints
• Complexity of near-optimal robust versions of multilevel optimization problems
• An exact algorithm for bilevel 0-1 knapsack problems
• Robust combinatorial optimization under convex and discrete cost uncertainty
• The bilevel knapsack problem with stochastic right-hand sides
• On the approximability of average completion time scheduling under precedence constraints.
• A study on the computational complexity of the bilevel knapsack problem
• Global optimality test for maximin solution of bilevel linear programming with ambiguous lower-level objective function
• On a class of bilevel linear mixed-integer programs in adversarial settings
• Closing the gap in linear bilevel optimization: a new valid primal-dual inequality
• A polynomial algorithm for a continuous bilevel knapsack problem
• A faster algorithm for the continuous bilevel knapsack problem
• Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints

Cited In (6)

• A survey on bilevel optimization under uncertainty
• Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
• The stochastic bilevel continuous knapsack problem with uncertain follower's objective
• Shortest path network interdiction with asymmetric uncertainty
• On a computationally ill-behaved bilevel problem with a continuous and nonconvex lower level
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023

This page was built for publication: The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective

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