Price of Coupling in Multilevel Linear Programming
Multilevel programming is the standard framework for modeling hierarchical decision-making. 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$-level LP is $Σ^{p}_{k-1}$-complete for $k \ge 2$. Without linking…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.25100
curl -X POST /api/v1/records/arxiv/2605.25100/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.25100/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'