Decision Problems in Multilevel Linear Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915984033447936 |
|---|---|
| author | Sugishita, Nagisa Carvalho, Margarida |
| author_facet | Sugishita, Nagisa Carvalho, Margarida |
| contents | We study the computational complexity of decision problems in $k$-level linear programming (LP). Seminal work by Jeroslow establishes that determining whether the optimal objective value of a $k$-level LP is at least as good as a given threshold is $Σ^{\mathrm{p}}_{k-1}$-hard. In this paper, we demonstrate the matching upper bound and thereby prove that this problem is $Σ^{\mathrm{p}}_{k-1}$-complete. To this end, we show that the feasible region of a $k$-level LP can be expressed as a union of sets defined by weak and strict linear inequalities. Moreover, we show that the decision of the unboundedness is $Σ^{\mathrm{p}}_{k-1}$-complete. Finally, we discuss the extension of our results to the mixed-binary cases. In short, this work closes lasting open questions in multilevel programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_04929 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Decision Problems in Multilevel Linear Programming Sugishita, Nagisa Carvalho, Margarida Optimization and Control We study the computational complexity of decision problems in $k$-level linear programming (LP). Seminal work by Jeroslow establishes that determining whether the optimal objective value of a $k$-level LP is at least as good as a given threshold is $Σ^{\mathrm{p}}_{k-1}$-hard. In this paper, we demonstrate the matching upper bound and thereby prove that this problem is $Σ^{\mathrm{p}}_{k-1}$-complete. To this end, we show that the feasible region of a $k$-level LP can be expressed as a union of sets defined by weak and strict linear inequalities. Moreover, we show that the decision of the unboundedness is $Σ^{\mathrm{p}}_{k-1}$-complete. Finally, we discuss the extension of our results to the mixed-binary cases. In short, this work closes lasting open questions in multilevel programming. |
| title | Decision Problems in Multilevel Linear Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.04929 |