pith. sign in

arxiv: 2605.04929 · v1 · submitted 2026-05-06 · 🧮 math.OC

Decision Problems in Multilevel Linear Programming

Nagisa Sugishita , Margarida Carvalho This is my paper

Pith reviewed 2026-05-08 15:52 UTC · model grok-4.3

classification 🧮 math.OC
keywords multilevel linear programmingcomputational complexitypolynomial hierarchydecision problemsfeasible regionunboundednessmixed-binary programs
0
0 comments X

The pith

The decision whether a k-level linear program's optimal value meets a threshold is Σ^p_{k-1}-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that deciding whether the optimal objective value of a k-level linear program meets or exceeds a given threshold is Σ^p_{k-1}-complete. Jeroslow had established the hardness result; the new contribution supplies the matching upper bound. The proof proceeds by rewriting the feasible region of a k-level LP as a union of sets defined by weak and strict linear inequalities. The same completeness holds for the decision problem of unboundedness. The results extend to mixed-binary multilevel programs and close several longstanding open questions.

Core claim

The authors show that the feasible region of a k-level linear program can be expressed as a union of sets defined by weak and strict linear inequalities. This representation permits a direct reduction establishing membership in Σ^p_{k-1}. Combined with the known hardness, the threshold decision problem is therefore Σ^p_{k-1}-complete. The same argument shows that deciding whether a k-level LP is unbounded is Σ^p_{k-1}-complete, and the completeness carries over to mixed-binary cases.

What carries the argument

The representation of the feasible region of a k-level LP as a union of sets defined by weak and strict linear inequalities.

If this is right

  • The decision problem of unboundedness for k-level LPs is Σ^p_{k-1}-complete.
  • The completeness results extend to mixed-binary multilevel linear programs.
  • Decision versions of multilevel linear programs are now fully located inside the polynomial hierarchy.
  • No polynomial-time algorithm exists for these decision problems unless the polynomial hierarchy collapses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The inequality-union representation may support new practical algorithms that exploit the disjunctive structure of multilevel feasible sets.
  • Analogous rewriting techniques could be tested on nonlinear or integer multilevel programs to obtain similar complexity classifications.
  • The results tighten the connection between multilevel optimization and quantified Boolean formulas, suggesting transfer of proof techniques in both directions.

Load-bearing premise

The feasible region of a k-level LP can be expressed as a union of sets defined by weak and strict linear inequalities in a form that permits a direct reduction to a Σ^p_{k-1} decision problem.

What would settle it

A concrete k-level linear program whose feasible region cannot be written as the required union of weak-and-strict inequality sets, or whose optimal-value threshold decision lies outside Σ^p_{k-1}.

read the original abstract

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 $\Sigma^{\mathrm{p}}_{k-1}$-hard. In this paper, we demonstrate the matching upper bound and thereby prove that this problem is $\Sigma^{\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 $\Sigma^{\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves that the decision problem for k-level linear programming—specifically, whether the optimal objective value is at least a given threshold—is Σ^p_{k-1}-complete. This is achieved by establishing a matching upper bound to Jeroslow's Σ^p_{k-1}-hardness result through a representation of the k-level feasible region as a union of sets defined by weak and strict linear inequalities. The paper also shows Σ^p_{k-1}-completeness for the unboundedness decision problem and discusses extensions to mixed-binary multilevel programs.

Significance. If the upper bound holds, the result resolves a long-standing open question in the complexity of multilevel optimization by providing completeness for the decision versions of k-level LPs. This has implications for understanding the polynomial hierarchy in hierarchical decision-making models and could inform algorithmic approaches or hardness results in related fields like game theory and operations research.

major comments (1)
  1. [Feasible-region representation (abstract and technical development of the upper bound)] The central upper-bound argument rests on rewriting the feasible region of a k-level LP as a union of sets defined by weak and strict linear inequalities (abstract). Standard enumerations of active bases or binding constraints across the k-1 lower levels produce exponentially many disjuncts in the total number of variables and constraints. Membership in such a union then requires an additional existential quantifier to select the correct disjunct before verifying the linear inequalities and objective threshold; this would place the problem in Σ^p_k rather than Σ^p_{k-1}. The manuscript must explicitly bound the number of sets (or provide a succinct encoding such as a polynomial-size circuit or implicit choice variable) and show that the reduction to a known Σ^p_{k-1}-complete language stays within the claimed class.
minor comments (1)
  1. [Abstract] The phrase 'the decision of the unboundedness' in the abstract is ambiguous; clarify whether this means deciding if the multilevel program is unbounded or deciding the status of unboundedness relative to the threshold.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to make the succinctness of the disjunct encoding explicit in the upper-bound argument. We address the concern below and will revise the manuscript accordingly to strengthen the presentation of the quantifier structure.

read point-by-point responses

  1. Referee: The central upper-bound argument rests on rewriting the feasible region of a k-level LP as a union of sets defined by weak and strict linear inequalities (abstract). Standard enumerations of active bases or binding constraints across the k-1 lower levels produce exponentially many disjuncts in the total number of variables and constraints. Membership in such a union then requires an additional existential quantifier to select the correct disjunct before verifying the linear inequalities and objective threshold; this would place the problem in Σ^p_k rather than Σ^p_{k-1}. The manuscript must explicitly bound the number of sets (or provide a succinct encoding such as a polynomial-size circuit or implicit choice variable) and show that the reduction to a known Σ^p_{k-1}-complete language stays within the claimed class.

    Authors: We agree that the number of disjuncts arising from enumerating active sets or bases across the lower levels is exponential in the input size. However, each disjunct is indexed by a choice of which constraints are active (or which basis is selected) at each lower level. Since the total number of constraints and variables is polynomial in the input size, such a choice can be encoded by a bit vector (or similar succinct descriptor) whose length is polynomial in the input size. Consequently, the selection of the disjunct is realized by a polynomial-size witness that is absorbed into the leading existential quantifier of the Σ^p_{k-1} definition; no additional alternation is introduced. The verification that a given witness satisfies the corresponding weak/strict inequalities, together with the objective threshold, remains a polynomial-time predicate once the lower-level optimality conditions encoded by the active sets are checked. We will revise the manuscript to state this encoding explicitly, bound the witness length, and confirm that the overall quantifier prefix therefore stays within Σ^p_{k-1}. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit representation yields independent upper bound

full rationale

The paper cites Jeroslow for Σ^p_{k-1}-hardness and claims membership via an explicit construction expressing the k-level feasible region as a union of sets defined by weak and strict linear inequalities. This construction is derived directly from the multilevel LP definition and permits a reduction to a known Σ^p_{k-1} decision problem without self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The argument is self-contained against external complexity benchmarks; the number of disjuncts is not shown to introduce an extra quantifier in the provided text.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies only on standard facts about linear programming feasibility and the definition of the polynomial hierarchy; no new parameters, axioms, or entities are introduced.

axioms (1)
  • standard math Standard properties of linear programming feasibility and the polynomial hierarchy
    The reduction uses known oracle characterizations of Σ^p_k and the fact that LP feasibility is in P.

pith-pipeline@v0.9.0 · 5442 in / 1248 out tokens · 36079 ms · 2026-05-08T15:52:01.412352+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 16 canonical work pages

  1. [1]

    Links between linear bilevel and mixed 0–1 programming problems

    C. Audet, P. Hansen, B. Jaumard, and G. Savard. “Links between linear bilevel and mixed 0–1 programming problems.” In:Journal of optimization theory and applications93.2 (1997), pp. 273–300

    1997

  2. [2]

    Geometric and algorithmic developments for a hierarchical plan- ning problem

    J. F. Bard. “Geometric and algorithmic developments for a hierarchical plan- ning problem.” In:European Journal of Operational Research19.3 (1985), pp. 372–383.doi:10.1016/0377-2217(85)90133-X

    work page doi:10.1016/0377-2217(85)90133-x 1985

  3. [3]

    Mixed-integer bilevel rep- resentability

    A. Basu, C. T. Ryan, and S. Sankaranarayanan. “Mixed-integer bilevel rep- resentability.” In:Mathematical programming185.1-2 (2021), pp. 163–197

    2021

  4. [4]

    Computational difficulties of bilevel linear programming

    O. Ben-Ayed and C. E. Blair. “Computational difficulties of bilevel linear programming.” In:Operations Research38.3 (1990), pp. 556–560.doi:10. 1287/opre.38.3.556

    1990

  5. [5]

    On the structure and properties of a linear multilevel programming problem

    H. P. Benson. “On the structure and properties of a linear multilevel pro- gramming problem.” In:Journal of Optimization Theory and Applications 60.3 (1989), pp. 353–373.doi:10.1007/BF00940342

    work page doi:10.1007/bf00940342 1989

  6. [6]

    Bertsimas and J

    D. Bertsimas and J. N. Tsitsiklis.Introduction to linear optimization. Vol. 6. Athena scientific Belmont, MA, 1997

    1997

  7. [7]

    The computational complexity of multi-level linear programs

    C. Blair. “The computational complexity of multi-level linear programs.” In: Annals of Operations Research34 (1992).doi:10.1007/BF02098170

    work page doi:10.1007/bf02098170 1992

  8. [8]

    Mathematical programs with optimization problems in the constraints

    J. Bracken and J. T. McGill. “Mathematical programs with optimization problems in the constraints.” In:Operations research21.1 (1973), pp. 37– 44.doi:10.1287/opre.21.1.37

    work page doi:10.1287/opre.21.1.37 1973

  9. [9]

    Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations

    C.Buchheim.“BilevellinearoptimizationbelongstoNPandadmitspolynomial- size KKT-based reformulations.” In:Operations Research Letters51.6 (2023), pp. 618–622.doi:https://doi.org/10.1016/j.orl.2023.10.006

    work page doi:10.1016/j.orl.2023.10.006 2023

  10. [10]

    Candler and R

    W. Candler and R. Norton.Multi-level programming and development policy. Working Paper. Washington, DC: World Bank, 1977

    1977

  11. [11]

    Integer pro- gramming games

    M. Carvalho, G. Dragotto, A. Lodi, S. Sankaranarayanan, et al. “Integer pro- gramming games.” In:Foundations and Trends®in Optimization7.4 (2025), pp. 264–391.doi:10.1561/2400000040

    work page doi:10.1561/2400000040 2025

  12. [12]

    Efficient distribution of resources through three levels of government

    R. Cassidy, M. Kirby, and W. Raike. “Efficient distribution of resources through three levels of government.” In:Management Science17.8 (1971), B–462.doi:10.1287/mnsc.17.8.B462

    work page doi:10.1287/mnsc.17.8.b462 1971

  13. [13]

    Conforti, G

    M. Conforti, G. Cornuéjols, and G. Zambelli.Integer Programming. Springer, 2014. 16 REFERENCES

    2014

  14. [14]

    Yijiang River Dong, Hongzhou Lin, Mikhail Belkin, Ramon Huerta, and Ivan Vulic

    S. Dempe and A. Zemkoho.Bilevel Optimization: Advances and Next Chal- lenges.1stEdition2020.Vol.161.SpringerOptimizationandItsApplications. Cham: Springer Nature, 2020.doi:10.1007/978-3-030-52119-6

    work page doi:10.1007/978-3-030-52119-6 2020

  15. [15]

    Hansen, B

    P. Hansen, B. Jaumard, and G. Savard. “New branch-and-bound rules for linear bilevel programming.” In:SIAM Journal on scientific and Statistical Computing13.5 (1992), pp. 1194–1217.doi:10.1137/0913069

    work page doi:10.1137/0913069 1992

  16. [16]

    The Polynomial Hierarchy and a Simple Model for Compet- itive Analysis

    R. G. Jeroslow. “The Polynomial Hierarchy and a Simple Model for Compet- itive Analysis.” In:Mathematical Programming32.2 (1985), pp. 146–164

    1985

  17. [17]

    Trilevel modeling of cyber attacks on transmission lines

    X. Liu and Z. Li. “Trilevel modeling of cyber attacks on transmission lines.” In:IEEE Transactions on Smart Grid8.2 (2015), pp. 720–729.doi:10.1109/ TSG.2015.2475701

    work page arXiv 2015

  18. [18]

    Weak via strong Stackelberg problem: new re- sults

    P. Loridan and J. Morgan. “Weak via strong Stackelberg problem: new re- sults.” In:Journal of Global Optimization8.3 (1996), pp. 263–287

    1996

  19. [19]

    Migdalas, P

    A. Migdalas, P. M. Pardalos, and P. Värbrand.Multilevel optimization: algo- rithms and applications. Vol. 20. Springer Science & Business Media, 2013. doi:10.1007/978-1-4613-0307-7

    work page doi:10.1007/978-1-4613-0307-7 2013

  20. [20]

    Complexity of the multilevel critical node problem

    A. Nabli, M. Carvalho, and P. Hosteins. “Complexity of the multilevel critical node problem.” In:Journal of Computer and System Sciences127 (2022), pp. 122–145.doi:10.1016/j.jcss.2022.02.004

    work page doi:10.1016/j.jcss.2022.02.004 2022

  21. [21]

    Non-Cooperative Games

    J. Nash. “Non-Cooperative Games.” In:Annals of Mathematics54.2 (1951), pp. 286–295

    1951

  22. [22]

    On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

    O. A. Prokopyev and T. K. Ralphs. “On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization.” In:Operations Research 0.0 (2026).doi:10.1287/opre.2024.1411

    work page doi:10.1287/opre.2024.1411 2026

  23. [23]

    Unboundedness in Bilevel Optimization

    B. Rodrigues, M. Carvalho, M. F. Anjos, and N. Sugishita. “Unboundedness in Bilevel Optimization.” In:Optimization Online(2024)

    2024

  24. [24]

    Schrijver.Theory of Linear and Integer Programming

    A. Schrijver.Theory of Linear and Integer Programming. Wiley-Interscience series in discrete mathematics and optimization. Chichester: Wiley, 1998

    1998

  25. [25]

    Sugishita and M

    N. Sugishita and M. Carvalho.Complexity of Bilevel Linear Programming with a Single Upper-Level Variable. 2025. arXiv:2510.21126 [math.OC]

    work page arXiv 2025

  26. [26]

    A. B. Tomasaz, M. Carvalho, R. Cordone, and P. Hosteins.On the complete- ness of several fortification-interdiction games in the Polynomial Hierarchy

  27. [27]

    arXiv:2406.01756 [cs.CC]

    work page arXiv

  28. [28]

    Descent Approaches for Quadratic Bilevel Programming

    L. Vicente, G. Savard, and J. Judice. “Descent Approaches for Quadratic Bilevel Programming.” eng. In:Journal of Optimization Theory and Applica- tions81.2 (1994), pp. 379–399

    1994

  29. [29]

    Bilevel and multilevel programming: A bibliography review

    L. N. Vicente and P. H. Calamai. “Bilevel and multilevel programming: A bibliography review.” In:Journal of Global optimization5.3 (1994), pp. 291– 306.doi:10.1007/BF01096458

    work page doi:10.1007/bf01096458 1994

  30. [30]

    Approaches to sensitivity analysis in linear programming

    J. E. Ward and R. E. Wendell. “Approaches to sensitivity analysis in linear programming.” In:Annals of Operations Research27.1 (1990), pp. 3–38

    1990

  31. [31]

    Complete sets and the polynomial-time hierarchy

    C. Wrathall. “Complete sets and the polynomial-time hierarchy.” In:Theo- retical Computer Science3.1 (1976), pp. 23–33. REFERENCES 17 Online Supplement AppendixA.Challenges to extend Buchheim’s Argument to Higher-Level LPs Inrecentwork[9], Buchheimdemonstratedtheinclusionofthedecisionversionof bilevelLPinNP. Healsobrieflydiscussedthathisargumentmightbeext...

    1976