Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/4/2026, 3:20:54 AM
Summary
The paper introduces GeoNest, a failure-aware large neighborhood search framework for the Two-Dimensional Circular-Container Irregular Knapsack Problem (2D-CIKP). It uses a graph policy trained via reinforcement learning to select repair subproblems defined by pairing failed target polygons with residual pockets and identifying blocking items. The method improves mean utilization over state-of-the-art solvers by approximately 0.9% on average and 0.6% on industrial data, evaluated on the new CircleNest-Bench dataset.
Entities (6)
Relation Signals (6)
GeoNest → evaluatedon → CircleNest-Bench
confidence 95% · For evaluation, we introduce CircleNest-Bench... Experimental results demonstrate that... GeoNest improves mean utilization
GeoNest → solves → 2D-CIKP
confidence 95% · we propose a failure-aware large neighborhood search framework named GeoNest... The two-dimensional irregular knapsack problem in a fixed circular container is an important combinatorial optimization problem
GeoNest → trainspolicywith → PPO
confidence 90% · masked GNN policy trained with PPO
GeoNest → uses → GNN
confidence 90% · GeoNest... driven by a graph policy trained via reinforcement learning... masked GNN policy
GeoNest → calls → PackingSolver
confidence 85% · PackingSolver (Fontan 2026) executes the selected repair with all other pieces fixed
GeoNest → improvesutilizationover → PackingSolver
confidence 85% · GeoNest improves mean utilization over a state-of-the-art standalone packing solver by about 0.9% on average
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.38863v1
- Canonical: https://arxiv.org/abs/2609.38863v1
Trouble viewing inline? Open PDF directly →
Full Text
47,671 characters extracted from source content.
Expand or collapse full text
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 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. 1Beihang University, Beijing, China 2Communication University of China, Beijing, China 3Hangzhou Innovation Institute of Beihang University, Hangzhou, China Introduction Two-dimensional irregular packing is a classical NP-hard problem with broad applications in material cutting, industrial nesting, and texture atlas generation (Lee et al. 2008; Nöl and Stricker 2011). Most studies consider strip or rectangular containers, whose straight boundaries and principal directions provide natural references for piece placement (Leão et al. 2020). In contrast, substrates such as semiconductor wafers and optical lens blanks are often circular or nearly circular and lack corner structure. Prior circular-container studies mainly consider regular objects (Huang et al. 2006; López and Beasley 2018). To our knowledge, this is the first study of irregular polygon knapsack packing in a fixed circular container. We call this problem the Two-Dimensional Circular-Container Irregular Knapsack Problem (2D-CIKP). Given an overloaded candidate set, 2D-CIKP selects a subset and determines translations and continuous rotations to maximize packed area subject to containment and non-overlap. Traditional methods combine explicit geometric computation with constructive heuristics or metaheuristic search, but early placement decisions can lock the search into unfavorable residual-space structures (Gomes and Oliveira 2006; Sato et al. 2019). Recent generative approaches jointly refine multiple piece poses (Xue et al. 2023; Xue et al. 2025), while reinforcement learning methods optimize packing sequences or select predefined low-level operators (Fang et al. 2023; Wang et al. 2026b). These approaches do not turn the interaction between an unpacked target and the residual geometry into a targeted repair decision. This limitation is most acute in the late stages of search. Geometry-based solvers quickly construct high-quality feasible layouts, but further improvement becomes difficult as utilization rises and residual free space fragments into pockets with blocked access or incompatible shapes. A valuable polygon can then remain unpacked even when the total residual area exceeds its area, while generic perturbations preserve the same bottleneck. As illustrated in Fig. 1, pairing a failed target with a residual pocket exposes an explanatory pose and its blockers, turning failure geometry into concrete release-and-repack neighborhoods. The central late-stage decision is therefore which neighborhood to repair next. 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. We therefore propose GeoNest, a failure-aware, learning-guided large-neighborhood search framework that augments geometry-based solvers, as illustrated in Fig. 2. Following learning-guided neighborhood search (Wu et al. 2021; Reijnen et al. 2024), GeoNest does not predict complete layouts or continuous poses. Starting from a feasible layout produced by bounded geometric search, it pairs unpacked targets with compatible residual pockets, constructs explanatory poses, and uses the resulting blockers to compile fixed-item repair neighborhoods at multiple scales. Each executable neighborhood forms an action defined by its release set, admitted unpacked items, scale, and repair-time cap. The value of an action depends on the current target–pocket–blocker configuration. Each repair decision updates future eligible actions and the remaining budget and may change the residual geometry, so neighborhood selection is sequential. Targets, pockets, blockers, and actions are encoded in a heterogeneous graph, where a masked GNN policy trained with PPO ranks eligible actions. PackingSolver (Fontan 2026) executes the selected repair with all other pieces fixed, and a common geometric verifier certifies the result. For evaluation, we introduce CircleNest-Bench, comprising 2,391 load-controlled circular-container instances from four contour sources. It covers in-distribution testing, size extrapolation, overload stress testing, cross-source transfer, and held-out industrial CAD. All methods use identical instances and matched time budgets, and only verifier-certified layouts contribute utilization. GeoNest improves certified utilization over the strongest geometry-based baseline by 0.6% to 1.0%. Ablations isolate the contributions of failure-aware neighborhood construction and learned neighborhood selection. The main contributions are as follows. • We formalize 2D-CIKP and introduce CircleNest-Bench, a benchmark of 2,391 load-controlled instances from four contour sources. • We introduce a failure-aware neighborhood construction mechanism that uses target–pocket pairs and explanatory poses to diagnose blockers and compile fixed-item repair neighborhoods. • We propose GeoNest, which casts failure recovery as sequential selection among repair-neighborhood actions and uses a masked GNN policy trained with PPO to rank them. Experiments demonstrate improved certified utilization and generalization across instance sizes and contour sources. Related Work Irregular Packing and Fixed-Container Problems Irregular packing relies on explicit geometric models of containment, non-overlap, and candidate placement. No-fit polygons encode pairwise relative-placement constraints, while raster models and mixed-integer formulations provide alternative mechanisms for geometric feasibility (Bennell and Oliveira 2008; Burke et al. 2007; Umetani and Murakami 2022; Lastra-Díaz and Ortuño 2024). Large neighborhood search and adaptive large neighborhood search provide general frameworks for improving incumbent solutions (Pisinger and Ropke 2010; Ropke and Pisinger 2006), and recent work applies LNS to irregular bin packing through large-scale perturbations of cross-bin polygon assignments (Wang et al. 2026a). Open-source heuristics such as Sparrow improve reproducibility (Gardeyn et al. 2025). Representative circular-container studies consider packing regular objects, including unequal circles and rectangles, in a fixed circular container (López and Beasley 2016; Bouzid and Salhi 2020). The closest prior formulation we are aware of is the Maximum Polygon Packing problem from the CG:SHOP 2024 Challenge (Fekete et al. 2024), addressed by representative SoCG approaches (Atak et al. 2024; da Fonseca and Gerard 2024). It considers profit-maximizing subset selection in a fixed convex polygonal container but permits translations only. 2D-CIKP instead considers a fixed circular container with continuous rotations, making radial boundary effects and the orientation-dependent accessibility of residual pockets central to subsequent insertions. Learning-Guided Packing and Neighborhood Search Learning-based irregular packing methods act during layout construction or refinement. Reinforcement learning has been used to optimize piece sequences (Fang et al. 2023), select low-level operators for sequence and orientation optimization (Wang et al. 2026b), and learn rotational placement within hybrid nesting pipelines (Abdou et al. 2026). Yang et al. select and group irregular UV patches and predict their relative poses, whereas GFPack and GFPack++ learn gradient fields for joint layout refinement (Yang et al. 2023; Xue et al. 2023; Xue et al. 2025). In contrast, the learned policy in GeoNest operates after bounded geometric search and uses unpacked items as failure targets without predicting placement coordinates or rotations. A complementary line preserves a conventional solver and learns to control large neighborhood search. For integer programs, learned policies select neighborhoods or variables for solver-based reoptimization (Song et al. 2020; Wu et al. 2021). Neural large neighborhood search learns repair heuristics, while learned ALNS methods control operators, parameters, or acceptance decisions (Hottung and Tierney 2022; Reijnen et al. 2024; Johnn et al. 2024). GeoNest follows this solver-control principle but uses a different action interface. Instead of selecting a global operator or a generic subset of solver variables, it ranks repair actions constructed from the current failed target and its local geometric context. Problem Formulation and Benchmark Task formulation. An instance of 2D-CIKP consists of a fixed circular container and n candidate polygonal items. Let [n]=1,…,n[n]=\1,…,n\ and let Pi⊂ℝ2P_i ^2 be a compact simple polygonal region with area ai=area(Pi)>0a_i=area(P_i)>0. The container is the fixed disk DR=x∈ℝ2:∥x∥2≤RD_R=\x ^2: x _2≤ R\ with radius R>0R>0. A selected item i is assigned a pose qi=(i,θi)∈ℝ2×[0,2π)q_i=(u_i, _i) ^2×[0,2π), where iu_i is a continuous translation vector and θi _i may take any in-plane angle over the full 360∘360 range. Its transformed region is Xi(qi)=Q(θi)Pi+iX_i(q_i)=Q( _i)P_i+u_i, where Q(θi)Q( _i) is the planar rotation matrix. Reflections are not allowed. A layout is L=(zi,qi)i=1nL=\(z_i,q_i)\_i=1^n, where zi∈0,1z_i∈\0,1\ indicates whether item i is selected and qiq_i is immaterial when zi=0z_i=0. The layout is feasible if the following conditions hold for every i∈[n]i∈[n] and every pair i<ji<j: zi=1 z_i=1 ⟹Xi(qi)⊆DR, \ X_i(q_i) D_R, zi=zj=1 z_i=z_j=1 ⟹intXi(qi)∩intXj(qj)=∅. \ intX_i(q_i) _j(q_j)= . Boundary contact is allowed. For a feasible layout, define its disk utilization as U(L)=∑i=1nziaiπR2.U(L)= _i=1^nz_ia_iπ R^2. Let ℒfeasL_feas denote the set of feasible layouts. We solve L⋆∈argmaxL∈ℒfeasU(L).L ∈ *argmax_L _feasU(L). Since R is fixed for each instance, maximizing U(L)U(L) is equivalent to maximizing the total packed area. The offered load is λ=∑i=1naiπR2,R=∑i=1naiπλ.λ= _i=1^na_iπ R^2, R= _i=1^na_iπλ. (1) CircleNest-Bench uses λ>1λ>1, so the total candidate area exceeds the disk area and subset selection is necessary. CircleNest-Bench. Public irregular-packing collections provide diverse source contours for constructing controlled circular-container knapsack instances across size, load, and source shifts. To provide a reproducible evaluation basis, CircleNest-Bench contains 2,391 load-controlled 2D-CIKP instances generated from ESICUP shapes, controlled synthetic shapes, the Gardeyn nesting instances, and a held-out industrial geometry source (ESICUP 2025; Gardeyn et al. 2025). The benchmark converts the source contours into new circular-container knapsack instances and sets the disk radius from Eq. (1) after forming the candidate set. Tab. 1 reports the complete split statistics. 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 Total 950 950 477 14 2,391 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. Splits and evaluation. The partitions are disjoint at the base candidate-item-set level. All load variants derived from the same base set share identical items, differ only in disk radius, and remain in the same split. Primary evaluation uses ESICUP Main, Synthetic Main, and Gardeyn Main and reports the unweighted macro average of their source-level means. The Main partitions span n∈48,64,96n∈\48,64,96\ and offered loads λ∈1.2,1.5,2.0λ∈\1.2,1.5,2.0\. The Size split evaluates extrapolation to n=128n=128 at λ∈1.5,2.0λ∈\1.5,2.0\, while Stress fixes n=64n=64 and tests λ=2.5λ=2.5. The held-out size n=128n=128 and load λ=2.5λ=2.5 do not appear in training or validation. Industrial contains 14 test-only CAD instances with n=100n=100 and λ=1.5λ=1.5. Its source contours do not occur in training or validation, and the Industrial split is excluded from the three-source Main average. All methods submit layouts to a common verifier that reconstructs every transformed polygon from the immutable instance geometry, checks item identities, disk containment, and pairwise non-overlap, and recomputes U(L)U(L). The primary metric is verifier-certified utilization, and invalid layouts receive zero. The benchmark release includes the instance files, split manifests, generation scripts, and verifier. Additional details on source mappings, instance construction, split auditing, and verification are provided in the supplementary material. Method Given a feasible initial layout L0L_0 and a takeover budget, GeoNest treats items left unpacked by bounded search as failure targets and pairs them with residual pockets to construct fixed-item repair subproblems. A graph policy ranks the corresponding solver calls and allocates the next portion of the budget to the selected subproblem. Fig. 2 illustrates the process. Failure-Grounded Neighborhoods At decision t, the controller state is st=(Lt,Bt,ℋt,ℱt,t,ζt),s_t=(L_t,B_t,H_t,F_t,P_t, _t), where LtL_t and BtB_t are the current and certified best layouts, respectively, ℋtH_t stores verifier-valid, geometrically distinct archived layouts, ℱtF_t orders items left unpacked by the preceding bounded search, tP_t contains residual pockets, and ζt _t records the remaining budget, stagnation, and retry state. Let ℐ(Lt)I(L_t) denote the identities of items placed in LtL_t. Using a deterministic polygonal disk proxy D^R D_R, we define the residual region as Ω^t=D^R∖⋃i∈ℐ(Lt)Xi(qi). _t= D_R _i (L_t)X_i(q_i). The nonempty connected components obtained by intersecting Ω^t _t with fixed multiscale radial and angular windows form tP_t. For a target f and pocket p, the compatibility score ρ(f,p)∈[0,1]ρ(f,p)∈[0,1] combines their area ratio with the best axis-aligned bounding-box fit under the original and 90∘90 -swapped spans and ranks target–pocket pairs for geometric testing. For each retained pair (f,p)(f,p), the generator constructs finite orientation and translation-anchor sets and produces 0(f,p)=q=(,θ)∣θ∈Θ(f,p),∈(f,p,θ).Q_0(f,p)=\q=(u,θ) θ∈ (f,p),\ u (f,p,θ)\. A pose is retained if the transformed target lies inside the disk and at least a fraction η∈(0,1]η∈(0,1] of its area overlaps p. It may overlap incumbent items, whose identities define the pose-induced blockers ℬt(f,q)=i∈ℐ(Lt)|area(Xf(q)∩Xi(qi))>εblk,B_t(f,q)= \i (L_t)\ |\ area\! (X_f(q)∩ X_i(q_i) )> _blk \, where εblk>0 _blk>0 is the blocker-overlap threshold. Among the retained poses, the explanatory pose q⋆q maximizes a fixed pose score that rewards pocket coverage and penalizes blocked area, blocker count, and radial displacement. Its blockers form the core release set, while the repair solver determines the final poses. Exact formulations of ρ(f,p)ρ(f,p) and q⋆q are provided in the supplementary material. Each executable failure-specific repair neighborhood defines a grounded action of the form a=(fa,pa,ℛa,Ca,ma,τa),a=(f_a,p_a,R_a,C_a,m_a, _a), where faf_a and pap_a are its target and pocket, ℛaR_a is the release set, Ca∋faC_a f_a is a bounded set of admitted unpacked items, and τa _a is the repair-time cap. The mode ma∈core,local,connected,deep-connectedm_a∈\ core, local, connected, deep-connected\ determines ℛaR_a. core releases only the pose-induced blockers, local also releases nearby placed items, and the connected modes expand through the placed-item connectivity graph at increasing depth. Additional unpacked items are admitted only when they have positive compatibility with pap_a and are ranked by compatibility, shape complementarity, and area ratio. The repair-time cap scales with the movable-item count, total vertex count, and neighborhood scale, subject to the remaining takeover budget. Algorithm 1 summarizes the compilation procedure. Algorithm 1 Failure-grounded neighborhood compilation 1: Layout LtL_t, frontier ℱtF_t, pockets tP_t, control state ζt _t 2: t←∅A_t← 3: for f∈TargetFrontier(ℱt)f∈ TargetFrontier(F_t) do 4: for p∈DiversePockets(f,t)p∈ DiversePockets(f,P_t) do 5: q⋆←ExplanatoryPose(f,p,Lt)q ← ExplanatoryPose(f,p,L_t) 6: if q⋆q exists then 7: ℬcore←ℬt(f,q⋆)B^core _t(f,q ) 8: for m∈AvailableModes(ζt)m∈ AvailableModes( _t) do 9: ℛ←ExpandRelease(ℬcore,m)R← ExpandRelease(B^core,m) 10: C←f∪PositiveFitAdmit(f,p)C←\f\∪ PositiveFitAdmit(f,p) 11: τ←RepairBudget(ℛ,C,m,ζt)τ← RepairBudget(R,C,m, _t) 12: if τ is executable then 13: add (f,p,ℛ,C,m,τ)(f,p,R,C,m,τ) to tA_t 14: end if 15: end for 16: end if 17: end for 18: end for 19: return ActionMask(BalanceAndCap(t),ζt) ActionMask( BalanceAndCap(A_t), _t) The compiler retains at most KAK_A candidates. It allocates most slots round-robin across neighborhood modes, covers unseen target–pocket pairs, and backfills remaining slots by the fixed geometric score. The action mask merges candidates inducing the same fixed-item subproblem, suppresses exact repeats, and permits bounded semantic retries. Sustained stagnation enables progressively deeper neighborhoods. Graph Policy At decision t, GtG_t encodes each executable repair and its failure geometry. Typed nodes represent targets, pockets, blockers, actions, boundary context, admission context and archived layouts. Object-node attributes encode normalized geometry, failure history, and search context, while action-node attributes encode the fixed geometric score, repair scope, time cap, mode, and remaining-budget ratio. Typed edges encode target–pocket fit, blocker and coupling relations, action membership, and archive dominance. The actor and critic use independent typed GNN encoders with relation-specific, edge-gated mean aggregation. The actor scores action nodes, while the critic pools non-action nodes to estimate the state value. A raw fixed geometric score h(a)h(a) enters the action logits over the eligible set za=ℓψ(a∣Gt)+ωhh(a)τπ,πψ=softmaxa∈telig(za).z_a= _ψ(a G_t)+ _hh(a) _π, _ψ=softmax_a _t^elig(z_a). Here, teligA_t^elig denotes the eligible action set after masking, and ψ denotes the policy parameters. The terms ℓψ(a∣Gt) _ψ(a G_t) and h(a)h(a) are the learned action logit and deterministic geometric score, respectively, while ωh _h and τπ _π are the score weight and policy temperature. Training samples from πψ _ψ, whereas inference selects its maximizer. Fixed-Item Repair and Verification For action a, define Ka=ℐ(Lt)∖ℛa,Ia=Ka∪ℛa∪Ca.K_a=I(L_t) _a, I_a=K_a _a∪ C_a. The repair instance contains IaI_a, with items in KaK_a fixed at their current poses and items in ℛa∪CaR_a∪ C_a, including faf_a, optional and movable. For each repair instance, PackingSolver approximates the continuous rotation domain with a finite, geometry-dependent orientation set Θexec(Ia) _exec(I_a) and searches continuous translations at those orientations within τa _a, returning the feasible candidate with highest U(L)U(L). An internal repair validator enforces fixed poses and checks the merged full layout. The common true-disk verifier then applies the benchmark checks and recomputes U(L)U(L). A candidate passing both checks becomes the certified candidate L^t L_t. If U(L^t)>U(Bt)U( L_t)>U(B_t), we set Lt+1=Bt+1=L^tL_t+1=B_t+1= L_t. If U(L^t)=U(Lt)=U(Bt)U( L_t)=U(L_t)=U(B_t) and the candidate creates a new search context with different action-relevant geometry, we set Lt+1=L^tL_t+1= L_t and retain Bt+1=BtB_t+1=B_t under the bounded plateau rule. If no certified candidate is returned or neither condition holds, we retain Lt+1=LtL_t+1=L_t and Bt+1=BtB_t+1=B_t. Thus, Bt+1B_t+1 remains feasible and satisfies U(Bt+1)≥U(Bt)U(B_t+1)≥ U(B_t). Learning Objective Because each repair decision updates the eligible actions and remaining budget and may change the residual pockets, neighborhood selection is sequential, and the learning objective balances immediate certified improvement, repair cost, and downstream packability. Let ΔtB=U(Bt+1)−U(Bt) _t^B=U(B_t+1)-U(B_t). We use the step reward with potential-based shaping (Ng et al. 1999) rt=βBΔtB−βcc^t+βΦ[γΦ(st+1)−Φ(st)]+rtevt,r_t= _B _t^B- _c c_t+ _ [γ (s_t+1)- (s_t) ]+r_t^evt, where βB _B, βc _c, and βΦ _ are fixed reward coefficients, γ is the discount factor, and c^t c_t is the normalized repair time. The fixed potential Φ satisfies Φ(s)∈[0,1] (s)∈[0,1] for every state s and assigns higher values to promising states based on unresolved-item burden, residual placeability, and layout quality. The event term contains clipped degraded-candidate feedback and fixed outcome penalties. At terminal step H, it credits improving transitions in proportion to U(BH)−U(L0)U(B_H)-U(L_0). A terminal correction preserves telescoping over the finite horizon. We train the masked actor–critic using PPO and GAE (Schulman et al. 2016; Schulman et al. 2017). During training, bounded probes compare alternative eligible actions by verifier-certified outcome, and the PPO loss includes a low-weight preference term favoring the better action. Only the policy-selected action advances the trajectory, and training uses fixed, certified initial layouts. Complete takeover pseudocode and implementation details are provided in the supplementary material. Experiments Source (N) 2DNesting Shadoks-MS PackingSolver GeoNest (μ±σμ\!±\!σ) Gain [95% CI] W/T/L ESICUP (90) 64.98 72.97 78.59 79.55±0.0879.55 ±0.08 +0.96[0.64,1.31]+0.96\,[0.64,1.31] 62/1/2762/1/27 Synthetic (90) 62.00 72.47 79.61 80.64±0.0880.64 ±0.08 +1.03[0.70,1.39]+1.03\,[0.70,1.39] 64/0/2664/0/26 Gardeyn (54) 60.47 72.17 76.93 77.53±0.1177.53 ±0.11 +0.60[0.34,0.86]+0.60\,[0.34,0.86] 36/2/1636/2/16 Main Avg. (234) 62.49 72.54 78.37 79.24±0.0879.24 ±0.08 +0.87[0.69,1.05]+0.87\,[0.69,1.05] 162/3/69162/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. Experimental Setup Data and training. We evaluate all methods on the held-out test partitions in Tab. 1. For each non-CAD source, we train three policies using seeds 42, 3407, and 7301, with checkpoints selected on a fixed source-specific validation set and frozen before testing. Results are averaged per instance across seeds before source aggregation, and Main Avg. equally weights ESICUP, Synthetic, and Gardeyn. All nine policies are evaluated zero-shot on CAD, with results grouped by training source. Training, validation, and tuning use only the three non-CAD sources. Baselines. Reproducible competitive irregular-packing implementations remain scarce (Gardeyn et al. 2025). We compare against PackingSolver (PS) (Fontan 2026), 2DNesting (lryan599 2025), and Shadoks-MS (da Fonseca and Gerard 2024). All three baselines are deterministic under our configurations and evaluated once per instance. PS is used without algorithmic modification, while 2DNesting and Shadoks-MS are adapted to the circular-container knapsack setting. All methods solve identical instances under matched wall-clock budgets and search orientations over the full [0∘,360∘)[0 ,360 ) range using their own placement and orientation-search strategies. Protocol and metrics. Under the 650-s budget, standalone methods use the full budget, while GeoNest uses 350 s for PS initialization and 300 s for takeover. Validation curves showed that PS plateaued by 350 s, so this split was fixed before testing. Under the 1200-s budget, PS uses the full budget, while GeoNest uses 600 s each for initialization and takeover. Failure-geometry extraction, action and graph construction, policy inference, repair, in-loop verification, rollback, and controller bookkeeping count toward the takeover budget. All methods are evaluated on the same Intel Xeon Platinum 8352V node with 125 GiB RAM and one CPU thread per instance, while training uses one NVIDIA RTX A5000 GPU. We report verifier-certified mean utilization, paired gain in percentage points, and instance-level W/T/L against PS. After averaging over training seeds, 95% confidence intervals are computed from 200,000 paired cluster-bootstrap resamples of base candidate-item sets within each source, with all load variants of each sampled set retained together. Sources are resampled separately before computing Main Avg. Selector comparisons use two-sided paired sign-flip tests at the base-set level with Holm correction. Main Comparison under Matched Budgets Matched-budget performance. Tab. 2 shows positive gains across all three sources, and all paired 95% confidence intervals exclude zero. PackingSolver already reaches a Main Avg. utilization of 78.37%78.37\%. At this utilization level, further improvement increasingly depends on reorganizing constrained residual space rather than filling obvious gaps. These results support a late-stage shift in search strategy after geometric construction has matured, redirecting computation from continued generic improvement to failure-conditioned repair, as illustrated in Fig. 3. Figure 3: Verifier-certified PackingSolver and GeoNest layouts for the same instance under matched 650-s budgets. Budget robustness and efficiency. The matched 1200-s comparison shows positive gains across all three sources. Despite using 45.8% less time, the 650-s GeoNest configuration exceeds PackingSolver at 1200 s by 0.46 p. The matched-budget gain at 1200 s retains 88.5% of the 650-s gain, showing that the benefit persists as both methods receive more time. This cross-budget reversal shows that targeted repair is more effective than nearly doubling generic search time. (a) Matched 1200-s budget Source PS GeoNest (μ±σμ\!±\!σ) Gain [95% CI] ESICUP 78.81 79.65±0.1079.65 ±0.10 +0.84[0.59,1.14]+0.84\,[0.59,1.14] Synthetic 80.06 80.96±0.1380.96 ±0.13 +0.90[0.68,1.14]+0.90\,[0.68,1.14] Gardeyn 77.46 78.03±0.1378.03 ±0.13 +0.57[0.31,0.82]+0.57\,[0.31,0.82] Main Avg. 78.78 79.55±0.1179.55 ±0.11 +0.77[0.63,0.92]+0.77\,[0.63,0.92] (b) Cross-budget efficiency Source PS GeoNest (μ±σμ\!±\!σ) Gain [95% CI] ESICUP 78.81 79.55±0.0879.55 ±0.08 +0.74[0.50,1.01]+0.74\,[0.50,1.01] Synthetic 80.06 80.64±0.0880.64 ±0.08 +0.58[0.32,0.85]+0.58\,[0.32,0.85] Gardeyn 77.46 77.53±0.1177.53 ±0.11 +0.07[−0.17,0.30]+0.07\,[-0.17,0.30] Main Avg. 78.78 79.24±0.0879.24 ±0.08 +0.46[0.32,0.61]+0.46\,[0.32,0.61] 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. Gardeyn is the only source with an inconclusive cross-budget comparison. Its more concave and intricate polygons induce complex pockets and blocker relations. The positive matched-budget gain and weaker cross-budget result are consistent with such geometry requiring a longer repair horizon. Ablation and Generalization Component analysis. All variants reuse the same 350-s PackingSolver layout and receive 300 s. Generic-LNS is failure-blind. FA-LNS-Random, FA-LNS-Score, FA-LNS-MLP, and GeoNest use the same state-dependent failure-aware action-generation procedure and repair executor. They differ only in action selection, using random choice, a fixed score, an MLP, or the relation-aware GNN. (a) Component analysis Variant E S G Main Δ PackingSolver 78.59 79.61 76.93 78.37 – Generic-LNS 79.16 79.89 77.17 78.74 +0.37+0.37 FA-LNS-Random 79.32 80.43 77.34 79.03 +0.66+0.66 FA-LNS-Score 79.41 80.53 77.34 79.10 +0.73+0.73 FA-LNS-MLP 79.34 80.58 77.49 79.14 +0.77+0.77 GeoNest 79.55 80.64 77.53 79.24 +0.87+0.87 (b) Direct selector and architecture comparisons Comparison Gain 95% CI pHolmp_Holm GeoNest −- Random +0.21+0.21 [0.13,0.29][0.13,0.29] 1.50×10−51.50×10^-5 GeoNest −- Score +0.14+0.14 [0.04,0.26][0.04,0.26] 1.95×10−21.95×10^-2 GeoNest −- MLP +0.10+0.10 [0.03,0.18][0.03,0.18] 1.95×10−21.95×10^-2 Table 4: Component analysis. E, S, and G denote ESICUP, Synthetic, and Gardeyn. Panel (a) reports verifier-certified utilization (%), with Δ 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. Failure-aware actions and learned selection. Failure-aware actions account for most of the gain beyond Generic-LNS. Because all selectors use the same action-generation procedure and repair executor, Tab. 4(b) isolates the value of action selection. GeoNest significantly outperforms Random, Score, and MLP, showing that relation-aware modeling of the target–pocket–blocker structure adds value beyond heuristic and non-graph learned ranking. A one-step audit of 18 states, for which all candidate actions were evaluated, found that the GNN selected the best immediate repair in 61.1% of cases and achieved a higher immediate gain than the mean over candidate actions, linking the end-to-end improvement to action-level discrimination. Scale and load. Tab. 5 shows opposite trends for instance size and packing pressure. Gain decreases with n but increases with λ, indicating that GeoNest responds more strongly to spatial competition than to instance size alone. With larger item sets, a fixed repair budget is spread across more candidate neighborhoods, whereas higher load magnifies the impact of blockers and residual pockets. (a) Main-set marginal trends Factor Low Medium High n 48(+1.00)48\,(+1.00) 64(+0.93)64\,(+0.93) 96(+0.67)96\,(+0.67) λ 1.2(+0.71)1.2\,(+0.71) 1.5(+0.79)1.5\,(+0.79) 2.0(+1.10)2.0\,(+1.10) (b) Held-out shifts Shift (N) PackingSolver GeoNest (μ±σμ\!±\!σ) Gain W/T/L Size (84) 80.70 80.92±0.0780.92 ±0.07 +0.22+0.22 63/10/1163/10/11 Stress (25) 77.86 78.56±0.0878.56 ±0.08 +0.70+0.70 18/2/518/2/5 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 p. Panel (b) reports equal-source utilization (%) and gain, together with instance-level W/T/L, on the held-out Size and Stress shifts. The held-out shifts reinforce this interpretation. Stress yields 3.2 times the mean gain of Size despite similar win rates. This pattern suggests that packing pressure affects the magnitude of improvement more than the frequency of wins, consistent with future-feasibility loss driven by residual-space competition. Cross-source and industrial transfer. All six off-diagonal gains are positive, and their mean is 91.7% of the mean source-matched gain. Policies trained on each of the three sources also produce similar positive CAD gains with no instance-level losses. The identical W/T/L counts across training sources further indicate consistent transfer to CAD. Together, these results show that relational failure cues transfer across contour distributions without requiring close contour matching. (a) Cross-source policy transfer Train \ Test ESICUP Synthetic Gardeyn ESICUP +0.96+0.96 +0.93+0.93 +0.63+0.63 Synthetic +0.80+0.80 +1.03+1.03 +0.61+0.61 Gardeyn +0.89+0.89 +0.89+0.89 +0.60+0.60 (b) Held-out industrial CAD transfer Train PS GeoNest Gain [95% CI] W/T/L ESICUP 79.78 80.39 +0.61[0.26,1.01]+0.61\,[0.26,1.01] 11/3/011/3/0 Synthetic 79.78 80.46 +0.68[0.32,1.19]+0.68\,[0.32,1.19] 11/3/011/3/0 Gardeyn 79.78 80.39 +0.61[0.26,1.08]+0.61\,[0.26,1.08] 11/3/011/3/0 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. Conclusion We formalized 2D-CIKP and introduced CircleNest-Bench for reproducible, verifier-backed evaluation. GeoNest treats unpacked items as evidence of residual pockets, explanatory poses, and blockers, then uses a relation-aware graph policy to select which fixed-item repair neighborhood to execute within the budget. Ablations show failure grounding drives most gains beyond Generic-LNS, while learned selection significantly outperforms random, fixed-score, and MLP selectors. Starting from PackingSolver incumbents, GeoNest consistently yields substantial utilization improvements under matched budgets. Notably, our approach achieves cross-budget efficiency, where shorter-budget configurations outperform the standalone solver under extended limits. Gains strengthen under higher packing pressure, and the learned policy transfers across unseen contour sources and held-out industrial CAD geometries. Together, the results show that late-stage packing is limited less by insufficient search than by failure diagnosis and repair allocation, positioning learning to direct expensive geometric computation rather than replacing it with pure neural approximations. The fixed-item repair contract enables this separation, allowing stronger compatible solvers to raise the backend ceiling while preserving the same failure-driven decision layer. References Abdou et al. (2026) K. Abdou, A. F. Ibrahim, K. Binder, and M. F. Huber Nest smarter, not harder: a hybrid vision-based deep reinforcement learning agent for packing 2D irregular geometries by rotational placement. Journal of Intelligent Manufacturing 37 (4), p. 1753–1767. External Links: Document Cited by: Learning-Guided Packing and Neighborhood Search. Atak et al. (2024) A. Atak, K. Buchin, M. Hagedoorn, J. Heinrichs, K. Hogreve, G. Li, and P. Pawelczyk Computing maximum polygonal packings in convex polygons using best-fit, genetic algorithms and ILPs (CG challenge). In 40th International Symposium on Computational Geometry (SoCG 2024), W. Mulzer and J. M. Phillips (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 293, Dagstuhl, Germany, p. 83:1–83:9. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Bennell and Oliveira (2008) J. A. Bennell and J. F. Oliveira The geometry of nesting problems: a tutorial. European Journal of Operational Research 184 (2), p. 397–415. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Bouzid and Salhi (2020) M. C. Bouzid and S. Salhi Packing rectangles into a fixed size circular container: constructive and metaheuristic search approaches. European Journal of Operational Research 285 (3), p. 865–883. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Burke et al. (2007) E. K. Burke, R. S. R. Hellier, G. Kendall, and G. Whitwell Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research 179 (1), p. 27–49. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. da Fonseca and Gerard (2024) G. D. da Fonseca and Y. Gerard Shadoks approach to knapsack polygonal packing (CG challenge). In 40th International Symposium on Computational Geometry (SoCG 2024), W. Mulzer and J. M. Phillips (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 293, Dagstuhl, Germany, p. 84:1–84:9. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems, Baselines.. ESICUP (2025) ESICUP Cutting & packing datasets. Note: https://github.com/ESICUP/datasetsEURO Special Interest Group on Cutting and Packing. Accessed: 2026-07-29 Cited by: CircleNest-Bench.. Fang et al. (2023) J. Fang, Y. Rao, X. Zhao, and B. Du A hybrid reinforcement learning algorithm for 2D irregular packing problems. Mathematics 11 (2). External Links: Document Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Fekete et al. (2024) S. P. Fekete, P. Keldenich, D. Krupke, and S. Schirra Maximum polygon packing: the CG:SHOP challenge 2024. External Links: 2403.16203, Link Cited by: Irregular Packing and Fixed-Container Problems. Fontan (2026) F. Fontan PackingSolver. Note: https://github.com/fontanf/packingsolverGitHub repository. Accessed: 2026-07-29 Cited by: Introduction, Baselines.. Gardeyn et al. (2025) J. Gardeyn, G. Vanden Berghe, and T. Wauters An open-source heuristic to reboot 2D nesting research. External Links: 2509.13329, Link Cited by: Irregular Packing and Fixed-Container Problems, CircleNest-Bench., Baselines.. Gomes and Oliveira (2006) A. M. Gomes and J. F. Oliveira Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research 171 (3), p. 811–829. External Links: Document Cited by: Introduction. Hottung and Tierney (2022) A. Hottung and K. Tierney Neural large neighborhood search for routing problems. Artificial Intelligence 313. External Links: Document Cited by: Learning-Guided Packing and Neighborhood Search. Huang et al. (2006) W. Huang, Y. Li, C. Li, and R. Xu New heuristics for packing unequal circles into a circular container. Computers & Operations Research 33 (8), p. 2125–2142. External Links: Document Cited by: Introduction. Johnn et al. (2024) S. Johnn, V. Darvariu, J. Handl, and J. Kalcsics A graph reinforcement learning framework for neural adaptive large neighbourhood search. Computers & Operations Research 172. External Links: Document Cited by: Learning-Guided Packing and Neighborhood Search. Lastra-Díaz and Ortuño (2024) J. J. Lastra-Díaz and M. T. Ortuño Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts. European Journal of Operational Research 313 (1), p. 69–91. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Leão et al. (2020) A. A. S. Leão, F. M. B. Toledo, J. F. Oliveira, M. A. Carravilla, and R. Alvarez-Valdés Irregular packing problems: a review of mathematical models. European Journal of Operational Research 282 (3), p. 803–822. External Links: Document Cited by: Introduction. Lee et al. (2008) W. Lee, H. Ma, and B. Cheng A heuristic for nesting problems of irregular shapes. Computer-Aided Design 40 (5), p. 625–633. External Links: Document Cited by: Introduction. López and Beasley (2016) C. O. López and J. E. Beasley A formulation space search heuristic for packing unequal circles in a fixed size circular container. European Journal of Operational Research 251 (1), p. 64–73. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. López and Beasley (2018) C. O. López and J. E. Beasley Packing unequal rectangles and squares in a fixed size circular container using formulation space search. Computers & Operations Research 94, p. 106–117. External Links: Document Cited by: Introduction. lryan599 (2025) lryan599 2DNesting: a 2d nesting/packing software. Note: https://github.com/lryan599/2DNestingGitHub repository. Accessed: 2026-07-29 Cited by: Baselines.. Ng et al. (1999) A. Y. Ng, D. Harada, and S. J. Russell Policy invariance under reward transformations: theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), San Francisco, CA, USA, p. 278–287. Cited by: Learning Objective. Nöl and Stricker (2011) T. Nöl and D. Stricker Efficient packing of arbitrary shaped charts for automatic texture atlas generation. Computer Graphics Forum 30 (4), p. 1309–1317. External Links: Document Cited by: Introduction. Pisinger and Ropke (2010) D. Pisinger and S. Ropke Large neighborhood search. In Handbook of Metaheuristics, M. Gendreau and J. Potvin (Eds.), International Series in Operations Research & Management Science, Vol. 146, p. 399–419. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Reijnen et al. (2024) R. Reijnen, Y. Zhang, H. C. Lau, and Z. Bukhsh Online control of adaptive large neighborhood search using deep reinforcement learning. In Proceedings of the 34th International Conference on Automated Planning and Scheduling (ICAPS 2024), S. Bernardini and C. Muise (Eds.), Vol. 34, p. 475–483. External Links: Document Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Ropke and Pisinger (2006) S. Ropke and D. Pisinger An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40 (4), p. 455–472. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Sato et al. (2019) A. K. Sato, T. C. Martins, A. M. Gomes, and M. S. G. Tsuzuki Raster penetration map applied to the irregular packing problem. European Journal of Operational Research 279 (2), p. 657–671. External Links: Document Cited by: Introduction. Schulman et al. (2016) J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel High-dimensional continuous control using generalized advantage estimation. In 4th International Conference on Learning Representations (ICLR 2016), External Links: Link Cited by: Learning Objective. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. External Links: 1707.06347 Cited by: Learning Objective. Song et al. (2020) J. Song, R. Lanka, Y. Yue, and B. Dilkina A general large neighborhood search framework for solving integer linear programs. In Advances in Neural Information Processing Systems, Vol. 33, p. 20012–20023. External Links: Link Cited by: Learning-Guided Packing and Neighborhood Search. Umetani and Murakami (2022) S. Umetani and S. Murakami Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes. European Journal of Operational Research 303 (3), p. 1009–1026. External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Wang et al. (2026a) J. Wang, K. Xu, and Z. Yang Large neighborhood search for the two-dimensional irregular bin packing problem. Note: Forthcoming in European Journal of Operational Research External Links: Document Cited by: Irregular Packing and Fixed-Container Problems. Wang et al. (2026b) Y. Wang, Q. Peng, Z. Wang, S. Huang, Z. Xu, C. Huang, and B. Guo Q-learning-based hyper-heuristic algorithm for open dimension irregular packing problems. Computers & Operations Research 185. External Links: Document Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Wu et al. (2021) Y. Wu, W. Song, Z. Cao, and J. Zhang Learning large neighborhood search policy for integer programming. In Advances in Neural Information Processing Systems, Vol. 34, p. 30075–30087. External Links: Link Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Xue et al. (2025) T. Xue, L. Lu, Y. Liu, M. Wu, H. Dong, Y. Zhang, R. Han, and B. Chen GFPack++: attention-driven gradient fields for optimizing 2D irregular packing. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), p. 18014–18023. External Links: Document, Link Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Xue et al. (2023) T. Xue, M. Wu, L. Lu, H. Wang, H. Dong, and B. Chen Learning gradient fields for scalable and generalizable irregular packing. In SIGGRAPH Asia 2023 Conference Papers, New York, NY, USA, p. 105:1–105:11. External Links: Document Cited by: Introduction, Learning-Guided Packing and Neighborhood Search. Yang et al. (2023) Z. Yang, Z. Pan, M. Li, K. Wu, and X. Gao Learning based 2D irregular shape packing. ACM Transactions on Graphics 42 (6), p. 1–16. External Links: Document Cited by: Learning-Guided Packing and Neighborhood Search.