Price of Coupling in Multilevel Linear Programming

Nagisa Sugishita, Margarida Carvalho · 2026

Read Price of Coupling in Multilevel Linear Programming by Nagisa Sugishita, Margarida Carvalho (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25100.txt.

Introduction

Nagisa Sugishita and Margarida Carvalho map how hard multilevel linear programming becomes as its structure changes. Deciding whether a feasible solution exists for a k-level problem is complete for a high complexity class, and the same holds for computing optimal values. Removing linking constraints between levels helps only up to a point. With unbounded variables the problem turns easy for few levels but hard again beyond them, so a linked bilevel problem cannot generally be rewritten link-free.

Catalog record

CREATORNagisa Sugishita, Margarida Carvalho
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88533
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.25100

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Price of Coupling in Multilevel Linear Programming Nagisa Sugishita, Margarida Carvalho Abstract Multilevel programming is the standard mathematical framework for modeling hierarchical decision-making, yet a comprehensive understanding of its computational complexity remains fragmented. In this paper, we characterize the computational complexity of deciding the existence of feasible and optimal solutions, as well as computing the optimal objective value in multilevel linear programming (LP). Our analysis considers various combinations of modeling assumptions, including the presence or absence of linking (coupling) constraints and whether all variables are bounded. In particular, we show the feasibility problem of k k -level LP for k ≥ 2 k\geq 2 is Σ k − 1 p \Sigma^{p}_{k-1} -complete in general. When linking constraints and unbounded variables are absent, feasibility is polynomial-time solvable for k ≤ 4 k\leq 4 but becomes Σ k − 1 p \Sigma^{p}_{k-1} -complete for k ≥ 5 k\geq 5 , indicating a sharp jump in computational complexity between four and five levels assuming the polynomial hierarchy does not collapse. Combined with other results, one major implication is that no polynomial-time Turing machine can transform a bilevel LP instance with linking constraints into one without linking constraints while preserving feasibility unless P = NP \textup{P}{}=\textup{NP}{} . In contrast, such machines exist for all k ≥ 5 k\geq 5 . We observe similar phenomena with the computational complexity of deciding the existence of an optimal solution in multilevel LP. In the bilevel case, feasibility and boundedness fully characterize the existence of an optimal solution, implying that the problem is DP-complete. However, these conditions are insufficient for k ≥ 3 k\geq 3 . We show that the problem for k ≥ 3 k\geq 3 is Δ k p \Delta^{p}_{k} -complete. Similar to the feasibility problem, the decision of the existence of an optimal solution becomes polynomially solvable for k = 2 , 3 k=2,3 without linking constraints and unbounded variables. However, the problem is Δ k p \Delta^{p}_{k} -complete for k ≥ 4 k\geq 4 , even with these simplifying assumptions. Interestingly, the computation of the optimal objective value is F ​ Δ k p \textup{F}\Delta^{p}_{k} -complete for any k ≥ 2 k\geq 2 , even without linking constraints and unbounded variables. We also discuss the extension of our results to the mixed-binary cases. 1 Introduction A multilevel programming problem is one in which some decision variables are constrained to belong to the optimal solution set of another problem. Following the work of Bracken and McGill [ 6 ] and Candler and Norton [ 7 ] , research activity in this area has expanded considerably. In particular, methodological progress in bilevel programming has produced a substantial literature addressing both theoretical questions and computational techniques; see Beck et al. [ 5 ] , Carvalho et al. [ 8 ] , and Dempe and Zemkoho [ 11 ] for recent overviews. Interest in trilevel programming has also grown, motivated by its expressive modeling power. Notable applications include the critical node problem [ 19 ] , resource allocation models [ 9 ] , fortification–interdiction settings [ 25 ] , and cyber-security planning [ 17 ] . Further examples of multilevel applications are surveyed in [ 18 , 27 ] . In this work, we focus on multilevel linear programming (LP). Moreover, we concentrate on the optimistic variant of multilevel models, where, if a lower-level problem possesses multiple optimal solutions, the one that is most advantageous for the (immediately preceding) upper-level decision maker is assumed to be chosen. In multilevel LP, a constraint is referred to as a linking (coupling) constraint if it involves variables from the followers. The presence of linking constraints makes multilevel LP more complicated at first glance. For example, the feasible set of a bilevel LP is connected when there are no linking constraints, but this property does not hold when linking constraints appear in the leader’s problem [ 2 , 10 ] . Indeed, one can model any mixed-binary LP as a bilevel LP with linking constraints [ 3 ] . However, from the perspective of computational complexity, many results hold regardless of the presence of linking constraints. For example, Jeroslow [ 14 ] showed that the decision version of k -level LP is \Sigma^{p}_{k-1} -hard, and this remains true even when the instance is restricted to have no linking constraints. Recently, Sugishita and Carvalho [ 24 ] established its membership in \Sigma^{p}_{k-1} , implying that the decision version of k -level LP is \Sigma^{p}_{k-1} -complete with or without linking constraints. Rodrigues et al. [ 21 ] proved \Sigma^{p}_{k-1} -hardness for deciding unboundedness in k -level LP with linking constraints, and later Sugishita and Carvalho [ 24 ] showed that this problem is \Sigma^{p}_{k-1} -complete regardless of the presence of linking constraints. Similarly, it follows from Vicente et al. [ 26 ] that, for a given bilevel LP and a candidate solution, verifying whether it is a local optimum is coNP -hard, with or without linking constraints. We note that all of the above hardness results are based on transformations producing instances with coefficients of polynomial magnitude. Consequently, under standard complexity assumptions, there cannot exist a pseudo-polynomial-time (oracle) Turing machine for the corresponding decision problems. There is also growing interest in developing approaches that transform a bilevel LP instance with linking constraints into one without them. One notable example is the work of Henke et al. [ 13 ] , which discusses an augmented-Lagrangian-based approach for removing linking constraints. Sugishita and Carvalho [ 23 ] presented a polynomial-time procedure that transforms a bilevel LP instance with linking constraints into an equivalent one without them, while preserving the optimal solutions. The correctness of these methods relies on certain assumptions, such as the existence of an optimal solution. In this paper, we analyze the computational complexity of deciding the existence of feasible and optimal solutions in multilevel LP, as well as the computational complexity of computing the optimal objective value, as summarized in Table 1 . These problems are fundamental and of interest per se. For example, the equivalence of the decision version of LP and its feasibility problem plays a key role in the analysis of the polynomial solvability of LP. Our results show that such an equivalence fails for bilevel LP without linking constraints. Furthermore, our results indicate the impacts of linking and unbounded variables on the computational complexity of k -level LP, hence the title of this paper. For instance, deciding the feasibility of a trilevel LP with linking constraints is \Sigma^{p}_{2} -complete. Without linking constraints, the problem becomes coNP -complete. Moreover, if there are neither linking constraints nor unbounded variables, the problem is solvable in polynomial time. We observe that the computational complexity appears to increase with the number of levels k in multilevel LP. A somewhat surprising result is that, without linking constraints and unbounded variables, feasibility can be decided in polynomial time for k\leq 4 , but becomes \Sigma^{p}_{k-1} -complete for k\geq 5 . Thus, there is a sharp increase in computational complexity when moving from 4-level to 5-level LPs, assuming the polynomial hierarchy does not collapse. With linking constraints, the problem is \Sigma^{p}_{k-1} -complete for any k\geq 2 . An interesting implication of the complexity results for feasibility decisions

Read the complete text