PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.38863v1cs.LGcs.AI

TL;DR

Late-stage geometric packing can strand valuable polygons in fragmented residual pockets. GeoNest constructs and selects blocker-grounded repair neighborhoods, improving certified utilization over a geometry-based baseline on the benchmark.

  • Problem

    Late-stage geometric packing can leave valuable polygons unpacked as residual space fragments into inaccessible or incompatible pockets.

    Source: Introduction · p. 1

  • Method

    GeoNest pairs failed items with residual pockets, uses explanatory poses to identify blockers and compile fixed-item repair neighborhoods, then uses a masked GNN policy trained with PPO to rank actions.

    Source: Introduction · p. 2, Failure-Grounded Neighborhoods · p. 4

  • Results

    0.6% to 1.0%: GeoNest improves certified utilization over the strongest geometry-based baseline.

    Source: Introduction · p. 2

  • Takeaways & Limitations

    Failure grounding drives most gains beyond Generic-LNS, while learned selection outperforms random, fixed-score, and MLP selectors.

    Source: Conclusion · p. 7

    Gardeyn is the only source with an inconclusive cross-budget comparison, consistent with its more intricate concave polygons requiring a longer repair horizon.

    Source: Main Comparison under Matched Budgets · p. 6

Abstract

from arXiv · show

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.

Introduction

GeoNest addresses late-stage packing failures by using target–pocket geometry and identified blockers to construct repair neighborhoods, then learning which repair to execute. On CircleNest-Bench, it improves certified utilization over the strongest geometry-based baseline.

Introduction

  • The paper formalizes 2D-CIKP as subset selection and continuous placement in a fixed circular container, and introduces CircleNest-Bench with 2,391 load-controlled instances from four contour sources.The benchmark includes a held-out industrial CAD source.Source: Introduction · pp. 1–2
  • Prior learning-based packing approaches do not turn the interaction between an unpacked target and residual geometry into a targeted repair decision.GeoNest is presented as a failure-aware, learning-guided large-neighborhood search framework augmenting geometric solvers.Source: Introduction · p. 1
  • Late-stage packing can leave a valuable polygon unpacked even when total residual area exceeds its area, because fragmented pockets may block access or be incompatible.Pairing a failed target with a pocket exposes an explanatory pose and blockers, making repair-neighborhood selection the central late-stage decision.Source: Introduction · p. 1, Figure 1 · p. 1
  • GeoNest pairs unpacked targets with residual pockets, uses explanatory poses to identify blockers, and compiles fixed-item repair neighborhoods at multiple scales.A heterogeneous-graph policy trained with PPO ranks eligible actions; the geometric solver executes the selected repair with other pieces fixed.Source: Introduction · p. 2
  • 0.6% to 1.0%: GeoNest improves certified utilization over the strongest geometry-based baseline.Evaluation uses 2,391 load-controlled instances from four contour sources.Source: Introduction · p. 2

Related Work

Prior irregular-packing work covers general neighborhood search, irregular bin packing, and fixed-container formulations, including circular packing of regular objects. Learning-guided methods typically refine layouts or control general solver actions, whereas GeoNest selects repairs grounded in a failed target’s local geometry.

Irregular Packing and Fixed-Container Problems

  • The closest prior fixed-container formulation permits translations only in a convex polygonal container, whereas 2D-CIKP uses a circular container and continuous rotations.The paper identifies radial boundary effects and orientation-dependent pocket accessibility as central to subsequent insertions.Source: Irregular Packing and Fixed-Container… · p. 3

Learning-Guided Packing and Neighborhood Search

  • Prior learning-based packing methods optimize sequences, select low-level operators, or refine multiple poses; GeoNest instead acts after bounded geometric search without predicting placement coordinates or rotations.The policy uses unpacked items as failure targets.Source: Learning-Guided Packing and… · p. 3
  • Learned large-neighborhood-search methods control neighborhoods, repair heuristics, or operators, while GeoNest ranks repair actions built from the current failed target and its local geometric context.The actions are not global operators or generic subsets of solver variables.Source: Learning-Guided Packing and… · p. 3

Problem Formulation and Benchmark

2D-CIKP selects polygonal items and assigns continuous poses inside a fixed circular container, subject to containment and non-overlap. CircleNest-Bench provides load-controlled instances across contour sources, evaluates held-out settings, and counts only verifier-certified layouts.

Problem Formulation and Benchmark

  • 2D-CIKP selects a subset of candidate polygons and assigns continuous translations and rotations to maximize packed area in a fixed disk, subject to containment and non-overlap.Boundary contact is allowed, and the candidate area exceeds the disk area in CircleNest-Bench, making subset selection necessary.Source: Problem Formulation and Benchmark · p. 3
  • CircleNest-Bench contains 2,391 load-controlled instances from ESICUP, synthetic, Gardeyn, and held-out industrial geometry sources.The industrial contours are held out from training and validation.Source: Problem Formulation and Benchmark · p. 3, Table 1 · p. 3
  • The Main partitions span item counts of 48, 64, and 96 and loads of 1.2, 1.5, and 2.0; additional splits test size extrapolation, overload stress, and 14 industrial instances.The held-out size/load combination is n = 128 and λ = 2.5; industrial tests use n = 100 and λ = 1.5.Source: Problem Formulation and Benchmark · p. 4
  • A common verifier checks item identities, disk containment, and pairwise non-overlap, recomputes utilization, and assigns invalid layouts zero.Verifier-certified utilization is the primary metric.Source: Problem Formulation and Benchmark · p. 4

Method

GeoNest starts from a feasible layout and uses a graph policy to select bounded repair neighborhoods grounded in unpacked targets, residual pockets, and their blockers. The solver repairs selected neighborhoods, while verification and a shaped learning objective guide sequential decisions.

Method

  • GeoNest pairs unpacked targets with residual pockets and uses a graph policy to rank solver calls under a takeover budget.The process starts from a feasible layout produced by bounded search.Source: Method · p. 4

Failure-Grounded Neighborhoods

  • Explanatory poses diagnose blockers; bounded neighborhoods vary the released items and admitted targets, with modes expanding the release set and repair caps tied to neighborhood scale and remaining budget.Target–pocket compatibility combines area ratio with bounding-box fit; retained explanatory poses reward pocket coverage and penalize blocked area, blocker count, and radial displacement.Source: Failure-Grounded Neighborhoods · p. 4

Graph Policy

  • A heterogeneous graph encodes targets, pockets, blockers, actions, and search context; a masked GNN policy trained with PPO ranks eligible actions using learned logits and a fixed geometric score.Training samples from the policy, while inference selects its maximizer.Source: Graph Policy · p. 5

Fixed-Item Repair and Verification

  • PackingSolver searches movable items while other pieces remain fixed, and a common true-disk verifier checks candidates before they can update the certified best layout.The best layout’s utility never decreases; equal-utility candidates may update the search context under a bounded plateau rule.Source: Fixed-Item Repair and Verification · p. 5

Learning Objective

  • The sequential learning objective balances immediate certified improvement, repair cost, and downstream packability through potential-based shaping, event feedback, and terminal credit.The fixed potential scores promising states using unresolved-item burden, residual placeability, and layout quality.Source: Learning Objective · p. 5

Experiments

Under matched budgets, GeoNest improves verifier-certified utilization over PackingSolver across the three main sources, with gains persisting at 1200 s. The experiments also examine selector contributions, scale and load robustness, and transfer to held-out industrial CAD.

Experimental Setup

  • The protocol tests held-out partitions with matched wall-clock budgets and full-range orientation search; GeoNest divides time between PackingSolver initialization and takeover.At 650 s the split is 350 s/300 s; at 1200 s it is 600 s/600 s, and takeover bookkeeping and verification count toward its budget.Source: Experimental Setup · pp. 5–6

Main Comparison under Matched Budgets

  • GeoNest gains over PackingSolver across all three sources under matched 650-s budgets, with paired 95% confidence intervals excluding zero.PackingSolver's Main Avg. utilization is 78.37%; Table 2 reports verifier-certified utilization.Source: Table 2 · p. 6, Main Comparison under Matched Budgets · p. 6
  • Using 45.8% less time, 650-s GeoNest exceeds 1200-s PackingSolver by 0.46 pp; its 1200-s matched-budget gain retains 88.5% of its 650-s gain.Gardeyn is the only source with an inconclusive cross-budget comparison; the authors associate its geometry with complex pockets and blocker relations.Source: Main Comparison under Matched Budgets · p. 6, Table 3 · p. 6

Ablation and Generalization

  • Failure-aware actions account for most gains beyond Generic-LNS, and GeoNest significantly outperforms Random, Score, and MLP selectors.The selector comparison holds action generation and repair execution constant; Table 4(b) compares selectors under that shared procedure.Source: Ablation and Generalization · p. 6, Table 4 · p. 7
  • In an 18-state one-step audit, the GNN chose the best immediate repair in 61.1% of cases and exceeded the mean candidate-action gain.All candidate actions were evaluated in the audited states.Source: Ablation and Generalization · p. 7
  • Gain decreases with item count but increases with packing pressure, which magnifies the impact of blockers and residual pockets.The authors attribute the size trend to a fixed repair budget being spread across more candidate neighborhoods.Source: Ablation and Generalization · p. 7
  • Stress yields 3.2 times the mean gain of Size despite similar win rates, indicating that packing pressure affects improvement magnitude more than win frequency.The held-out shifts reinforce the scale-and-load pattern.Source: Ablation and Generalization · p. 7
  • All six off-diagonal transfer gains are positive and average 91.7% of source-matched gains; policies trained on each non-CAD source also produce similar positive CAD gains with no instance-level losses.These results support transfer across contour distributions without close contour matching.Source: Ablation and Generalization · p. 7, Table 6 · p. 7

Conclusion

GeoNest improves utilization under matched budgets and shows cross-budget efficiency, with gains strengthening under higher packing pressure and transferring to unseen contour sources. The results support directing geometric computation through failure diagnosis and repair allocation.

Conclusion

  • Starting from PackingSolver incumbents, GeoNest consistently yields substantial utilization improvements under matched budgets.Source: Conclusion · p. 7
  • GeoNest uses unpacked items to identify residual pockets, explanatory poses, and blockers, then selects fixed-item repair neighborhoods with a relation-aware graph policy.Source: Conclusion · p. 7
  • Ablations show failure grounding drives most gains beyond Generic-LNS, while learned selection significantly outperforms random, fixed-score, and MLP selectors.Source: Conclusion · p. 7
  • Shorter-budget GeoNest configurations outperform the standalone solver under extended limits, demonstrating cross-budget efficiency.Source: Conclusion · p. 7
  • Gains strengthen under higher packing pressure, and the learned policy transfers across unseen contour sources and held-out industrial CAD geometries.Source: Conclusion · p. 7
  • The paper formalizes 2D-CIKP and introduces CircleNest-Bench for reproducible, verifier-backed evaluation.Source: Conclusion · p. 7
Loading 2609.38863v1…