GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container

Zhongman Du; Huiming Zhang; Linlin Yang; Sheng Xu; Baochang Zhang

cs.LGSep 30, 2026

GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container

Authors: Zhongman Du, Huiming Zhang, Linlin Yang, Sheng Xu, Baochang Zhang

Organizations: Beihang University, Beijing, China · Communication University of China, Beijing, China · Hangzhou Innovation Institute of Beihang University, Hangzhou, China

Abstract

The two-dimensional irregular knapsack problem in a fixed circular container is an important combinatorial optimization problem for maximizing material utilization in manufacturing. Conventional geometric packing solvers can produce tightly packed layouts, yet they often partition the residual space into isolated small pockets that cannot fit valuable unplaced polygons. To overcome this late-stage packing bottleneck, we propose a failure-aware large neighborhood search framework named GeoNest, driven by a graph policy trained via reinforcement learning. Specifically, we first construct neighborhoods by pairing failed target polygons with residual pockets. We then use explanatory poses to identify the placed polygons that block candidate insertions. These diagnosed blocking relations define bounded, fixed-item repair subproblems for the underlying geometric solver. Finally, the graph policy selects the most promising subproblem for execution. For evaluation, we introduce CircleNest-Bench, a benchmark comprising 2,391 load-controlled instances from four contour sources, including a held-out industrial CAD source. Experimental results demonstrate that, under the same total time budget, GeoNest improves mean utilization over a state-of-the-art standalone packing solver by about 0.9% on average across the three main test sets and by about 0.6% on the held-out industrial set.

Figures & tables

Figure 1: Failure geometry and grounded repair in 2D-CIKP. A target–pocket pair and its explanatory pose identify blockers, which define executable release-and-repack neighborhoods.

Figure 2: Overview of one GeoNest decision. An unpacked target is paired with a residual pocket, and an explanatory pose identifies candidate blockers. The resulting fixed-item repair actions are encoded in a graph and scored by the policy. PackingSolver then executes the selected action under its repair-time cap.

Split	E	S	G	I	Total
Train	720	720	360	–	1,800
Validation	90	90	54	–	234
Main	90	90	54	–	234
Industrial	–	–	–	14	14
Size	40	40	4	–	84
Stress	10	10	5	–	25

Table 1: CircleNest-Bench partitions. E, S, G, and I denote the ESICUP, Synthetic, Gardeyn, and Industrial sources, respectively. The Industrial source contains held-out CAD-derived contours.

Source ( $N$ )	2DNesting	Shadoks-MS	PackingSolver	GeoNest ( $\mu\!\pm\!\sigma$ )	Gain [95% CI]	W/T/L
ESICUP (90)	64.98	72.97	78.59	$\mathbf{79.55}\boldsymbol{\pm}\mathbf{0.08}$	$+0.96\,[0.64,1.31]$	$62/1/27$
Synthetic (90)	62.00	72.47	79.61	$\mathbf{80.64}\boldsymbol{\pm}\mathbf{0.08}$	$+1.03\,[0.70,1.39]$	$64/0/26$
Gardeyn (54)	60.47	72.17	76.93	$\mathbf{77.53}\boldsymbol{\pm}\mathbf{0.11}$	$+0.60\,[0.34,0.86]$	$36/2/16$
Main Avg. (234)	62.49	72.54	78.37	$\mathbf{79.24}\boldsymbol{\pm}\mathbf{0.08}$	$+0.87\,[0.69,1.05]$	$162/3/69$

Table 2: Main results under matched 650-s budgets. Entries report verifier-certified utilization (%). GeoNest is reported as the mean and sample standard deviation over three training seeds, and Main Avg. equally weights the three sources.

Figure 3: Verifier-certified PackingSolver and GeoNest layouts for the same instance under matched 650-s budgets.

(a) Matched 1200-s budget
Source	PS	GeoNest ( $\mu\!\pm\!\sigma$ )	Gain [95% CI]
ESICUP	78.81	$\mathbf{79.65}\boldsymbol{\pm}\mathbf{0.10}$	$+0.84\,[0.59,1.14]$
Synthetic	80.06	$\mathbf{80.96}\boldsymbol{\pm}\mathbf{0.13}$	$+0.90\,[0.68,1.14]$
Gardeyn	77.46	$\mathbf{78.03}\boldsymbol{\pm}\mathbf{0.13}$	$+0.57\,[0.31,0.82]$
Main Avg.	78.78	$\mathbf{79.55}\boldsymbol{\pm}\mathbf{0.11}$	$+0.77\,[0.63,0.92]$
(b) Cross-budget efficiency

Table 3: Long-budget results with verifier-certified utilization (%). Panel (a) reports matched 1200-s comparisons. Panel (b) compares 1200-s PackingSolver with the 650-s GeoNest configuration.

(a) Component analysis
Variant	E	S	G	Main	$\Delta$
PackingSolver	78.59	79.61	76.93	78.37	–
Generic-LNS	79.16	79.89	77.17	78.74	$+0.37$
FA-LNS-Random	79.32	80.43	77.34	79.03	$+0.66$
FA-LNS-Score	79.41	80.53	77.34	79.10	$+0.73$
FA-LNS-MLP	79.34	80.58	77.49	79.14	$+0.77$

Table 4: Component analysis. E, S, and G denote ESICUP, Synthetic, and Gardeyn. Panel (a) reports verifier-certified utilization (%), with

\Delta

denoting the equal-source Main improvement over PackingSolver. Panel (b) compares selectors under the same failure-aware action-generation procedure. GeoNest , FA-LNS-Random, and FA-LNS-MLP are averaged over three seeds.

(a) Main-set marginal trends
Factor	Low	Medium	High
$n$	$48\,(+1.00)$	$64\,(+0.93)$	$96\,(+0.67)$
$\lambda$	$1.2\,(+0.71)$	$1.5\,(+0.79)$	$2.0\,(+1.10)$

Table 5: Scale and load robustness under the 650-s budget. Panel (a) reports gains averaged over three seeds and equally across sources, with each cell showing the factor value and gain in pp. Panel (b) reports equal-source utilization (%) and gain, together with instance-level W/T/L, on the held-out Size and Stress shifts.

(a) Cross-source policy transfer
Train $\backslash$ Test	ESICUP	Synthetic	Gardeyn
ESICUP	$+0.96$	$+0.93$	$+0.63$
Synthetic	$+0.80$	$+1.03$	$+0.61$
Gardeyn	$+0.89$	$+0.89$	$+0.60$

Table 6: Generalization under the 650-s budget. Panel (a) reports seed-averaged gains over PS, with off-diagonal entries denoting zero-shot transfer. Panel (b) reports verifier-certified results on 14 held-out industrial CAD instances.

Explore similar work

Geometry-Aware Reinforcement Learning for 2D Irregular Nesting
Jun 9, 2026Auguste Lehuger, Guillaume Henon-JustGeometry-Aware Geometric Planning
Valeo Brain
GFPack++: Attention-Driven Gradient Fields for Optimizing 2D Irregular Packing
Jun 9, 2024Tianyang Xue, Lin Lu, Yang Liu +5Shape Optimization
Shandong University, China · Microsoft Research Asia, China · Peking University, China
GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem
Jun 22, 2026Xiang LiSalesman Problem Neural Solvers
College of Computer Science, Yangtze University, Jingzhou, China

Jun 9, 2026, cs.LGJ/K move · Enter open · S save

Geometry-Aware Reinforcement Learning for 2D Irregular Nesting

Auguste Lehuger, Guillaume Henon-Just

Valeo Brain

Geometry-Aware Geometric Planning Geometric Guidance

Open paper AskPDF arXiv

Traditional heuristic solvers for the 2D irregular nesting problem share a fundamental limitation: they are blind to polygon geometry, relying on guided brute-force to navigate the continuous placement space with minimal geometrical guidance. In this paper, we argue that Reinforcement Learning is uniquely positioned to overcome this bottleneck. By pairing an optimization policy with a geometry-aware neural encoder, an agent can automatically discover rich geometric priors directly from data, utilizing these learned intuitions to strategically guide exploration. To realize this, we introduce the Polygons Transformer (PoT), a novel architecture that encodes 2D continuous vector geometries while allowing cross-polygons attention. We couple this novel architecture with a Combinatorial Optimization Reinforcement Learning (CORL) training framework to find optimal solutions. To support this paradigm, we release an open-source training dataset derived from complex geographic contours alongside a dedicated evaluation benchmark. Our empirical validation demonstrates that our trained agent achieves area utilization performance highly competitive with Sparrow, the state-of-the-art heuristic solver, proving that reinforcement learning can successfully discover and exploit geometric awareness for precise spatial tasks.

Abstract

Explore similar work

Geometry-Aware Reinforcement Learning for 2D Irregular Nesting

GFPack++: Attention-Driven Gradient Fields for Optimizing 2D Irregular Packing

GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem