Full metadata record
DC FieldValueLanguage
dc.contributor.authorBuchheim, Christoph-
dc.contributor.authorHenke, Dorothee-
dc.description.abstractWe 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.de
dc.relation.ispartofseriesJournal of global optimization;vol. 83, pp 803–824 (2022)-
dc.subjectBilevel optimizationde
dc.subjectRobust optimizationde
dc.subjectInterval orderde
dc.titleThe robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objectivede
dcterms.accessRightsopen access-
eldorado.secondarypublication.primarycitationJournal of Global Optimization. Vol. 83. 2022, pp 803–824de
Appears in Collections:Lehrstuhl V Diskrete Optimierung

Files in This Item:
File Description SizeFormat 
s10898-021-01117-9.pdf483.95 kBAdobe PDFView/Open

This item is protected by original copyright

Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.