The Stochastic Bilevel Selection Problem

Jannik Irmai ()
Additional contact information
Jannik Irmai: TU Dresden

Chapter Chapter 7 in Operations Research Proceedings 2022, 2023, pp 51-57 from Springer

Abstract: Abstract We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack, while the follower chooses a feasible packing maximizing his own profit. The leader’s aim is to optimize a linear objective function in the follower’s solution, but with respect to item values that can be different from the follower’s item values. We address a stochastic version of this problem where the follower’s profits are uncertain and only a probability distribution is known. This problem is #P-hard for the case of independently and uniformly distributed follower profits. In this paper, efficient algorithms are developed for the special case where all items have unit weight, as is the case in the bilevel selection problem. Generalizing these results to the case of arbitrary weights leads to pseudo-polynomial time algorithms for the bilevel continuous knapsack problem.

Keywords: Bilevel optimization; Stochastic optimization; Complexity (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-24907-5_7

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_7

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().