A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908665669222400 |
|---|---|
| author | Ketkov, Sergey S. Prokopyev, Oleg A. |
| author_facet | Ketkov, Sergey S. Prokopyev, Oleg A. |
| contents | Bilevel linear programs (BLPs) form a class of hierarchical decision-making problems in which both the upper-level and the lower-level decision-makers, known as the leader and the follower, respectively, solve linear optimization problems. It is well-known that general BLPs are strongly $NP$-hard, even when the leader's and the follower's objective functions are exact opposites. However, the complexity classification of BLPs remains incomplete when one of the decision-makers has a fixed number of variables or constraints. In particular, it has been shown that optimistic BLPs are polynomially solvable when the number of follower variables is fixed, whereas both optimistic and pessimistic BLPs remain $NP$-hard even with a single leader variable and no upper-level constraints. In this note, we close the remaining gap in this complexity landscape. Specifically, we prove that BLPs are polynomially solvable in both the optimistic and the pessimistic settings when the number of follower constraints is fixed. In contrast, we also show that the pessimistic problem with a fixed number of follower variables is strongly $NP$-hard. To the best of our knowledge, this is the first result demonstrating that, under comparable assumptions, the pessimistic formulation is one complexity class harder than its optimistic counterpart. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15592 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions Ketkov, Sergey S. Prokopyev, Oleg A. Computational Complexity Bilevel linear programs (BLPs) form a class of hierarchical decision-making problems in which both the upper-level and the lower-level decision-makers, known as the leader and the follower, respectively, solve linear optimization problems. It is well-known that general BLPs are strongly $NP$-hard, even when the leader's and the follower's objective functions are exact opposites. However, the complexity classification of BLPs remains incomplete when one of the decision-makers has a fixed number of variables or constraints. In particular, it has been shown that optimistic BLPs are polynomially solvable when the number of follower variables is fixed, whereas both optimistic and pessimistic BLPs remain $NP$-hard even with a single leader variable and no upper-level constraints. In this note, we close the remaining gap in this complexity landscape. Specifically, we prove that BLPs are polynomially solvable in both the optimistic and the pessimistic settings when the number of follower constraints is fixed. In contrast, we also show that the pessimistic problem with a fixed number of follower variables is strongly $NP$-hard. To the best of our knowledge, this is the first result demonstrating that, under comparable assumptions, the pessimistic formulation is one complexity class harder than its optimistic counterpart. |
| title | A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.15592 |