{"id":"c041055e-6d04-44d2-9ca0-a669b85bf745","arxiv_id":"1908.01792","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SNAC generates a minimum-cardinality set of non-anticipativity constraints for multistage stochastic programs with gradual uncertainty realization and incomplete scenario sets.","lead":"This paper introduces SNAC, an algorithm that builds a minimum-cardinality set of non-anticipativity constraints for multistage stochastic programs where uncertainty is revealed gradually and the scenario list is incomplete. It could make large stochastic optimization models with decision-dependent uncertainty cheaper to formulate and solve.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's optimality proof establishes only inclusion-minimality, not minimum cardinality; the claim that spanning-tree choices do not affect future edge counts is unproven and fails to account for non-nested equal-cardinality cuts.","rationale":"The paper proposes a useful graph-based method for reducing NACs in MSSPs with gradual uncertainty and incomplete scenario sets, and the computational results show substantial reductions relative to the full formulation. However, the central theorem is the minimum-cardinality guarantee, and that is where the argument is weakest. Lemma 2 correctly characterizes feasibility as connectivity of every cut block, and Algorithm 1 is a natural greedy way to enforce this, but the proof that every added edge is necessary only shows that the output is inclusion-minimal; it does not show that no other feasible edge set is smaller. The additional claim that a spanning-tree choice at one cut does not change future edge counts is load-bearing and unproved. The paper's own C contains incomparable cuts of equal cardinality, so the nested-chain intuition from Lemma 1 does not apply across cuts of the same cardinality. A sequential implementation can make the output order-dependent, while a parallel implementation as described in Remark 1 ignores same-level interactions that could create redundant edges. The experiments in Section 4 compare SNAC only with the full pairwise formulation, so they do not independently verify minimality. I therefore agree with the reader's conditional verdict: the algorithm may be correct, but Theorem 3 as stated needs either a rigorous exchange or lower-bound proof that handles non-nested equal-cardinality cuts, or a clearly justified tie-breaking rule. A brute-force enumeration of small instances is the most direct way to determine whether this is an actual counterexample or only a proof gap.","tokens_in":16860,"tokens_out":18738,"duration_ms":221952,"concrete_test":"Enumerate all small instances consistent with the paper's gradual-realization model (e.g., two or three products, up to four outcomes per product, |S| ≤ 8, with C equal to all permissible event sets). For each instance, run SNAC under every tie-breaking order for cuts and spanning trees, then compare the output size with a brute-force minimum: enumerate subsets of S×S in increasing size, or solve an ILP with binary edge variables and connectivity constraints for each S^c_j, to find the true minimum number of scenario pairs satisfying Lemma 2. If any instance has |E_SNAC| greater than the true minimum, Theorem 3 is false; if all instances match, the immediate risk is resolved, though an analytic exchange proof would still be needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1, Theorem 3: the central claim is that Algorithm 1 returns a NAC set enforced on the minimum number of scenario pairs, with running time O(|C||S|^3). By Lemma 2, the problem is to choose a minimum edge set E such that for every cut c∈C and every block S^c_j, the induced graph (S,E)[S^c_j] is connected. The proof does not establish this. It argues that each edge added at step 6 is 'necessary' in the sense that removing it disconnects the block for which it was added, treating all other added edges as fixed. That is an inclusion-minimality argument, not a cardinality-minimality argument: an edge set can be inclusion-minimal yet strictly larger than another feasible set, and sharing edges across crossing blocks is exactly what can create such a gap. The sentence 'this choice has no effect on the number of arcs needed to be included at future iterations' is asserted without proof and is not valid for equal-cardinality cuts, which need not be nested; the paper's own manufacturing example has cuts {e^1_{P1}} and {e^1_{P2}} that cross. If step 6 is implemented sequentially, the output can depend on cut order; if it is implemented 'in parallel' as Remark 1 states, edges added for one cut are invisible to another, so the union may contain cycles and an edge can be necessary only relative to previously added edges, not relative to the final set. The numerical study in Section 4 compares SNAC only against the full pairwise NAC formulation, so it does not test optimality. A lower-bound or exchange argument independent of tie-breaking is missing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a graph-based algorithm (SNAC) for generating a set of non-anticipativity constraints (NACs) in multistage stochastic programs with gradual uncertainty realization and incomplete scenario sets. Scenarios are vertices and NACs are edges; Lemma 2 characterizes feasibility of a NAC set as connectivity of every block of every partition induced by each permissible event set. Algorithm 1 iterates from fine to coarse event sets, adding spanning-tree edges to connect each block, and Theorem 3 claims that the output is a minimum-cardinality edge set with running time O(|C||S|^3). The paper illustrates the algorithm on a manufacturing example and reports computational experiments on clinical-trial planning instances, comparing the SNAC-reduced formulation with the full pairwise NAC formulation.","tokens_in":17167,"tokens_out":26581,"duration_ms":246685,"significance":"The paper addresses a relevant and practically motivated problem: reducing the number of non-anticipativity constraints in multistage stochastic programs with gradual uncertainty realization and incomplete scenario sets. Its reformulation of the NAC-enforcement condition as block connectivity (Lemma 2) is a useful observation, and the SNAC algorithm is simple and clearly structured, with a plausible polynomial bound when the number of uncertain parameters is fixed. The computational case study demonstrates that the SNAC-based formulation can substantially reduce model generation and solution times relative to the full pairwise formulation, and the observation that SNAC can be run once for a family of instances sharing a scenario structure is a genuine practical advantage. However, the central theoretical result, the assertion of minimum-cardinality output, is not established and is in fact false for the algorithm as stated. If corrected and properly validated, the idea could serve as a useful heuristic; as it stands, the main contribution of the paper is not supported.","major_comments":[{"comment":"The optimality claim in Theorem 3 is false as stated. Consider S={1,2,3,4,5,6}, C={c1,c2} with |c1|=|c2|=1, Π(c1)={A={1,5,6}, B={2,3,4}}, and Π(c2)={C={1,2,3}, D={4,5,6}}. This instance is realizable in the paper's framework (e.g., the manufacturing example of Section 2.2 with two products and the cuts corresponding to the first completion event for each product). A feasible set must connect A, B, C, and D. The minimum cardinality is 6: the edges (5,6),(1,5),(2,3),(2,4),(1,2),(4,5) achieve this, and no 5-edge set can, because the four 3-vertex blocks require at least 8 block-edge incidences while only the two edges (5,6) and (2,3) can be shared between two blocks, giving at most 7 incidences with 5 edges. If Algorithm 1 processes c1 first and at step 6 chooses the spanning trees (1,5),(1,6) on A and (2,4),(3,4) on B, then c2 has no previously added edges inside C or D, and the algorithm adds (1,2),(2,3),(4,5),(5,6), for a total of 8 edges. If instead c1's trees are (1,5),(5,6) and (2,3),(2,4), then c2 needs only (1,2) and (4,5), for a total of 6 edges. Since Algorithm 1 does not specify how the spanning tree at step 6 is constructed, both outputs are valid executions, and the theorem's 'minimum number of pairs' claim is contradicted. The proof's assertion that the spanning-tree choice 'has no effect on the number of arcs needed to be included at future iterations' is false: the choice at c1 changes the number of edges required at the same-iteration cut c2. More generally, the proof's necessity argument establishes only inclusion-minimality relative to the previously added edges, not minimum cardinality, and it does not account for alternate paths created by edges added later or at the same iteration.","section":"Section 3.1, Theorem 3 and Algorithm 1"},{"comment":"The computational study does not test the optimality claim. Tables 2 and 3 compare the SNAC formulation only with the full pairwise NAC formulation, reporting reductions in the number of scenario pairs and in model generation and CPLEX times. No comparison is made against an exact minimum-cardinality NAC set (e.g., the MILP of Hooshmand and MirHassani (2016) or an exhaustive enumeration on the smallest instances), and no non-trivial lower bound is computed. The observed reductions are consistent with a heuristic that generates a feasible but not necessarily minimum set, so the experiments cannot substitute for a valid proof of Theorem 3.","section":"Section 4, Tables 2 and 3"}],"minor_comments":[{"comment":"The treatment of cuts of the same cardinality is ambiguous: the for-loop in Algorithm 1 updates N after each c, so a later cut at the same level sees edges added for an earlier cut, whereas Remark 1 states that components are treated 'in parallel' without regard to edges added at the same iteration. This distinction matters for correctness, and the manuscript should specify the intended semantics and state the corresponding proof obligations.","section":"Section 3.1, Algorithm 1 and Remark 1"},{"comment":"The formula for the number of pairs in the full formulation is typeset with an extra space as '0 .5[|S|(|S|− 1)]'.","section":"Section 3.2"},{"comment":"There are several typos, including 'suprizing' for 'surprising', 'teh' for 'the', and 'allied' for 'applied' in Remark 2.","section":"Section 4"},{"comment":"The abstract's statement that the algorithm 'scales polynomially in the number of scenarios' should carry the qualifier 'for a fixed number of uncertain parameters and events' that appears later in Section 3.1, since the running time is O(|C||S|^3) and |C| can be exponential in the number of events.","section":"Abstract and Section 3.1"},{"comment":"The displayed definition of the permissible event set C contains a malformed union expression; it should be written as a standard set comprehension.","section":"Section 2.1"}],"recommendation":"reject","confidential_remarks":"The counterexample in my major comment appears to refute Theorem 3 as stated, and the flaw is central to the paper's claimed contribution. A revision that presents SNAC as a heuristic, with appropriate experiments and no optimality theorem, might be viable, but that would be a substantially different paper. I recommend rejection of the current submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper fills a real gap—nobody else, as far as I can tell, has given a NAC-reduction algorithm for multistage stochastic programs with gradual realization and incomplete scenario sets. The graph/connectivity view is clean, and SNAC as a constructive heuristic works: it always returns a feasible NAC set, and the experiments show big reductions against the full pairwise formulation. But the headline claim—minimum cardinality—does not hold up. Theorem 3's proof is an inclusion-minimality argument, not a cardinality-minimality one. 'Necessary' is defined relative to edges added so far; an edge can be non-redundant at the time it is added and still be globally redundant because a crossing cut at the same level provides the same connectivity. The paper's own example has crossing equal-cardinality cuts ({e^1_P1} and {e^1_P2}), so this is not an exotic case. The sentence about spanning-tree choices having no effect on future iterations is asserted, not proved, and looks false in general: with the parallel treatment in Remark 1, different spanning-tree choices can give different total edge counts. You can build four-scenario examples where the algorithm outputs four edges while three suffice. The computational study does not test optimality—it only compares against the full set of pairwise constraints, so it cannot detect the gap.\n\nWhat the paper does well: Lemma 2 is the right formalization; the manufacturing example is actually useful; the empirical savings in constraint count and solve time are believable; and the point that SNAC depends only on scenario structure, so it can be computed once for a family of instances, is a good practical observation. The literature review is fair and does not overclaim novelty—the new part is the gradual/incomplete case.\n\nRecommendation: this deserves serious refereeing, because the problem is real and the algorithm is valuable even without the optimality guarantee. But the paper should not be accepted as is. The authors need to either supply a real proof of minimality (an exchange argument or lower bound independent of tie-breaking) or soften the claim to a heuristic that produces valid NAC sets. I'd send it to a stochastic-programming or combinatorial-optimization reviewer, not desk reject. A revised version that fixes the theorem would be a useful paper; the version now is a useful algorithm with an incorrect proof.","headline":"Useful NAC-reduction algorithm for gradual uncertainty on incomplete scenario sets, but the minimum-cardinality theorem is not proved and the greedy choice can matter.","tokens_in":17703,"tokens_out":11204,"would_cite":true,"duration_ms":115405,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a greedy spanning-tree algorithm produces a minimum-cardinality set of non-anticipativity constraints for multistage stochastic programs with gradual uncertainty and incomplete scenario sets.","keywords":["multistage stochastic programming","non-anticipativity constraints","endogenous uncertainty","gradual uncertainty realization","incomplete scenario sets","graph connectivity","spanning tree","minimum cardinality"],"falsifier":"Take a small incomplete scenario set with two information states having the same number of realized events whose scenario groups are not nested; run SNAC under all tie-breaking orders of these two states and compare the number of scenario pairs in the output. If any order yields strictly more pairs than another, Theorem 3's guarantee of a minimum-cardinality NAC set fails for that instance.","tokens_in":16660,"feed_emoji":"🧩","tokens_out":11794,"duration_ms":105710,"temperature":0.7,"pith_summary":"This paper establishes that the problem of generating a minimum-cardinality set of non-anticipativity constraints (NACs) for a multistage stochastic program can be solved exactly by a greedy spanning-tree algorithm, even when uncertainty is revealed gradually and the scenario set is only a subset of all possible outcomes. In such models, NACs are equality constraints that stop decisions from using information that has not yet been realized; too many of them bloat the model. The paper proves that a set of NACs is sufficient exactly when every group of scenarios that are indistinguishable at some information state is connected in a graph whose edges are scenario pairs. SNAC builds these connections from the finest information partition to the coarsest and proves the result has the smallest possible number of scenario pairs, scaling polynomially in the scenario count when the number of uncertain parameters is fixed. A computational study on pharmaceutical and manufacturing planning instances reports the same optimal objective values with far fewer constraints and lower solver times.","feed_headline":"New graph algorithm finds fewest non-anticipativity constraints","feed_subtitle":"SNAC connects scenario groups so no decision anticipates the future, shrinking models and solver time in tests.","key_machinery":"The central object is the scenario graph $G=(S,E)$ whose vertices are scenarios and whose edges are NAC pairs, together with the family of partitions $\\Pi(c)$ induced by permissible event sets $c\\in C$, called cuts. Lemma 2 converts non-anticipativity into a connectivity condition: a NAC set is sufficient exactly when every block $S^c_j$ is connected in the graph restricted to that block. SNAC works from the finest cuts (largest $|c|$) down to the coarsest, adding a spanning tree within each block where needed; the downward order and the necessity argument in Definition 1 ensure every added edge is necessary, so no edge can be removed without breaking connectivity, hence the set is minimum.","core_discovery":"The central claim is Theorem 3: Algorithm 1 terminates with a subset of edges that corresponds to a set of NACs enforced on the minimum number of pairs of scenarios, with an implementation running in $O(|C||S|^3)$ time as the scenario set $S$ and event-set family $C$ grow. The proof rests on two structural facts. First, for every permissible set of realized events $c\\in C$, the partition $\\Pi(c)$ divides scenarios into groups $S^c_j$ that are still indistinguishable, and a NAC set is sufficient iff each such group is connected in the induced subgraph of $G=(S,E)$ (Lemma 2). Second, because a coarser information state is refined by later states (Lemma 1), any edge needed to connect a group at a coarser state cannot be implied by edges added at finer states; SNAC's downward sweep over $|c|$ therefore adds only necessary edges, and the spanning-tree construction keeps each added edge necessary. The paper generalizes prior minimum-NAC-set results, which required instantaneous uncertainty realization or the full Cartesian-product scenario set, to gradual realizations with arbitrary scenario subsets.","pith_inferences":["Editorial inference: because Lemma 2 reduces NAC sufficiency to a connectivity check, any heuristic that removes NACs can be audited by testing each block's connectivity; the paper does not present this as a standalone verification routine, but it follows directly.","Editorial inference: the same graph and partition construction should apply to any nested family of information states, not only those derived from Cartesian products of independent uncertain parameters; SNAC's correctness depends on Lemma 1's nesting, not on the product structure.","Editorial inference: the minimal scenario-pair set produced by SNAC is a natural set to dualize in Lagrangean or progressive-hedging decompositions, since those methods dualize NACs and benefit from fewer linking constraints; the paper's experiments only use SNAC to build and solve the full model.","Editorial inference: if the equal-cardinality order assumption in Theorem 3 is false for some incomplete scenario set, the algorithm would still output a sufficient NAC set, but not necessarily a minimum one; a counterexample would appear as an order-dependent edge count in a small exhaustive search."],"forward_implications":["A user can compute the minimal NAC pair count once for a given scenario structure and reuse it across instances that differ only in objective coefficients, since SNAC reads only the uncertainty structure, not costs or revenues.","The sufficiency condition in Lemma 2 gives a cheap certificate: to check whether any proposed NAC set is sufficient, verify that every information-state group is connected in the graph; no optimization solve is needed.","For fixed numbers of uncertain parameters and events, the running-time bound $O(|C||S|^3)$ means the method remains practical as the scenario sample grows, which is the typical scaling regime for incomplete scenario sets.","In the reported case studies, SNAC preserved the optimal objective value in all instances while reducing scenario-pair counts sharply; for example, at 1,024 scenarios the full model's 523,776 pairs fell to 3,840, and total solution time dropped by roughly 30 percent for that instance."],"supporting_citations":[{"why":"introduced the graph-based NAC-removal approach and the scenario-pair counting convention that SNAC generalizes to gradual realizations and incomplete scenario sets.","marker":"Hooshmand and MirHassani (2016)"},{"why":"supplies the general MSSP formulation with endogenous and exogenous uncertainty and the prior graph-theoretic extension that SNAC builds on.","marker":"Apap and Grossmann (2017)"},{"why":"establishes the minimum-cardinality NAC-set problem and conditions for omitting NACs, which this paper extends from complete scenario sets to arbitrary subsets.","marker":"Boland et al. (2016)"},{"why":"provides the pharmaceutical and manufacturing planning model with gradual uncertainty via processing-stage completions used as the illustrative and computational testbed.","marker":"Colvin and Maravelias (2008)"},{"why":"defines the class of stochastic programs with decision-dependent uncertainty and the complete-scenario-set setting that the proposed method relaxes.","marker":"Goel and Grossmann (2006)"},{"why":"introduces endogenous uncertainty with decision-dependent random elements, the problem class the paper addresses.","marker":"Jonsbråten et al. (1998)"}],"fun_headline_variants":["Graph algorithm minimizes non-anticipativity constraints in MSSP","SNAC: fewest future-peek constraints via graph connectivity","Graph approach trims constraints for stochastic programs with incomplete scenarios","Minimum NAC set via graph partitions in multistage stochastic programs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the greedy order yields the fewest constraints rests on the claim that, when several information states have the same number of realized events, the choice of order in which they are processed does not change how many connections are needed at coarser states later; for non-nested equal-size states this claim is assumed rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Graph algorithm minimizes non-anticipativity constraints in MSSP","SNAC: fewest future-peek constraints via graph connectivity","Graph approach trims constraints for stochastic programs with incomplete scenarios","Minimum NAC set via graph partitions in multistage stochastic programs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1510,"prompt_tokens":916,"completion_tokens":594,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":524}},"tokens_in":532,"tokens_out":594,"duration_ms":6299,"temperature":1.0,"reasoning_tokens":524,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:04:36.131924+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small incomplete scenario set with two information states having the same number of realized events whose scenario groups are not nested; run SNAC under all tie-breaking orders of these two states and compare the number of scenario pairs in the output. If any order yields strictly more pairs than another, Theorem 3's guarantee of a minimum-cardinality NAC set fails for that instance.","supporting_citations":[{"cited_title":"M., Grossmann, I","cited_arxiv_id":null,"evidence_quote":"supplies the general MSSP formulation with endogenous and exogenous uncertainty and the prior graph-theoretic extension that SNAC builds on."},{"cited_title":"Minimum cardinality non-anticipativity constraint sets for multistage stochastic programming","cited_arxiv_id":null,"evidence_quote":"establishes the minimum-cardinality NAC-set problem and conditions for omitting NACs, which this paper extends from complete scenario sets to arbitrary subsets."},{"cited_title":"T., 2008","cited_arxiv_id":null,"evidence_quote":"provides the pharmaceutical and manufacturing planning model with gradual uncertainty via processing-stage completions used as the illustrative and computational testbed."}],"review_version":1}