The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
From MaRDI portal
Publication:2154452
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.
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
Cites work
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Representation and Economic Interpretation of a Two-Level Programming Problem
- A dynamic programming algorithm for the bilevel Knapsack problem
- A faster algorithm for the continuous bilevel knapsack problem
- A polynomial algorithm for a continuous bilevel knapsack problem
- A study on the computational complexity of the bilevel knapsack problem
- An exact algorithm for bilevel 0-1 knapsack problems
- An overview of bilevel optimization
- Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints
- Bilevel programming problems. Theory, algorithms and applications to energy networks
- Bilevel programming with knapsack constraints
- Closing the gap in linear bilevel optimization: a new valid primal-dual inequality
- Complexity of near-optimal robust versions of multilevel optimization problems
- Discrete-variable extremum problems
- Existence, uniqueness, and computation of robust Nash equilibria in a class of multi-leader-follower games
- Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints
- Finding the upper envelope of n line segments in O(n log n) time
- Global optimality test for maximin solution of bilevel linear programming with ambiguous lower-level objective function
- New Branch-and-Bound Rules for Linear Bilevel Programming
- On a class of bilevel linear mixed-integer programs in adversarial settings
- On the approximability of average completion time scheduling under precedence constraints.
- Pessimistic bilevel optimization
- Robust combinatorial optimization under convex and discrete cost uncertainty
- Robust discrete optimization and its applications
- The Price of Robustness
- The bilevel knapsack problem with stochastic right-hand sides
Cited in
(6)- 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
- A survey on bilevel optimization under uncertainty
- The stochastic bilevel continuous knapsack problem with uncertain follower's objective
- Shortest path network interdiction with asymmetric uncertainty
- Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
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)
