acceptodds
Desk rejected at ICLR 2027

Scalable Learned Large Neighborhood Search via Fixed-Canvas Segmentation

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Large neighborhood search improves an incumbent by releasing selected variables and repairing the resulting subproblem under a time limit. FOVEA casts variable selection as dense semantic segmentation on a fixed canvas. A small U-Net reads twelve semantic channels and predicts cell scores, which are decoded into a variable set subject to a fixed variable budget. Family-specific layouts connect the search state to the canvas, while one set of network weights serves four problem families. The FP32 network input occupies  kB across instance sizes. Our analysis bounds constraint coupling for spatially coherent regions, gives a rank certificate for rounds with zero possible improvement, and bounds the coupling advantage attainable on an expander family. On the tested families and hardware, FOVEA trails the strongest graph encoder at variables and overtakes it near ; the cost model provides an approximate crossover estimate. At larger sizes, where the graph-encoder baselines exceed device memory, FOVEA reduces the primal integral by to relative to the best runnable baselines. On the expander family, FOVEA performs comparably to random selection, with a coupling advantage close to one.

Primary area:
optimization
Keywords:
Large Neighborhood Search, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_KgsfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents FOVEA, which formulates the destroy step of Large Neighborhood Search as dense segmentation over a fixed-resolution canvas. Problem-specific layouts map optimization entities to the canvas, a U-Net predicts candidate regions, and the selected cells are decoded into variables for repair. The method is evaluated across several combinatorial optimization problems, with a focus on scalability, and is accompanied by theoretical analyses of spatial locality and constraint coupling.

Critical strengths
  1. The paper targets an important scalability issue in learned LNS and provides a simple fixed-size representation that remains usable at very large problem scales.
  2. The experiments are well-designed with proper controls.
Critical weaknesses
  1. This paper does not include AI Statement, which is mandatory. And the title in the submission system is inconsistent with the title in the PDF.
  2. Actual variable decoding relies on family-specific heuristics, so the learned contribution is not fully isolated.
  3. The comparison with g∝ng\propto\sqrt{n} only shows that a simple scale-dependent resolution is not beneficial. It remains unclear whether a more adaptive canvas strategy based on instance density or local complexity could better preserve fine-grained information while retaining scalability.
Questions for authors
  1. Why use U-Net? Will it be better to use other larger networks? More ablation studies about architecture should be included.
Reviewer_e41oOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Graph-encoder destroy operators for large neighborhood search scale poorly in cost and device memory. FOVEA rasterises the search state onto a fixed 128×128×12 canvas using family-specific layouts, such as an RCM-reordered constraint matrix for MILP or native coordinates for CVRP. One shared U-Net scores the cells, which are decoded into at most k ≤ 10³ variables for sub-solver repair, with conditional coupling, rank and expander results in the appendix. On a 200 s compute-charged primal integral, FOVEA trails CL-LNS at 10⁴ variables (by 2.8–5.6%), while at 10⁵–10⁶, where graph encoders exceed a 40 GB device, it beats its own region-growing control — the best runnable baseline — by 12.4–15.7% (Table 1). Routing gaps stay well above HGS (0.88% vs. 0.19%), and zero-shot transfer helps scheduling (7.5% below random selection) but not bin packing (1.8% above).

Critical strengths

S1. A fixed-resolution canvas as the interface for destroy selection differs from per-variable graph scoring (CL-LNS) and from the closest visual methods, which grow the image with n (Chen et al., 2025) or select rectangles on a rendered tour (Yin et al., 2026). The entity layer (Sec. 3.1, Table 5) lets one policy serve four families with a 786 kB input and 31–38 ms selection across three decades of n (Fig. 2a). The expander bound (Prop. 11) also serves as a falsification control, with coupling advantage 1.01 versus 3.4 on ordinary set cover (Sec. 4, Table 3).

S2. The region-growing control shares canvas, layout, truncation, budget, sub-solver and seeds (Sec. 4), and Table 3's factorial separates layout from learning: layout lowers the primal integral by 28.7% on set cover and 37.2% on CVRP relative to index order, and learning adds 8.7% and 9.2% on that layout (p < 0.01) but is not significant under index order. Selection time is charged, classical methods (SCIP, LB-RELAX, HGS, LKH-3, FILO2, CP-SAT) sit alongside CL-LNS, IL-LNS and L2D, Holm-corrected Wilcoxon tests are used (Sec. C.8), and negative results are reported.

Critical weaknesses

W1. The scaling claim has no learned comparator: at 10⁵–10⁶ the best runnable baseline is FOVEA's own control (Table 1), and CL-LNS is dropped for exceeding device memory (Fig. 2c) without trying host, CPU or partitioned inference, although FOVEA keeps its O(n) index on the host (Sec. A.8). Partition-based learned methods for large integer programs (Ye et al., ICML 2023; Light-MILPopt, ICLR 2024) are not discussed, and the hardware is ambiguous ("one CPU core" vs. "on the device"). Suggestion: add a learned baseline that runs at 10⁵–10⁶ under the same budget, and document hardware and baseline training.

W2. Some evidence is illustrative and some numbers conflict: Fig. 4 shows "reconstructed" curves with "generated" bands although traces were recorded (Sec. C.7); the rank panel (Fig. 3, right) is 4,000 generated points, yet Table 16 lists it as Proposition 1's result; LB-RELAX ranks ahead of Random LNS and RINS in Table 1 (89.1 vs. 96.4 and 94.8) despite selections of about 10² s at 10⁶ (Fig. 2a); FILO2-short "completes" within 200 s (Table 2) but takes 370 s and 532 s in Table 15; and Tables 1–4 omit the standard deviations described in Sec. C.8. Suggestion: plot recorded per-seed trajectories, report rounds and variance per method, and reconcile these entries.

W3. Most components are unablated: Table 17 specifies 35 studies but only the five in Table 4 have results, leaving channels and normalisation (A3, A8), two-stage decoding (B1), the perimeter penalty and block cap (B2, B5), refinement (C6), REINFORCE versus imitation (D1; the deployed choice is unstated), hindsight relabelling (D4) and the 1-D canvas (A6) untested. Sec. C.5 is empty, two splits (Table 7) have no results, and the deployed setting is not the best arm in four of the five reported studies. Suggestion: ablate or remove each component and justify the defaults.

W4. The theory does not certify the deployed operator — the bounds "do not transfer to the truncated set" (Sec. A), Proposition 1 does not apply to the inequality-only families, and n⋆ uses a slope fitted on the same CL-LNS runs (Table 11) — and the practical gains are narrow: CL-LNS wins all four synthetic families at 10⁴ (Table 9), HGS, LKH-3 and FILO2 reach lower routing gaps (Table 2), CP-SAT reportedly does better on scheduling (no numbers), and bin packing does not benefit. Suggestion: measure coupling on truncated sets, validate n⋆ on held-out sizes, and report CP-SAT primal integrals.

Questions for authors

Q1. At 10⁵–10⁶, how does FOVEA compare with CL-LNS using host memory or partitioned inference? Were CL-LNS and IL-LNS retrained at 10⁴?

Q2. How many rounds did each method complete at n = 10⁶ in Table 1, and how does LB-RELAX reach 89.1 given Fig. 2(a)? Was FILO2-short cut off at 200 s on set I and Lazio?

Q3. Can recorded per-seed trajectories replace Fig. 4, with standard deviations or confidence intervals in Tables 1–4?

Q4. In Table 4, does the rank rule's edge over adaptive growth (45.2 vs. 46.9, using the tight-inequality heuristic) hold at a matched average budget? On equality-constrained families, what fraction of rounds is full-rank?

Q5. Which components explain the 8.7% gain over region growing in Table 3? What does training cost in oracle solves, wall-clock time and hardware?

Reviewer_rTuCOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

Typical learned destroy operators used for large neighborhood search in mixed integer programming solvers, encode the problem as a graph whose cost grows with instance size and quickly runs out of memory on larger real-world instances. This paper proposes FOVEA, which lays out the variables on a fixed-size 2D canvas and trains a small U-Net to decide which regions to focus on. This makes the cost independent of problem size, and leads to gains here the problem structures have spatial locality.

Critical strengths

The problem statement is valid and it is reasonable to assume that leveraging spatial locality in the problem structure will be able to learn meaningful destroy operators which do not scale linearly with problem size. The authors also report negative results on expanders and bin packing, which clarifies where this may not help.

Critical weaknesses

The paper has significant writing and presentation issues which make it near impossible to understand.

First the title as presented in the Openreview page and the paper header do not match!

Going into the paper, at the very beginning, the abstract is extremely poorly written. It is just a compressed list of facts which might make sense to someone who has already read the paper. For a first time human reader, it is a collection of unexplained jargon and numbers. Assuming the reader has background needed to understand the jargon (incumbent, primal integral, coupling advantage, expander family), what even would “coupling advantage close to one” mean for someone who hasn’t made their way to page 6 analysis of the paper? The abstract completely unable to convey the central problem this paper aims to solve. Why include low level details such as “The FP32 network input occupies 786 kB” – what do I make of it without understanding the problem statement.

The introduction also needs to be significantly improved. Claims like graph encoders "reach the memory limit beyond a few times 10^4 variables" are stated without evidence or explanation. Later in the intro, discussion on FOVEA starts abruptly. Nothing tells the reader what FOVEA is and what is its purpose? The mix of claims, results and forward references are difficult to disentangle and cause significant cognitive overload.

Figure 1 only adds to the confusion. There are a bunch of unexplained symbols, none of which make sense at that stage. What are κ\kappa, B∂B_\partial or η\eta ? These seem to be mentioned only in section 3.6 and then in the appendix.

Coupling is introduced in the Preliminaries, but the paper never clearly explains why a destroy set with low coupling should give a better neighborhood.

Notation is confusing. Why is ρ\rho the destroy fraction and ρmax⁡\rho_{\max} the variable density?

After making our way through the incomprehensible landscape above, we land into the following where the authors make a research proposal but never actually run/report the experiments.

Where are the promised “the ablation design includes a one-dimensional canvas”, “the ablation design also specifies a separate normalisation study”. Where exactly is the comparison promised under “Section B.5 describes the proposed comparison of truncation rules”? “The optional refinement in Section B.6 re-rasterises the selected region “ – is this evaluated or ever used ? “End-to-end CP-SAT retains better performance.” – where are the numbers? “At budgets k in the hundreds, the rank test takes milliseconds.”” – no timing is ever reported.

Fig. 3 (right) plots "4000 generated points". Why not plot the actual data from your runs?

Finally, the paper reads “Under review as a conference paper at ICLR 2026” !!

Questions for authors

Due to the significant issues with the writing and incomplete experiements, the paper needs a significant revision. The authors propose many experiments in Table 17 of the appendix, many of which are not currently run/reported. As of now, I do not have any questions for the authors which would materially affect my assessment. My feedback is detailed above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.