Complexity of Bilevel Linear Programming with a Single Upper-Level Variable
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910061038665728 |
|---|---|
| author | Sugishita, Nagisa Carvalho, Margarida |
| author_facet | Sugishita, Nagisa Carvalho, Margarida |
| contents | Bilevel linear programming (LP) is one of the simplest classes of bilevel optimization problems, yet it is known to be NP-hard in general. Specifically, determining whether the optimal objective value of a bilevel LP is at least as good as a given threshold, a standard decision version of the problem, is NP-complete. However, this decision problem becomes tractable when either the number of lower-level variables or the number of lower-level constraints is fixed, which prompts the question: What if restrictions are placed on the upper-level problem? In this paper, we address this gap by showing that the decision version of bilevel LP remains NP-complete even when there is only a single upper-level variable, no upper-level constraints (apart from the constraint enforcing optimality of the lower-level decision) and all variables are bounded between 0 and 1. This result implies that fixing the number of variables or constraints in the upper-level problem alone does not lead to tractability in general. On the positive side, we show that there is a polynomial-time algorithm that finds a local optimal solution of such a rational bilevel LP instance. We also demonstrate that many combinatorial optimization problems, such as the knapsack problem and the traveling salesman problem, can be written as such a bilevel LP instance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21126 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of Bilevel Linear Programming with a Single Upper-Level Variable Sugishita, Nagisa Carvalho, Margarida Optimization and Control Bilevel linear programming (LP) is one of the simplest classes of bilevel optimization problems, yet it is known to be NP-hard in general. Specifically, determining whether the optimal objective value of a bilevel LP is at least as good as a given threshold, a standard decision version of the problem, is NP-complete. However, this decision problem becomes tractable when either the number of lower-level variables or the number of lower-level constraints is fixed, which prompts the question: What if restrictions are placed on the upper-level problem? In this paper, we address this gap by showing that the decision version of bilevel LP remains NP-complete even when there is only a single upper-level variable, no upper-level constraints (apart from the constraint enforcing optimality of the lower-level decision) and all variables are bounded between 0 and 1. This result implies that fixing the number of variables or constraints in the upper-level problem alone does not lead to tractability in general. On the positive side, we show that there is a polynomial-time algorithm that finds a local optimal solution of such a rational bilevel LP instance. We also demonstrate that many combinatorial optimization problems, such as the knapsack problem and the traveling salesman problem, can be written as such a bilevel LP instance. |
| title | Complexity of Bilevel Linear Programming with a Single Upper-Level Variable |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.21126 |