{"id":"ebdc4624-c790-4916-ba4a-160f23b0bf84","arxiv_id":"2412.08206","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"Recursively applying large neighborhood search to its own auxiliary MILPs, guided by a graph transformer, finds good solutions faster than one-layer LNS and standard solvers on four large MILP benchmarks.","lead":"The paper stacks large neighborhood search on itself: the search step for a big MILP is replaced by another LNS, so commercial solvers only handle small subproblems. On four public benchmarks, the learning-guided version reports up to 96% faster progress in finding good solutions than a single-layer LNS or Gurobi and SCIP.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"TLNS gains over LNS may be an artifact of unequal neighborhood sizes; no matched-k baseline is reported.","rationale":"The reader centered on the unverified presolve claim in Remark 2. That is an explanatory assumption; even if false, the empirical results might stand. A more damaging threat to the central empirical claim is that the LNS baselines are not comparable: TLNS searches a much larger space (larger k1), while the paper's formal argument (Remark 2) compares against LNS with the union of neighborhoods, a configuration never tested. This confound directly affects the headline 'up to 66% over LNS' and the 'generally outperforms' conclusion. The proposed matched-k experiment would separate the effect of the two-layer recursion from that of a larger neighborhood. The reader's proposed instrumentation (measuring T1p, T2p, and H) is useful but would only test Remark 2, not the empirical claim. Thus the verdict remains CONDITIONAL/UNCHANGED, with an added condition: report a matched-neighborhood LNS baseline.","tokens_in":13689,"tokens_out":12372,"duration_ms":128388,"concrete_test":"Run CL-LNS on the same 10 LARGE test instances per benchmark with the neighborhood size k set to CL-TLNS's outer k1 (SC 500, CA 60,000, MIS 30,000, MVC 5,500), allowing a per-solve time limit equal to the average time CL-TLNS spends in its inner LNS, and compare PI/PB at 1,000 s. If CL-LNS attains PI/PB comparable to CL-TLNS, the two-layer recursion is not the active ingredient; if CL-TLNS remains clearly superior, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim that TLNS 'generally outperforms' LNS is not supported by a controlled comparison. In Table 2, TLNS is assigned outer neighborhood sizes k1 that are far larger than the LNS neighborhood sizes: for example, on SC, CL-LNS uses k=175 while CL-TLNS uses 500/120; on MIS, 12,500 vs 30,000/7,000; on MVC, 1,250 vs 5,500/1,000. Because PI rewards earlier progress from a larger search space, the gains in Table 3 (e.g., 66.1% on MIS) may reflect the larger k1 rather than the two-layer recursion. Remark 2 formally compares TLNS with LNS using the union neighborhoods F1∪F2, but no experiment realizes this baseline; the only LNS variants tested use smaller k. Without a matched-neighborhood LNS (or an ablation fixing k1 and toggling the inner LNS), the observed improvements over LNS cannot be attributed to the two-layer structure.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-layer large neighborhood search (TLNS) for mixed-integer linear programs: the outer LNS creates an auxiliary MILP as usual, but instead of handing it to an exact solver, an inner LNS solves that auxiliary problem, so that only small sub-MILPs are given to off-the-shelf solvers. A simplified graph transformer (SGT) with linear attention is trained by contrastive learning to score variables for neighborhood construction. Experiments on four public benchmark families (set covering, combinatorial auctions, maximum independent set, minimum vertex cover) compare TLNS with single-layer LNS (both random and learned) and with Gurobi/SCIP, reporting primal-integral improvements up to 66% over LNS and up to 96% over the solvers.","tokens_in":13908,"tokens_out":4711,"duration_ms":46767,"significance":"If the reported improvements are robust, the two-layer recursion idea is a useful contribution: it reduces reliance on exact solvers inside LNS and may scale better to very large MILPs. The paper's SGT architecture with linear attention is a sensible way to extend GNN-based policies to large graphs, and the training/inference pipeline is described with enough detail to be reproducible. The paper also ships code and uses public benchmark generators, which supports independent verification. The main value, however, depends on whether the two-layer structure, rather than the larger neighborhoods assigned to TLNS, is responsible for the observed gains; for that reason the current evidence is suggestive but not conclusive.","major_comments":[{"comment":"The claimed superiority of TLNS over LNS is confounded by unequal neighborhood sizes. In Table 2, TLNS is always assigned a larger outer neighborhood (k1) than the single-layer LNS neighborhood (k): e.g., on SC CL-LNS uses k=175 while CL-TLNS uses 500/120; on MIS 12,500 vs 30,000/7,000; on MVC 1,250 vs 5,500/1,000. Since the primal-integral metric rewards earlier progress, the larger k1 alone could explain much of the reported gain. The paper does not include a matched-k baseline (e.g., single-layer LNS with the union neighborhood F1∪F2 as described in Remark 2) nor an ablation that fixes k1 and toggles the inner LNS. Without such a control, the central claim that TLNS generally outperforms LNS is not supported.","section":"§4.2–4.3, Table 2"},{"comment":"The efficiency argument of Remark 2 relies on the assumption that presolving the inner auxiliary problem A(P, y, F2^h) is much cheaper than presolving A(M, x, F1∪F2^h), i.e., T2p << T1p. This is an unverified assumption; the inner LNS may invoke the solver many times, and each invocation incurs its own presolve cost, so the total presolve time could be larger than T1p. The manuscript reports no measurements of T1p, T2p, or the number of inner iterations. Please provide empirical timing data or at least an ablation that reports presolve times and inner-iteration counts to substantiate the claim that the nested scheme saves presolving time.","section":"Remark 2, §3.1"},{"comment":"The primal-bound (PB) improvements are small or negative on two of the four benchmarks. In Table 3, CL-TLNS PB on SC is 113.0 vs 112.7 for CL-LNS (0.2% worse), and on MVC the gain is only 0.07%. The conclusion that TLNS 'generally outperforms' LNS is therefore based primarily on the primal-integral (PI) metric. Since PI is normalized by best-known bounds and integrated over the runtime, a systematic difference in neighborhood sizes can dominate it. The authors should temper the general claim, report PB gaps or performance profiles, and explicitly separate the PI-based results from the PB-based results in the conclusions.","section":"§4.3–4.4, Table 3"}],"minor_comments":[{"comment":"The text 'akaneighborhood size' has a missing space; it should read 'a neighborhood size'.","section":"Definition 1"},{"comment":"The '–' entry for SCIP on MIS is not explained in the text; the discussion should mention that SCIP failed due to memory limits.","section":"Table 4"},{"comment":"The hardware description '12th Gen Intel(R) Core(TM) i9-12900K CPUs with Nvidia GeForce RTX 3090 GPUs' should clarify how many CPUs/GPUs are used per run (e.g., one CPU and one GPU per instance).","section":"§4.1"},{"comment":"The statement that SCIP is used as the underlying solver 'since the presolve operator in Gurobi is inaccessible' is unclear; Gurobi's presolve can be disabled, so the reason for not using Gurobi in LNS should be explained more precisely.","section":"§4.2"},{"comment":"The 'Gain' column sometimes takes negative values (e.g., SC PB -2.7%), which indicates worse performance for TLNS; the sign convention and interpretation should be stated explicitly.","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an interesting and timely problem, and the two-layer LNS idea is novel. The main weakness is the absence of a controlled comparison with equal neighborhoods; this is fixable by adding a matched-k baseline or an ablation that isolates the inner LNS. If the authors can provide such evidence, the paper would be a strong candidate for acceptance. Otherwise, the central claim should be weakened to 'TLNS with the tuned larger neighborhoods improves PI over LNS with smaller neighborhoods,' which would be a less significant contribution. The small test set (10 instances per benchmark) and the many tuned hyperparameters (neighborhood sizes, adaptive rates) also suggest that the empirical claims should be phrased with appropriate caution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about arXiv:2412.08206. First, the core idea is genuinely new: instead of handing each auxiliary MILP in LNS to an exact solver, TLNS runs another LNS on it, so the exact solver only ever sees small sub-MILPs. That is a sensible divide-and-conquer move and I have not seen it before. Second, the headline empirical comparison to LNS is undercut by unequal neighborhood sizes, and the authors never supply the matched-k ablation that would settle the question.\n\nWhat the paper does well: the framing is clear, the two-layer scheme is simple to state, the use of a simplified graph transformer is a reasonable way to get global attention without O(n^2), and the training procedure follows the established contrastive-learning template. The numerical results are large and consistent in the PI metric—66% over CL-LNS on MIS, 96% over Gurobi on SC—and the authors are honest about the cases where PB does not improve (SC is slightly worse). They also include an ablation of the architecture and a comparison to LP-free heuristics. So there is real engineering substance here.\n\nThe soft spots: the central claim that TLNS outperforms LNS is not backed by a controlled comparison. In Table 2, TLNS is given an outer neighborhood size k1 that is much larger than the LNS neighborhood size (e.g., SC: 175 for CL-LNS vs 500/120 for CL-TLNS; MIS: 12,500 vs 30,000/7,000). Since the inner layer then fixes a smaller sub-neighborhood, TLNS is in effect running many small SCIP calls instead of one larger one. The gains in PI could come from that different search budget rather than from the recursive structure. The paper's Remark 2 compares TLNS to LNS on the union of the neighborhoods, but no experiment realizes that baseline. A matched-k LNS (or an ablation fixing k1 and toggling the inner LNS) would be the right control, and it is missing. Also, only 10 test instances per benchmark, no significance tests, no code or data release, and the presolve-time saving argument in Remark 2 is asserted, not measured.\n\nWho this is for: anyone working on ML-guided LNS or primal heuristics for large MILPs. It is a legitimate contribution even if the headline comparison is not sealed. A serious referee should engage with it, and the revision requests should center on the matched-k baseline and code release. My own verdict is conditional, but the paper is worth the referee time.","headline":"TLNS is a genuinely new recursive LNS idea, but its empirical edge over LNS is not cleanly established because the comparison uses unequal neighborhood sizes and no matched-k baseline.","tokens_in":14471,"tokens_out":2877,"would_cite":true,"duration_ms":29358,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"A two-layer scheme that hunts solutions inside its own neighborhoods beats single-layer LNS and top solvers, cutting primal integral by up to 96%.","keywords":["large neighborhood search","mixed-integer linear programming","graph transformer","contrastive learning","presolve","primal heuristic","learning to optimize","combinatorial optimization"],"falsifier":"Measure T1p (presolve time of the outer auxiliary problem), T2p (presolve time of a single inner auxiliary problem), and H (number of inner LNS iterations) on the four benchmark families. If H * T2p is not substantially smaller than (H - 1) * T1p, the Remark 2 time saving does not hold and TLNS could be slower than a single-layer LNS with an equivalent small neighborhood; the reported gains would then be attributable to neighborhood size or hardware, not nesting. A direct test is to run TLNS with the inner LNS replaced by a single exact solve of the same small neighborhood and compare wall-clock time per unit primal-bound improvement.","tokens_in":13422,"feed_emoji":"🧩","tokens_out":8012,"duration_ms":71481,"temperature":0.7,"pith_summary":"In large neighborhood search (LNS) for mixed-integer linear programs (MILPs), the most expensive step is the interior solve: every iteration hands an auxiliary MILP to a general-purpose solver. This paper claims that the auxiliary MILP can be solved by another round of LNS instead of by an exact solver, and that the resulting two-layer scheme (TLNS) is faster overall. The outer layer fixes a large set of variables, presolves the remaining subproblem once, and the inner layer runs a standard LNS on that reduced model, so only small MILPs ever reach the off-the-shelf solver. A contrastively trained graph transformer with linear global attention selects which variables to unfix. On benchmarks with up to 100,000 variables and 5 million constraints, TLNS reports up to 66% better primal integral than single-layer LNS and up to 96.1% better than Gurobi and SCIP, with final primal bounds improved by up to 39.7%.","feed_headline":"Nested search beats Gurobi and SCIP by up to 96%","feed_subtitle":"A two-layer large neighborhood search finds good solutions to huge mixed-integer programs faster than the top solvers.","key_machinery":"The central object is the two-layer fixation-neighborhood scheme. An auxiliary MILP defined by fixing variables (a fixing neighborhood) is itself solved by LNS rather than by an exact solver, and the presolve operator Q is what makes the nesting affordable: it compresses the outer auxiliary problem so that the inner LNS operates on a smaller model and each inner presolve is cheap. The neighborhood-selection policy is a lightweight graph transformer that adds linear global attention on top of two graph-convolutional half-layers, trained with contrastive loss where local branching supplies positive and negative action samples. This policy is shared by both layers, and the same trained model is applied to test instances larger than those used for training.","core_discovery":"The paper's central claim is that replacing the exact solve of an auxiliary MILP with a heuristic LNS pass accelerates the whole search. Formally, TLNS applies LNS at two levels: in the outer layer it fixes a neighborhood F1 around the incumbent, forming an auxiliary problem A(M, x-bar, F1), then presolves that problem once into a reduced model P; the inner layer runs a standard LNS on P, with a count limit that enlarges the inner neighborhood whenever progress stalls; postsolve maps the inner solution back. The paper argues via Remark 1 that the inner heuristic exits the outer neighborhood faster than branch-and-bound, and via Remark 2 that the single outer presolve makes the total presolve time smaller than presolving each of H inner neighborhoods separately, saving (H - 1)T1p - H T2p when the inner presolve time T2p is much smaller than the outer T1p. Empirically, on Set Cover, Combinatorial Auction, Maximum Independent Set, and Minimum Vertex Cover instances, the learning-guided version CL-TLNS is reported to beat the single-layer CL-LNS by 26.5% to 66.1% in primal integral and to beat both Gurobi and SCIP by up to 96.1% in primal integral and 39.7% in final primal bound.","pith_inferences":["The paper's speedup rests on the unmeasured premise that inner presolve is much cheaper than outer presolve; if that premise fails, TLNS's advantage could vanish on other instance classes, so a direct measurement of T1p, T2p, and H on new benchmarks would settle when nesting helps.","Because the graph transformer is trained on small instances (up to 6,000 variables) and applied to much larger ones (up to 100,000), the receptive-field argument suggests the method will degrade least on problems whose structure is scale-invariant, such as the random graphs used here; on highly irregular or tightly coupled instances, the fixed training distribution may limit transfer.","The comparison to state-of-the-art MILP solvers uses a 1,000-second time limit and excludes cases where the solvers can close the gap; on smaller or easier instances where Gurobi or SCIP can prove optimality, the PB/PI gains would likely shrink, and the method's role is best seen as a primal heuristic for hard large instances.","A recursive multi-layer version would forgo exact solves entirely; an immediate test is whether depth three or four continues to improve primal integral, or whether presolve time savings saturate as inner models become tiny."],"forward_implications":["TLNS yields faster primal progress than single-layer LNS for both random and learned neighborhood heuristics on all four benchmarks, with primal-integral gains of 26.2% to 51.3% for the random version and 26.5% to 66.1% for the contrastive-learned version.","CL-TLNS beats both Gurobi and SCIP (with aggressive internal heuristics) on all benchmarks, by up to 96.1% in primal integral and up to 39.7% in primal bound at the 1,000-second time limit.","The simplified graph transformer (SGT) outperforms GCN and GAT in guiding TLNS and avoids GAT's out-of-memory failures on the Set Cover instances.","The number of LNS layers can be increased: GRB(NoRel), CL-LNS(NoRel), and CL-TLNS have 0, 1, and 2 layers, respectively, and performance improves with each added layer.","The method only needs small MILPs for the exact solver, reducing reliance on branch-and-bound for large problems and suggesting multi-layer LNS as a research direction."],"supporting_citations":[{"why":"Supplies the presolve reductions that Remark 2 relies on for the claim that presolving the outer auxiliary problem once makes inner presolves cheap.","marker":"[1]"},{"why":"Defines the local-branching neighborhood used as the expert to generate positive and negative training samples for contrastive learning.","marker":"[5]"},{"why":"Provides the variable-constraint bipartite graph representation used as the policy network's input.","marker":"[7]"},{"why":"Gurobi is the off-the-shelf solver used for initial solutions and the main state-of-the-art baseline in the numerical comparison.","marker":"[8]"},{"why":"SCIP is the underlying solver used inside both LNS and TLNS (because its presolve is accessible) and is another baseline.","marker":"[3]"},{"why":"The contrastive-learning LNS that the CL-LNS baseline builds on; the paper adapts its positive/negative sample construction.","marker":"[12]"},{"why":"The classic random large neighborhood search (R-LNS) that the paper compares against; also a source of the fixing-neighborhood definition.","marker":"[20]"},{"why":"A learning-based LNS using imitation learning; the paper notes its contrastive loss reduces to the cross-entropy used there when only one positive sample exists.","marker":"[23]"},{"why":"The simplified graph transformer with linear attention that the SGT policy network uses to widen the receptive field.","marker":"[28]"}],"fun_headline_variants":["Nested search plus graph transformer speeds MILP solving","Learning-based TLNS delivers 96% gains on MILPs","Inner LNS solves outer LNS for faster MILP optimization","Graph-guided two-layer LNS beats top MILP solvers","Graph transformer guides two-layer search to 96% speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole time-saving argument assumes that after the outer presolve, each inner auxiliary problem can be presolved much faster than the original auxiliary problem would be, so the nested scheme saves more time than it spends on extra inner iterations; the paper does not report presolve times T1p and T2p or inner iteration counts directly.","fun_headline_variants_meta":{"raw":{"variants":["Nested search plus graph transformer speeds MILP solving","Learning-based TLNS delivers 96% gains on MILPs","Inner LNS solves outer LNS for faster MILP optimization","Graph-guided two-layer LNS beats top MILP solvers","Graph transformer guides two-layer search to 96% speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000765,"raw_usage":{"total_tokens":3427,"prompt_tokens":1012,"completion_tokens":2415,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":628,"completion_tokens_details":{"reasoning_tokens":2331}},"tokens_in":628,"tokens_out":2415,"duration_ms":19408,"temperature":1.0,"reasoning_tokens":2331,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:05:46.787094+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure T1p (presolve time of the outer auxiliary problem), T2p (presolve time of a single inner auxiliary problem), and H (number of inner LNS iterations) on the four benchmark families. If H * T2p is not substantially smaller than (H - 1) * T1p, the Remark 2 time saving does not hold and TLNS could be slower than a single-layer LNS with an equivalent small neighborhood; the reported gains would then be attributable to neighborhood size or hardware, not nesting. A direct test is to run TLNS with the inner LNS replaced by a single exact solve of the same small neighborhood and compare wall-clock time per unit primal-bound improvement.","supporting_citations":[{"cited_title":"INFORMS Journal on Computing32(2), 473–506 (2020)","cited_arxiv_id":null,"evidence_quote":"Supplies the presolve reductions that Remark 2 relies on for the claim that presolving the outer auxiliary problem once makes inner presolves cheap."},{"cited_title":"Advances in neural information processing systems 32 (2019)","cited_arxiv_id":null,"evidence_quote":"Provides the variable-constraint bipartite graph representation used as the policy network's input."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gurobi is the off-the-shelf solver used for initial solutions and the main state-of-the-art baseline in the numerical comparison."},{"cited_title":"ZIB-Report 21-41, Zuse Institute Berlin (December 2021), http://nbn-resolving.de/urn:nbn:de:0297-zib-85309","cited_arxiv_id":null,"evidence_quote":"SCIP is the underlying solver used inside both LNS and TLNS (because its presolve is accessible) and is another baseline."},{"cited_title":"INFORMS Journal on Computing19(4), 534–541 (2007)","cited_arxiv_id":null,"evidence_quote":"The classic random large neighborhood search (R-LNS) that the paper compares against; also a source of the fixing-neighborhood definition."},{"cited_title":"Advances in Neural Information Processing Systems36 (2024)","cited_arxiv_id":null,"evidence_quote":"The simplified graph transformer with linear attention that the SGT policy network uses to widen the receptive field."}],"review_version":1}