Unboundedness in Bilevel Optimization

• 成果类型: Article; Early Access
• 署名作者: Rodrigues, Barbara; Carvalho, Margarida; Anjos, Miguel F.; Sugishita, Nagisa
• 署名单位: University of Edinburgh; University of Edinburgh; Heriot Watt University; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02344-2
• 发表日期: 2026-03-26
• 关键词: Computational Complexity; unbounded; bilevel optimization; Multilevel Optimization; LINEAR BILEVEL; algorithm; PROGRAMS; branch

摘要

Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel and multilevel optimization by studying its computational complexity. We show that deciding whether an optimistic linear bilevel problem is unbounded is strongly NP-complete, even without coupling constraints. Furthermore, we extend the hardness result to the linear multilevel case, by showing that for each extra level added, the decision problem of checking unboundedness moves up a level in the polynomial hierarchy. Deciding unboundedness of a mixed-integer multilevel problem is shown to be one level higher in the polynomial complexity hierarchy than the decision problem for linear multilevel problem with the same number of levels. Finally, we introduce two algorithmic approaches to determine whether a linear bilevel problem is unbounded and, if so, return a certificate of unboundedness. This certificate consists of a direction of unboundedness and corresponding bilevel feasible point. We present a proof of concept of these algorithmic approaches on some relevant examples, and provide a brief computational comparison.