The complexity landscape of robust (integer) linear programming

Dorothee Henke; Jannis Kurtz; Marc Goerigk; Michael Poss

REVIEW

The complexity landscape of robust (integer) linear programming

Michael Poss, Jannis Kurtz, Marc Goerigk, Dorothee Henke

Optimization and Control · Submitted 21 Aug 2026

Pith's verdict: Useful classification paper held back by a fixed-K overclaim in Theorem 21; otherwise solid and worth reviewing.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 27, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2608.21574 (version 2)

Pith IDMSHSLLF2, Pith's permanent record of this paper and its review

CitationDorothee Henke, Jannis Kurtz, Marc Goerigk, Michael Poss. "The complexity landscape of robust (integer) linear programming." arXiv:2608.21574 (2026). https://pith.science/paper/MSHSLLF2

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Here's my take on 2608.21574. It's a serious and useful paper: the first unified complexity map for robust static, two-stage, and K-adaptability problems under continuous/discrete, bounded/unbounded, and decision-dependent uncertainty. The tables alone will become a standard reference. The strongest work is structural: the small-certificate machinery, the Sigma2^p-completeness for Bounded-Static(Xc,Ud(x)), the new Two-Stage memberships, and especially the K-adaptability reductions (monotonicity in K, reduction to two-stage, and the reverse reduction to static for fully discrete decision-dependent instances). The alternative NP proof for bilevel LP is a nice bonus.

The main problem is Theorem 21. The statement says Bounded-K-Adaptability(Xd,Uc,Y) is in NP without qualification, and Table 3 uses it for the Xd/Uc NP-complete rows. The proof enumerates all mappings phi:[K]->[m_y] and explicitly says 'Since K is fixed', but the paper's standing definition of K allows any function of the input, including polynomial K. For K(n)=n and m_y=2, the enumeration is exponential, so the proof does not deliver NP membership. This is a real overclaim as written. The fix is straightforward: either restrict Theorem 21 (and the table entries) to fixed K, or give a different argument for polynomial K. The rest of the K-adaptability machinery (Theorems 18-19, Lemma 6) is not affected.

One smaller point: the reader flagged Theorem 20's claim that the set S has a 'polynomial-size description'. I think that is actually not a problem, because Fact 1 only needs each inequality to have polynomial encoding length, which it does; the number of constraints can be exponential. But the proof is terse there, and in the Xc/Yc case the projection argument could use one more sentence to justify the facet complexity. Worth asking for a clarification, not a correction.

Overall: the framework is sound, the citation practice is honest, and the open questions are clearly flagged. With the Theorem 21 qualification fixed, I'd be comfortable citing this as the standard reference for this classification. It deserves serious peer review.

Referee report

Significance

If the classification is correct, this is a valuable reference map for a large family of robust optimization problems, and the membership proofs go beyond the usual hardness reductions by addressing the non-obvious issue of small certificates in sets with exponentially large or unbounded elements. The reduction from K-adaptability to static robustness for fully discrete decision-dependent instances, and the alternative NP-membership proof for bilevel linear programming, are notable contributions. The paper is generally careful with duality and Farkas arguments and is honest about its open questions. However, the K-adaptability membership statements need qualification: at least one central NP-membership claim is not supported by the proof as written, and some Sigma_2^p claims also require an explicit polynomial bound on K.

Major objections (3)

[Section 5, Theorem 21; Table 3 (Xd/Uc rows)] Theorem 21 states that Bounded-K-Adaptability(Xd,Uc,Y) is in NP for Y in {Yc,Yd} without any fixed-K hypothesis, but the proof verifies a certificate (xhat,yhat^1,...,yhat^K) by enumerating all m_y^K mappings phi:[K]->[m_y] and explicitly says "Since K is fixed the number of possible mappings is polynomial." In the notation of Section 1, K is a function of the input that is not part of the input, and Theorems 1, 2, 18, and 19 repeatedly use "K polynomial in the input." For K(n)=n and m_y=2, the enumeration is exponential, so the proof does not establish NP membership for polynomial K. The theorem and the NP-complete entries in Table 3 for the Xd/Uc rows must either be restricted to fixed K, or a genuinely polynomial-time verification argument for polynomial K must be provided. The K-adaptability-to-static reduction for fully discrete decision-dependent instances (Lemma 6 and Theorem 19) is not affected by this issue.
[Section 5, Theorem 20; Table 3 (Ud and Ud(x) rows)] Theorem 20 claims Sigma_2^p membership without any explicit bound on K. Its proof uses (xhat,yhat^1,...,yhat^K) as a single outer certificate; if K is an exponential function of the input size, this certificate has exponential size and cannot witness membership in Sigma_2^p. Since Section 1 explicitly permits K to be any function of the input, Theorem 20 should be stated with the hypothesis "If K is polynomial in the input" (or another appropriate bound), and the corresponding Sigma_2^p entries in Table 3 should be read under the same qualification. Without such a qualification, the proof is valid only for polynomially bounded K, which is not what the theorem statement says.
[Section 5, proof of Theorem 20] In the proof of Theorem 20, the set S is defined using constraints indexed by every u in U_d, which may be an exponentially large set, yet the proof moves from "S is described by a finite set of constraints of polynomial encoding length" to the existence of a polynomial-size point in S. The number of constraints is not polynomial, so the appeal to Fact 1 and the associated small-certificate conclusion should be justified explicitly, for instance by noting that any vertex of a bounded polyhedron with polynomial-size coefficients has polynomial encoding length even if the number of constraints is exponential. As written, this step is too terse for a load-bearing membership proof.

Minor objections (4)

[Keywords and Conclusion] There are several typos: "polynomial hiearchy" in the keywords should be "polynomial hierarchy," and the Conclusion repeatedly writes "continous" for "continuous."
[Section 1, first paragraph] The phrase "u in the Luncertain constraints" appears to be missing a space; it should read "u in the L uncertain constraints" or similar.
[Section 5, Lemma 5 proof] The notation "Bounded-Finite-AdaptabilityK(X,U,Y)" is awkward; consider writing "Bounded-Finite-Adaptability(X,U,Y) with parameter K" or similar.
[Section 5, Theorem 21 proof] The proof assumes that U_c is nonempty and bounded. The empty-uncertainty case, where the universal quantifier is vacuous and every first-stage solution is feasible, should be dispatched separately or excluded explicitly.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Robust optimization's decision problems range from P to undecidable, and for fully discrete decision-dependent uncertainty, K-adaptability reduces to static robust optimization.

The reading

This paper sets out to map the computational complexity of the decision versions of three classic robust-optimization problems—static, two-stage, and $K$-adaptability—across a grid of modeling choices: continuous or integer variables, decision-independent or decision-dependent uncertainty, and bounded or unbounded feasible regions. The authors claim a systematic classification: most combinations land in $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{coNP}$, or the second and third levels of the polynomial hierarchy, while decision-dependent uncertainty with quadratic constraints pushes continuous variants into the existential theory of the reals and unbounded discrete variants into the undecidable. A by-product is an alternative proof that bilevel linear programming belongs to $\mathsf{NP}$, via a reduction to static robust optimization with decision-dependent right-hand sides. For $K$-adaptability, the paper proves that hardness grows monotonically with $K$ and that, in the fully discrete decision-dependent regime, $K$-adaptability reduces back to static robust optimization, making the two equivalent in hardness. A sympathetic reading takes these results as a near-complete complexity atlas for the core robust linear and integer programming models.

What carries the argument

The load-bearing machinery is a pair of small-certificate facts from mixed-integer programming: any nonempty mixed-integer polyhedron with facet complexity $\varphi$ contains a vector of encoding length polynomial in $\varphi$, and the vertices and rays of its integer hull have polynomial encoding length. The proof pattern is then uniform: reformulate universal quantification over an infinite uncertainty set by duality or by extreme-point and ray decomposition, and certify each quantifier block with a polynomially sized witness. For decision-dependent uncertainty, Lemma 1 lets the authors replace a certificate $x^*$ by another point $\hat{x}$ of polynomial encoding length that induces the same uncertainty set $U_d(x^*) = U_d(\hat{x})$. For $K$-adaptability, the key reductions encode integrality of $T(u)x + Wy$ into indicator variables and big-$M$ constraints, which is what makes a $(K+1)$-th policy discardable and yields the reduction from $K$-adaptability back to static in the fully discrete decision-dependent case.

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the complexity of robust linear and integer programming is governed by a small set of structural switches: continuity versus integrality of first-stage, uncertainty, and recourse sets; decision-dependence of the uncertainty region; and boundedness. The paper proves that each combination can be placed, often exactly, in a complexity class: static robust optimization with continuous uncertainty is in $\mathsf{P}$ or $\mathsf{NP}$-complete, with discrete uncertainty $\mathsf{coNP}$-complete or $\Sigma_2^p$-complete, with continuous decision-dependent uncertainty $\exists\mathbb{R}$-complete or $\Sigma_2^p$-complete, and with unbounded discrete decision-dependent uncertainty undecidable. Two-stage problems sit one or two levels higher, especially with discrete recourse ($\Sigma_3^p$-hard), and $K$-adaptability interpolates between static and two-stage. The most notable claimed result is that when all variables are discrete and the uncertainty set is decision-dependent and bounded, Bounded-$K$-Adaptability reduces to Bounded-1-Adaptability, i.e., to static robust optimization, so choosing among $K$ policies does not make the problem harder there. Along the way, the paper gives polynomial-size certificates for membership in the higher complexity classes despite sets that generally contain vectors of exponential encoding length.

Load-bearing premise

The membership proofs assume that the mixed-integer sets constructed in the reductions—especially sets defined by constraints over the full scenario set, which may contain exponentially many scenarios—always admit polynomial-size descriptions with polynomial facet complexity; if that compression can fail, the $\Sigma_2^p$ membership results for $K$-adaptability with decision-dependent discrete uncertainty do not follow.

Editorial extensions

If this is right

For bounded continuous decision-dependent uncertainty, static robust optimization is $\exists\mathbb{R}$-complete, so no reduction to ordinary mixed-integer linear programming can solve it unless $\mathsf{NP} = \exists\mathbb{R}$.
For unbounded discrete decision-dependent uncertainty, the decision versions are undecidable, so no finite algorithm can answer them in general.
For polynomial $K$, increasing $K$ never makes the $K$-adaptability decision problem easier, and in the fully discrete decision-dependent regime the problem is exactly as hard as static robust optimization.
Bilevel linear programming is in $\mathsf{NP}$, with a polynomial-size certificate obtained through the decision-dependent robust reformulation.
In the discrete-recourse cases, the chain Static $\le$ $K$-Adaptability $\le$ Two-Stage $\le$ Finite-Adaptability holds, so hardness increases monotonically along this modeling ladder.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the classification is correct, the practical boundary for algorithm design is the one between bounded and unbounded decision-dependent discrete models: the former are decidable but high in the polynomial hierarchy, while the latter are undecidable.
The equivalence between static and $K$-adaptability in the fully discrete decision-dependent regime suggests that approximation analyses for $K$-adaptability there can be reduced to static robust optimization, an extension the paper does not spell out.
The same small-certificate pattern could carry over to other quantified mixed-integer problems, such as quantified integer programming with three or more alternations, potentially yielding membership results where only hardness is currently known.
A natural testable extension is to move from feasibility to optimization: because the reductions preserve objective thresholds through epigraph encodings, the full complexity map should survive, though the paper does not prove this.

Original abstract

We study the computational complexity of the decision versions of three classic classes of robust optimization problems: static robust optimization, two-stage (adjustable) robust optimization, and $K$-adaptability. We consider that the feasibility sets, the uncertainty sets, and the recourse sets are polyhedra or integer-programming-representable sets, the uncertainty is decision-independent or decision-dependent, and the feasible regions are bounded or unbounded. While these problems are well-established in the current literature, we give a systematic classification that places them in the complexity classes $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{coNP}$, and higher levels of the polynomial hierarchy ($\Sigma_2^p$ and $\Sigma_3^p$), and, once decision-dependent uncertainty introduces quadratic constraints, in the existential theory of the reals and its hierarchy ($\exists\mathbb{R}$, $\Sigma_2\mathbb{R}$, and $\Sigma_3\mathbb{R}$) or among the undecidable problems. Beyond hardness reductions, we pay particular attention to membership proofs, establishing polynomial-size certificates even though the sets considered generally contain vectors of exponential encoding length. As a by-product, we give an alternative proof that bilevel linear optimization lies in $\mathsf{NP}$, exploiting its connection to decision-dependent robust optimization. For $K$-adaptability, we relate the problem to its static and two-stage counterparts, showing that hardness grows monotonically with $K$ and that, for fully discrete decision-dependent instances, $K$-adaptability reduces back to the static problem.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,277 input tokens.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.15 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.22 · compares with prior results 0.43 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We study the computational complexity of the decision versions of three classic robust optimization problems: static robust optimization, two-stage (adjustable) robust optimization, and $K$-adaptability. We consider that the feasibility, uncertainty, and recourse sets are polyhedra or integer-programming-representable sets, the uncertainty is decision-independent or decision-dependent, and the feasible regions are bounded or unbounded. While these problems are well-established in the current literature, we give a systematic classification that places the resulting problems in $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{coNP}$, and higher levels of the polynomial hierarchy ($\Sigma_2^p$ and $\Sigma_3^p$), and, once decision-dependent uncertainty introduces quadratic constraints, in the existential theory of the reals and its hierarchy ($\exists\mathbb{R}$, $\Sigma_2\mathbb{R}$, and $\Sigma_3\mathbb{R}$) or among the undecidable problems. Beyond hardness reductions, we pay particular attention to membership proofs, establishing polynomial-size certificates even though the sets considered generally contain vectors of exponential encoding length. As a by-product, we give an alternative proof that bilevel linear optimization lies in $\mathsf{NP}$, exploiting its connection to decision-dependent robust optimization. For $K$-adaptability, we relate the problem to its static and two-stage counterparts, showing that hardness grows monotonically with $K$ and that, for fully discrete decision-dependent instances, $K$-adaptability reduces back to the static problem.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We study the computational complexity of the decision versions of three classic robust optimization problems: static robust optimization, two-stage (adjustable) robust optimization, and $K$-adaptability.	contribution 0.83	0.87	0.06	asserted 0.92
s1	We consider that the feasibility, uncertainty, and recourse sets are polyhedra or integer-programming-representable sets, the uncertainty is decision-independent or decision-dependent, and the feasible regions are bounded or unbounded.	method 0.45	0.41	0.02	asserted 0.90
s2	While these problems are well-established in the current literature, we give a systematic classification that places the resulting problems in $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{coNP}$, and higher levels of the polynomial hierarchy ($\Sigma_2^p$ and $\Sigma_3^p$), and, once decision-dependent uncertainty introduces quadratic constraints, in the existential theory of the reals and its hierarchy ($\exists\mathbb{R}$, $\Sigma_2\mathbb{R}$, and $\Sigma_3\mathbb{R}$) or among the undecidable problems.	contribution 0.56	0.90	0.71	asserted 1.00
s3	Beyond hardness reductions, we pay particular attention to membership proofs, establishing polynomial-size certificates even though the sets considered generally contain vectors of exponential encoding length.	contribution 0.74	0.94	0.06	asserted 1.00
s4	As a by-product, we give an alternative proof that bilevel linear optimization lies in $\mathsf{NP}$, exploiting its connection to decision-dependent robust optimization.	result 0.87	0.94	0.06	asserted 1.00
s5	For $K$-adaptability, we relate the problem to its static and two-stage counterparts, showing that hardness grows monotonically with $K$ and that, for fully discrete decision-dependent instances, $K$-adaptability reduces back to the static problem.	result 0.96	0.93	0.12	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Venn diagram illustrating the results from Tables 1 and 2.

Figures reproduced from arXiv:2608.21574 by the authors.

References

How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

What it cites · 2 sentences without a confident label

Cites as background 1 paper

More generally, the existential theory of the reals extends to a hierarchy with alternating quantifiers over real variables, analogous to the polynomial hierarchy [ref] .

The Existential Theory of the Reals as a Complexity Class: A Compendium · Preliminaries · 0.91

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.