期刊
OPERATIONS RESEARCH LETTERS
卷 49, 期 5, 页码 703-707出版社
ELSEVIER
DOI: 10.1016/j.orl.2021.07.009
关键词
Bilevel optimization; Robust optimization; Complexity
资金
- Deutsche Forschungsgemeinschaft(DFG) [BU 2313/6]
This study examines the complexity of bilevel combinatorial optimization with uncertainty in the follower's objective using a robust optimization approach. It shows that under interval uncertainty, the robust counterpart of the bilevel problem can be Sigma(P)(2)- hard, even when the certain bilevel problem is NP-equivalent and the follower's problem is tractable. Conversely, in the case of discrete uncertainty, the robust bilevel problem is at most one level harder than the follower's problem.
We investigate the complexity of bilevel combinatorial optimization with uncertainty in the follower's objective, in a robust optimization approach. We show that the robust counterpart of the bilevel problem under interval uncertainty can be Sigma(P)(2)- hard, even when the certain bilevel problem is NP-equivalent and the follower's problem is tractable. On the contrary, in the discrete uncertainty case, the robust bilevel problem is at most one level harder than the follower's problem. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据