Autor(en): Buchheim, Christoph
Henke, Dorothee
Titel: The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective
Sprache (ISO): en
Zusammenfassung: 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.
Schlagwörter: Bilevel optimization
Robust optimization
Interval order
URI: http://hdl.handle.net/2003/41127
http://dx.doi.org/10.17877/DE290R-22974
Erscheinungsdatum: 2022-01-02
Enthalten in den Sammlungen:Lehrstuhl V Diskrete Optimierung

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
s10898-021-01117-9.pdf483.95 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.