一维装箱问题中物品兼容性图的深度强化学习

# Deep Reinforcement Learning on Item-Compatibility Graphsfor One-Dimensional Bin Packing
Source: [https://arxiv.org/html/2609.25397](https://arxiv.org/html/2609.25397)
M\. Aslı AydınEmail:[asli\.aydin@bau\.edu\.tr](mailto:[email protected])Corresponding author:Corresponding author\.Affiliation:Department of Management Engineering, Bahçeşehir University, Istanbul, Türkiye

###### Abstract

The one\-dimensional bin packing problem \(1D\-BPP\) is a classical NP\-hard combinatorial optimization problem with applications ranging from logistics and manufacturing to cloud resource management\. Although deep reinforcement learning \(DRL\) has become a competitive paradigm for data\-driven optimization, most learned packing methods target 2D and 3D variants, and intelligent learned solvers for 1D\-BPP remain scarce\. In this paper, we present a novel end\-to\-end, size\-agnostic graph reinforcement learning framework for 1D\-BPP\. We formulate the packing process as a Markov decision process on an item\-compatibility graph, serving as a structural knowledge representation in which every action merges two partial bins that fit together\. A graph neural network actor–critic policy extracts relational features from this representation and is trained through reinforcement learning and decoded by stochastic beam search, enabling a single trained model to generalize zero\-shot to instances of any size\. We conduct a systematic empirical study across graph encoders, DRL algorithms, reward functions, training distributions, and hyperparameters\. Evaluated zero\-shot on the full BPPLIB benchmark against a constructive heuristic, a grouping genetic algorithm, and recent learned methods, our data\-driven policy lowers the mean optimality gap of the constructive heuristic from 2\.66% to 2\.31%, with the largest gains on structured instances\. Against learned baselines evaluated on the same benchmark, it attains a lower gap on most of the nine families and is far more stable across instance distributions\. On the hardest benchmark family, it outperforms a state\-of\-the\-art learned solver that relies on column generation and integer programming, while using no solver at all\. A grouping genetic algorithm remains ahead overall, and we analyze where and why the residual gap arises\.

###### Keywords:

Bin packing , Deep reinforcement learning , Graph neural networks , Combinatorial optimization , Item\-compatibility graph

## 1Introduction

The one\-dimensional bin packing problem \(1D\-BPP\) asks for the assignment ofnnitems with known weightsw1,…,wnw\_\{1\},\\dots,w\_\{n\}to the smallest possible number of identical bins of capacityCCsuch that the total weight in every bin does not exceedCC\[[1](https://arxiv.org/html/2609.25397#bib.bib1)\]\. Despite its simple statement, 1D\-BPP is the core formulation behind a wide range of industrial decisions\. In freight transportation and supply\-chain management it models the cargo loading onto the fewest possible trucks or containers\[[2](https://arxiv.org/html/2609.25397#bib.bib2),[1](https://arxiv.org/html/2609.25397#bib.bib1)\]\. In manufacturing it coincides with the unit\-demand one\-dimensional cutting stock problem \(CSP\), which governs the cutting of steel bars, paper rolls or glass tubes with minimum trim loss\[[3](https://arxiv.org/html/2609.25397#bib.bib3),[4](https://arxiv.org/html/2609.25397#bib.bib4)\]\. In information technology it underlies virtual machine placement and server consolidation in data centres\[[5](https://arxiv.org/html/2609.25397#bib.bib5),[6](https://arxiv.org/html/2609.25397#bib.bib6)\]\. The problem also continues to attract methodological work in operations research, including recent exact approaches to variants that couple packing with scheduling objectives\[[7](https://arxiv.org/html/2609.25397#bib.bib7)\]\.

1D\-BPP is NP\-hard\[[8](https://arxiv.org/html/2609.25397#bib.bib8)\]\. Exact methods such as branch\-and\-price, arc\-flow formulations and the BISON procedure\[[9](https://arxiv.org/html/2609.25397#bib.bib9),[10](https://arxiv.org/html/2609.25397#bib.bib10),[3](https://arxiv.org/html/2609.25397#bib.bib3)\]solve moderate instances to proven optimality but struggle on large or structurally hard instances\[[11](https://arxiv.org/html/2609.25397#bib.bib11)\]\. In this case, practitioners often use fast constructive heuristics, most notably First\-Fit Decreasing \(FFD\) and Best\-Fit Decreasing \(BFD\)\. The idea is to sort the items in non\-increasing order first and then place each item into the first or the tightest feasible bin\[[12](https://arxiv.org/html/2609.25397#bib.bib12),[1](https://arxiv.org/html/2609.25397#bib.bib1),[13](https://arxiv.org/html/2609.25397#bib.bib13),[14](https://arxiv.org/html/2609.25397#bib.bib14)\]\. Their worst\-case guarantees are well established\[[15](https://arxiv.org/html/2609.25397#bib.bib15)\]and on many benchmark instances FFD is within a fraction of a bin of the optimum\. Where higher quality is required, metaheuristics ranging from local search and simulated annealing to grouping genetic algorithms search the combinatorial space and close most of the remaining gap\[[16](https://arxiv.org/html/2609.25397#bib.bib16),[17](https://arxiv.org/html/2609.25397#bib.bib17),[18](https://arxiv.org/html/2609.25397#bib.bib18)\]\. However, metaheuristics are comparatively expensive\. They depend on hand\-crafted problem\-specific operators, and solve every new instance from scratch without retaining any transferable knowledge\.

Over the past decade, deep reinforcement learning \(DRL\) and neural combinatorial optimization have emerged as a data\-driven alternative\[[19](https://arxiv.org/html/2609.25397#bib.bib19),[20](https://arxiv.org/html/2609.25397#bib.bib20),[21](https://arxiv.org/html/2609.25397#bib.bib21)\]\. Pointer networks, graph neural networks \(GNNs\) and attention models achieve competitive results on routing problems such as the travelling salesman and vehicle routing problems\[[22](https://arxiv.org/html/2609.25397#bib.bib22),[23](https://arxiv.org/html/2609.25397#bib.bib23),[24](https://arxiv.org/html/2609.25397#bib.bib24),[25](https://arxiv.org/html/2609.25397#bib.bib25),[26](https://arxiv.org/html/2609.25397#bib.bib26)\]\. In packing, learned methods have focused almost exclusively on two\- and three\-dimensional variants\[[27](https://arxiv.org/html/2609.25397#bib.bib27),[28](https://arxiv.org/html/2609.25397#bib.bib28),[29](https://arxiv.org/html/2609.25397#bib.bib29)\], where spatial layouts offer natural inductive biases and classical heuristics leave substantial room for improvement\.

End\-to\-end learning for 1D\-BPP, in contrast, has received little attention\[[30](https://arxiv.org/html/2609.25397#bib.bib30),[31](https://arxiv.org/html/2609.25397#bib.bib31),[32](https://arxiv.org/html/2609.25397#bib.bib32)\]\. There are two main reasons for this\. First, a 1D instance is just a set of numbers with no coordinates or adjacency\. So sequence models must cope with permutation invariance and dynamic capacity constraints without any spatial prior\. Second, because FFD is already near\-optimal on average, a learned policy risks collapsing to a sorting rule unless it discovers non\-myopic item combinations\. Hence, some existing methods train a network to predict only an item*ordering*and leave placement to a heuristic\[[33](https://arxiv.org/html/2609.25397#bib.bib33),[34](https://arxiv.org/html/2609.25397#bib.bib34)\]\. Some other method embeds a bipartite GNN inside a column\-generation loop that solves linear and integer programs at every inference step\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]\.

This paper asks whether a pure, end\-to\-end graph DRL solver can learn high\-quality packing policies for 1D\-BPP\. We propose a framework that first turns a 1D\-BPP instance into an*item\-compatibility graph*\[[36](https://arxiv.org/html/2609.25397#bib.bib36)\]whose nodes are \(partial\) bins and whose edges join pairs whose combined load fits into one bin\. Then packing becomes a sequential edge\-merge Markov decision process \(MDP\) where each action contracts one edge, and the episode ends when no compatible pair remains\. Every node is described only by ratios, its relative load and its normalized degree\. The network scores each candidate merge from the two nodes it joins and summarizes the whole graph by averaging over its nodes\. Hence no part of the model depends on how many items an instance contains\. A single trained policy therefore transfers zero\-shot to instance sizes and families never seen during training\.

Beyond its algorithmic performance, the proposed end\-to\-end framework connects classical combinatorial optimization with modern intelligent decision support systems\. Casting 1D\-BPP onto an item\-compatibility graph provides a structural knowledge representation of the combinatorial space\. On this representation the graph neural network extracts relational knowledge about feasible item combinations and learns a data\-driven optimization policy without hand\-crafted heuristic rules\. The trained size\-agnostic model can therefore serve as an adaptable decision component within intelligent decision support systems in which packing decisions recur at scale and must be made without a solver in the loop\.

The contributions of this paper are as follows\.

- 1\.We define 1D\-BPP as an MDP on an item\-compatibility graph with a size\-invariant state representation whose return is objective\-equivalent to the bin count\.
- 2\.We develop an end\-to\-end, size\-agnostic graph reinforcement learning framework\. By utilizing relative capacity and topological degree features, the model achieves strong zero\-shot generalization to unseen problem scales\.
- 3\.We compare three graph encoders \(GCN, GAT, GIN\) and six RL algorithms \(PPO, A2C, REINFORCE, DQN, SAC, SARSA\) selecting all design choices on in\-distribution validation data rather than on the benchmark\.
- 4\.We evaluate a single uniform\-trained model on all complete BPPLIB families against FFD, a grouping genetic algorithm and recent learned solvers on the identical benchmark and metric\. We analyse where the learned policy helps, where it does not, and why\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2609.25397#S2)reviews classical, metaheuristic and learning\-based approaches to 1D\-BPP\. Section[3](https://arxiv.org/html/2609.25397#S3)states the problem formally and introduces the item\-compatibility graph\. Section[4](https://arxiv.org/html/2609.25397#S4)presents the MDP, the DRL architecture, and the training and decoding procedures\. Section[5](https://arxiv.org/html/2609.25397#S5)describes the computational experiments and reports the results\. Section[6](https://arxiv.org/html/2609.25397#S6)discusses their implications and Section[7](https://arxiv.org/html/2609.25397#S7)concludes with limitations and future work\.

## 2Related work

### 2\.1Exact and heuristic methods

The study of bin packing and cutting stock problems originates with Kantorovich’s production\-planning formulation\[[37](https://arxiv.org/html/2609.25397#bib.bib37)\]and the delayed column generation of Gilmore and Gomory\[[38](https://arxiv.org/html/2609.25397#bib.bib38)\]\. Dyckhoff\[[39](https://arxiv.org/html/2609.25397#bib.bib39)\]and Wäscher et al\.\[[4](https://arxiv.org/html/2609.25397#bib.bib4)\]established the standard typologies of cutting and packing problems, and Martello and Toth\[[1](https://arxiv.org/html/2609.25397#bib.bib1)\]provided the reference integer programming models, lower bounds and branch\-and\-bound algorithms\. Modern exact solvers include the arc\-flow formulation of Valério de Carvalho\[[10](https://arxiv.org/html/2609.25397#bib.bib10),[40](https://arxiv.org/html/2609.25397#bib.bib40)\]and the BISON procedure of Scholl et al\.\[[9](https://arxiv.org/html/2609.25397#bib.bib9)\]\. Delorme et al\.\[[3](https://arxiv.org/html/2609.25397#bib.bib3),[11](https://arxiv.org/html/2609.25397#bib.bib11)\]surveyed mathematical models and instances in the BPPLIB library, which we use as the test bed\. Exact methods solve moderate instances efficiently but their effort grows sharply on instances with tight capacity structure\. For real\-time use, constructive heuristics remain the practical standard\. FFD and BFD\[[12](https://arxiv.org/html/2609.25397#bib.bib12)\]admit tight worst\-case bounds\[[15](https://arxiv.org/html/2609.25397#bib.bib15),[13](https://arxiv.org/html/2609.25397#bib.bib13)\], and have been refined by later constructive schemes\[[14](https://arxiv.org/html/2609.25397#bib.bib14)\]\.

### 2\.2Grouping metaheuristics

When constructive heuristics leave an unacceptable residual gap and exact solvers are too slow, metaheuristics search the solution space directly\. Early studies applied simulated annealing and tabu search\[[18](https://arxiv.org/html/2609.25397#bib.bib18)\]\. But item\-level encodings suffer from the fact that moving single items between bins frequently violates capacity\. Falkenauer’s Grouping Genetic Algorithm \(GGA\) and its hybrid variant HGGA\[[16](https://arxiv.org/html/2609.25397#bib.bib16)\]instead manipulate whole bins with group\-level crossover and mutation, and remain the standard high\-quality reference for 1D\-BPP\. Later work developed parallel and cooperative grouping metaheuristics\[[17](https://arxiv.org/html/2609.25397#bib.bib17)\]and hybrid evolutionary schemes\[[18](https://arxiv.org/html/2609.25397#bib.bib18),[41](https://arxiv.org/html/2609.25397#bib.bib41)\]\. However, metaheuristics offer no quality or convergence guarantees and are comparatively expensive\. They are also memoryless, meaning that nothing learned on one instance transfers to the next\.

### 2\.3Learning\-based methods for bin packing

These limitations, together with the success of DRL on hard sequential decision problems\[[42](https://arxiv.org/html/2609.25397#bib.bib42)\], have motivated a line of work often called neural combinatorial optimization\. Instead of relying on hand\-designed rules, it learns solution policies for combinatorial problems directly from data\[[19](https://arxiv.org/html/2609.25397#bib.bib19),[20](https://arxiv.org/html/2609.25397#bib.bib20)\]\. Pointer networks\[[22](https://arxiv.org/html/2609.25397#bib.bib22),[43](https://arxiv.org/html/2609.25397#bib.bib43)\], policy\-gradient training\[[23](https://arxiv.org/html/2609.25397#bib.bib23)\], structure\-to\-vector GNNs\[[24](https://arxiv.org/html/2609.25397#bib.bib24)\]and attention models\[[25](https://arxiv.org/html/2609.25397#bib.bib25),[26](https://arxiv.org/html/2609.25397#bib.bib26)\]produce high\-quality solutions on routing problems, which are naturally defined on graphs\. In bin packing, learned solvers have concentrated on 2D and 3D variants and on strip packing\[[27](https://arxiv.org/html/2609.25397#bib.bib27),[28](https://arxiv.org/html/2609.25397#bib.bib28),[29](https://arxiv.org/html/2609.25397#bib.bib29),[30](https://arxiv.org/html/2609.25397#bib.bib30)\], where spatial layouts create geometric sub\-problems that heuristics handle poorly\. Recent surveys of learning\-based methods for bin packing make the same observation\[[30](https://arxiv.org/html/2609.25397#bib.bib30),[32](https://arxiv.org/html/2609.25397#bib.bib32),[31](https://arxiv.org/html/2609.25397#bib.bib31)\]\. Almost all of the effort has gone into the multi\-dimensional variants, and the one\-dimensional problem has attracted very little of it\. The few 1D approaches are not end\-to\-end constructors\. Instead, they learn an item ordering for a heuristic decoder\[[33](https://arxiv.org/html/2609.25397#bib.bib33),[34](https://arxiv.org/html/2609.25397#bib.bib34)\], or combine a bipartite graph convolutional network with column generation and integer programming so that linear and integer programs are solved at every inference step\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]\.

### 2\.4Graph representations of 1D\-BPP

Applying a GNN policy to 1D\-BPP requires projecting weights and capacities onto an explicit graph\. The arc\-flow network\[[10](https://arxiv.org/html/2609.25397#bib.bib10)\]is one option, but its nodes index integer capacity levels, so its size scales withCCand its action semantics are awkward for a stationary sequential decision process\. The item\-compatibility graph\[[36](https://arxiv.org/html/2609.25397#bib.bib36)\]instead places one node per item \(or partial bin\) and joins two nodes whenever their combined load fits into a bin\. Its edge set is exactly the set of feasible pairwise merges, and a merge updates the graph locally, which makes it a natural state space for reinforcement learning\.

Our work differs from prior learned 1D\-BPP methods in two respects\. First, the MDP is defined directly on the item\-compatibility graph with a size\-independent state, so one trained policy applies to instances of any size\. Second, every packing decision is produced by the learned policy rather than by a heuristic placement rule\[[33](https://arxiv.org/html/2609.25397#bib.bib33)\]or by a mathematical programming loop\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]\. We evaluate this design on the complete BPPLIB benchmark to establish where learned constructive policies succeed and where their limits lie relative to constructive heuristics, grouping metaheuristics and existing learned solvers\.

## 3Problem definition

### 3\.1One\-dimensional bin packing problem

An instance of 1D\-BPP is a pair\(W,C\)\(W,C\), whereW=\{w1,…,wn\}W=\\\{w\_\{1\},\\dots,w\_\{n\}\\\}is a set ofnnitems with integer weights0<wi≤C0<w\_\{i\}\\leq CandCCis the common capacity of an unlimited supply of identical bins\. A packing assigns every item to exactly one bin such that the total weight in every bin is at mostCCand the objective is to minimize the number of bins used\. With binary variablesyky\_\{k\}\(binkkis used\) andxi​kx\_\{ik\}\(itemiiis placed in binkk\), fork∈\{1,…,n\}k\\in\\\{1,\\dots,n\\\}, the integer programming formulation of 1D\-BPP is\[[1](https://arxiv.org/html/2609.25397#bib.bib1)\]

min\\displaystyle\\min\\∑k=1nyk\\displaystyle\\sum\_\{k=1\}^\{n\}y\_\{k\}\(1\)s\.t\.∑k=1nxi​k=1,\\displaystyle\\sum\_\{k=1\}^\{n\}x\_\{ik\}=1,i=1,…,n,\\displaystyle i=1,\\dots,n,\(2\)∑i=1nwi​xi​k≤C​yk,\\displaystyle\\sum\_\{i=1\}^\{n\}w\_\{i\}x\_\{ik\}\\leq C\\,y\_\{k\},k=1,…,n,\\displaystyle k=1,\\dots,n,\(3\)xi​k,yk∈\{0,1\},\\displaystyle x\_\{ik\},\\,y\_\{k\}\\in\\\{0,1\\\},i,k=1,…,n\.\\displaystyle i,k=1,\\dots,n\.\(4\)The continuous relaxation of \([1](https://arxiv.org/html/2609.25397#S3.E1)\)–\([4](https://arxiv.org/html/2609.25397#S3.E4)\) yields the trivial lower boundL1=⌈∑iwi/C⌉L\_\{1\}=\\lceil\\sum\_\{i\}w\_\{i\}/C\\rceil\.

### 3\.2Item\-compatibility graph

An instance\(W,C\)\(W,C\)has no graph structure of its own\. Following\[[36](https://arxiv.org/html/2609.25397#bib.bib36)\], we build the*item\-compatibility graph*of the instance as an undirected graphG=\(V,E\)G=\(V,E\)where

V=\{1,…,n\},E=\{\(i,j\):i<j,wi\+wj≤C\}\.V=\\\{1,\\dots,n\\\},\\qquad E=\\\{\(i,j\)\\,:\\,i<j,\\ w\_\{i\}\+w\_\{j\}\\leq C\\\}\.\(5\)An edge between two vertices indicates that the two items may share a bin\. A packing corresponds to a partition ofVVinto vertex setsS1,…,SbS\_\{1\},\\dots,S\_\{b\}such that everySkS\_\{k\}is a clique ofGGand∑i∈Skwi≤C\\sum\_\{i\\in S\_\{k\}\}w\_\{i\}\\leq C\. Minimizing the number of bins used therefore reduces to a capacity\-constrained minimum clique partition ofGG\.

##### Illustrative example

Figure[1](https://arxiv.org/html/2609.25397#S3.F1)shows how the item\-compatibility graph is constructed for a small sample instance withn=5n=5items,W=\{1,2,4,5,9\}W=\\\{1,2,4,5,9\\\}andC=11C=11\. The eight edgesk1,…,k8k\_\{1\},\\dots,k\_\{8\}of the resulting graph denote the pairs of items whose weights sum to at most 11\.

d1d\_\{1\}w1=1w\_\{1\}=1d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d4d\_\{4\}w4=5w\_\{4\}=5d5d\_\{5\}w5=9w\_\{5\}=9\(a\)d1d\_\{1\}w1=1w\_\{1\}=1d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d4d\_\{4\}w4=5w\_\{4\}=5d5d\_\{5\}w5=9w\_\{5\}=9k1k\_\{1\}k2k\_\{2\}k3k\_\{3\}k4k\_\{4\}k5k\_\{5\}k6k\_\{6\}k7k\_\{7\}k8k\_\{8\}\(b\)

Figure 1:Item\-compatibility graph of a five\-item instance withC=11C=11\. \(a\) Items as isolated nodes\. \(b\) Edges join pairs whose combined weight does not exceedCC\.

## 4Methods

### 4\.1MDP formulation

We model packing as a deterministic, episodic MDP\(𝒮,𝒜,T,R\)\(\\mathcal\{S\},\\mathcal\{A\},T,R\)in which every step contracts one edge of the current graph\.

##### State

The state at stepttis the graphGt=\(Vt,Et\)G\_\{t\}=\(V\_\{t\},E\_\{t\}\)whose nodes are the current partial bins\. Nodeiicarries a loadℓi\\ell\_\{i\}, initialized towiw\_\{i\}, and two nodes are adjacent while their combined load fits into a bin,\(i,j\)∈Et⇔ℓi\+ℓj≤C\(i,j\)\\in E\_\{t\}\\iff\\ell\_\{i\}\+\\ell\_\{j\}\\leq C\. HenceG0G\_\{0\}is the item\-compatibility graph \([5](https://arxiv.org/html/2609.25397#S3.E5)\)\. Each node is described by the two\-dimensional feature vector

xi=\[ℓiC,degt⁡\(i\)maxk∈Vt⁡degt⁡\(k\)\],x\_\{i\}=\\Big\[\\ \\frac\{\\ell\_\{i\}\}\{C\},\\ \\ \\frac\{\\deg\_\{t\}\(i\)\}\{\\max\_\{k\\in V\_\{t\}\}\\deg\_\{t\}\(k\)\}\\ \\Big\],\(6\)i\.e\. its relative load and its degree normalized by the largest degree inGtG\_\{t\}\. Both entries are ratios in\[0,1\]\[0,1\], which makes the representation independent ofnnand of the absolute scale ofCC\. The normalized degree measures how many merge options a node still has\. A node with a high value fits with almost everything and can wait, while a node with a low value has only a few compatible partners left and risks ending up as a bin on its own\.

##### Action

The action set is the current edge set,𝒜⁡\(st\)=Et\\mathcal\{A\}\(s\_\{t\}\)=E\_\{t\}\. Choosingat=\(i,j\)a\_\{t\}=\(i,j\)merges the two endpoints into a single node of loadℓi\+ℓj\\ell\_\{i\}\+\\ell\_\{j\}, i\.e\. it packs the two partial bins together\. Feasibility is guaranteed by construction, so no masking or penalty for infeasible actions is required\.

##### Transition

Transitions are deterministic\. The merged node replaces its two endpoints\. Its incident edges are recomputed from the new load, so that any edge that would now violate the capacity is removed\. Since exactly one node disappears per step, an episode has at mostn−1n\-1steps and the number of bins at termination equalsnnminus the number of merges\.

##### Reward

We use a per\-step rewardR⁡\(st,at\)=\+1R\(s\_\{t\},a\_\{t\}\)=\+1for every merge and00at termination, so the return of an episode is the number of merges\. Since the number of bins used equalsnnminus the total number of merges, maximizing the cumulative reward \(the total number of merges\) is equivalent to minimizing the number of bins used\. We define and compare two alternative reward designs in Section[5\.7\.1](https://arxiv.org/html/2609.25397#S5.SS7.SSS1)\.

##### Terminal state

An episode ends whenEt=∅E\_\{t\}=\\varnothing, i\.e\. no two remaining bins can be combined\. At that point every node of the graph is a bin of the final packing, the items it contains are the original items merged into it, and the number of remaining nodes is the objective value of the solution\.

##### Illustrative example \(continued\)

Figure[2](https://arxiv.org/html/2609.25397#S4.F2)traces one episode of the MDP on the five\-item instance of Figure[1](https://arxiv.org/html/2609.25397#S3.F1)\. The initial states0s\_\{0\}\(Figure[2](https://arxiv.org/html/2609.25397#S4.F2)a\) is the item\-compatibility graph itself, so all eight edges are available as actions\. Suppose the policy selectsa0=k7a\_\{0\}=k\_\{7\}\(Figure[2](https://arxiv.org/html/2609.25397#S4.F2)b\), the edge betweend1d\_\{1\}andd4d\_\{4\}\. The two items, of weights 1 and 5, are merged into a new noded6d\_\{6\}of load 6, and the edges ofd6d\_\{6\}are recomputed from this load\. Onlyd2d\_\{2\}andd3d\_\{3\}still fit together withd6d\_\{6\}, whereasd5d\_\{5\}does not \(Figure[2](https://arxiv.org/html/2609.25397#S4.F2)c\)\. The policy next selectsa1=k3a\_\{1\}=k\_\{3\}\(Figure[2](https://arxiv.org/html/2609.25397#S4.F2)d\) and merges the item of weight 2 intod6d\_\{6\}, producingd7d\_\{7\}of load 8\. Now no two remaining nodes fit together, since every pairwise sum exceeds the capacity\. The episode ends in the terminal statesTs\_\{T\}with the three isolated nodesd3d\_\{3\},d5d\_\{5\}andd7d\_\{7\}\(Figure[2](https://arxiv.org/html/2609.25397#S4.F2)e\), which are the three bins of the solution,\{4\}\\\{4\\\},\{9\}\\\{9\\\}and\{1,5,2\}\\\{1,5,2\\\}\. Two merges were made, so the return is11and the number of bins is5−2=35\-2=3\. This solution is not optimal\. Selectingk1k\_\{1\}first \(items 2 and 9\) and then packing items 1, 4 and 5 together reaches the optimum of two bins, which shows that the order of merges matters and is exactly what the policy has to learn\.

d1d\_\{1\}w1=1w\_\{1\}=1d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d4d\_\{4\}w4=5w\_\{4\}=5d5d\_\{5\}w5=9w\_\{5\}=9k1k\_\{1\}k2k\_\{2\}k3k\_\{3\}k4k\_\{4\}k5k\_\{5\}k6k\_\{6\}k7k\_\{7\}k8k\_\{8\}\(a\) Initial states0s\_\{0\}d1d\_\{1\}w1=1w\_\{1\}=1d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d4d\_\{4\}w4=5w\_\{4\}=5d5d\_\{5\}w5=9w\_\{5\}=9k1k\_\{1\}k2k\_\{2\}k3k\_\{3\}k4k\_\{4\}k5k\_\{5\}k6k\_\{6\}k7k\_\{7\}k8k\_\{8\}\(b\) Actiona0=k7a\_\{0\}=k\_\{7\}d6d\_\{6\}ℓ6=6\\ell\_\{6\}=6d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d5d\_\{5\}w5=9w\_\{5\}=9k1k\_\{1\}k3k\_\{3\}k5k\_\{5\}k6k\_\{6\}\(c\) States1s\_\{1\}d6d\_\{6\}ℓ6=6\\ell\_\{6\}=6d2d\_\{2\}w2=2w\_\{2\}=2d3d\_\{3\}w3=4w\_\{3\}=4d5d\_\{5\}w5=9w\_\{5\}=9k1k\_\{1\}k3k\_\{3\}k5k\_\{5\}k6k\_\{6\}\(d\) Actiona1=k3a\_\{1\}=k\_\{3\}d7d\_\{7\}ℓ7=8\\ell\_\{7\}=8d3d\_\{3\}w3=4w\_\{3\}=4d5d\_\{5\}w5=9w\_\{5\}=9\(e\) Terminal statesTs\_\{T\}

Figure 2:One episode of the MDP on the example instance\. \(a\) Initial state\. \(b\) Selection ofa0a\_\{0\}\. \(c\) Graph after the first merge; edges of the new node are recomputed from its load\. \(d\) Selection ofa1a\_\{1\}\. \(e\) Terminal state with three isolated nodes, i\.e\. three bins\.

### 4\.2DRL architecture

Compatibility graphGtG\_\{t\}node featuresxi=\[ℓi/C,degt⁡\(i\)/degmax\]x\_\{i\}=\[\\ell\_\{i\}/C,\\ \\deg\_\{t\}\(i\)/\\deg\_\{\\max\}\]Linear2→d2\\to dL=3L\{=\}3GNN layers\(GCN\|\|GAT\|\|GIN\)residual \+ LayerNormnode embeddingshi∈ℝdh\_\{i\}\\in\\mathbb\{R\}^\{d\},d=128d=128Edge readouth\(i,j\)=\[hi∥hj\]h\_\{\(i,j\)\}=\[h\_\{i\}\\,\\\|\\,h\_\{j\}\]Mean poolinghs=1\|Vt\|​∑ihih\_\{s\}=\\frac\{1\}\{\|V\_\{t\}\|\}\\sum\_\{i\}h\_\{i\}Actor MLPfθf\_\{\\theta\}softmax overEtE\_\{t\}πθ​\(a∣st\)\\pi\_\{\\theta\}\(a\\mid s\_\{t\}\)Critic MLPVψ​\(st\)V\_\{\\psi\}\(s\_\{t\}\)Merge\(i,j\)\(i,j\)recompute edgessampleat∼πθa\_\{t\}\\sim\\pi\_\{\\theta\}\(training\) or beam search \(inference\)ata\_\{t\}Gt\+1G\_\{t\+1\}: repeat untilEt=∅E\_\{t\}=\\varnothing

Figure 3:Proposed actor\-critic architecture\. The encoder maps the current compatibility graph to node embeddings\. Two size\-independent readouts feed the actor and the critic\. The chosen merge updates the graph and the loop repeats until no compatible pair remains\.Policy and value are parameterized by a GNN operating onGtG\_\{t\}\(Figure[3](https://arxiv.org/html/2609.25397#S4.F3)\)\.

##### Graph encoder

Node features \([6](https://arxiv.org/html/2609.25397#S4.E6)\) are linearly embedded intoℝd\\mathbb\{R\}^\{d\}\(d=128d=128\) and refined byL=3L=3message\-passing layers, each followed by a residual connection and layer normalization,hi\(l\+1\)=LN⁡\(hi\(l\)\+h~i\(l\+1\)\)h\_\{i\}^\{\(l\+1\)\}=\\mathrm\{LN\}\\big\(h\_\{i\}^\{\(l\)\}\+\\tilde\{h\}\_\{i\}^\{\(l\+1\)\}\\big\)\. We instantiate three standard aggregation schemes forh~i\(l\+1\)\\tilde\{h\}^\{\(l\+1\)\}\_\{i\}, with𝒩⁡\(i\)\\mathcal\{N\}\(i\)the neighbourhood ofiiinGtG\_\{t\}andW\(l\)W^\{\(l\)\}a learnable matrix\. The graph convolutional network \(GCN\)\[[44](https://arxiv.org/html/2609.25397#bib.bib44)\]uses isotropic, degree\-normalized aggregation,

h~i\(l\+1\)=ReLU⁡\(∑j∈𝒩⁡\(i\)∪\{i\}1d~i​d~j​W\(l\)​hj\(l\)\),\\tilde\{h\}\_\{i\}^\{\(l\+1\)\}=\\mathrm\{ReLU\}\\Big\(\\textstyle\\sum\_\{j\\in\\mathcal\{N\}\(i\)\\cup\\\{i\\\}\}\\frac\{1\}\{\\sqrt\{\\tilde\{d\}\_\{i\}\\tilde\{d\}\_\{j\}\}\}\\,W^\{\(l\)\}h\_\{j\}^\{\(l\)\}\\Big\),\(7\)whered~i\\tilde\{d\}\_\{i\}is the degree ofiiincluding the self\-loop\. The graph attention network \(GAT\)\[[45](https://arxiv.org/html/2609.25397#bib.bib45)\]replaces the fixed normalization by learnable anisotropic weights, here withK=4K=4attention heads,

h~i\(l\+1\)=ReLU⁡\(∑j∈𝒩⁡\(i\)∪\{i\}αi​j\(l\)​W\(l\)​hj\(l\)\),\\tilde\{h\}\_\{i\}^\{\(l\+1\)\}=\\mathrm\{ReLU\}\\Big\(\\textstyle\\sum\_\{j\\in\\mathcal\{N\}\(i\)\\cup\\\{i\\\}\}\\alpha\_\{ij\}^\{\(l\)\}\\,W^\{\(l\)\}h\_\{j\}^\{\(l\)\}\\Big\),\(8\)whereαi​j\(l\)\\alpha\_\{ij\}^\{\(l\)\}is a softmax over𝒩⁡\(i\)∪\{i\}\\mathcal\{N\}\(i\)\\cup\\\{i\\\}of a single\-layer scoring network applied to\[W\(l\)hi\(l\)∥W\(l\)hj\(l\)\]\[W^\{\(l\)\}h\_\{i\}^\{\(l\)\}\\,\\\|\\,W^\{\(l\)\}h\_\{j\}^\{\(l\)\}\]\. The graph isomorphism network \(GIN\)\[[46](https://arxiv.org/html/2609.25397#bib.bib46)\]uses sum aggregation followed by an MLP update,

h~i\(l\+1\)=MLP\(l\)​\(\(1\+ϵ\(l\)\)​hi\(l\)\+∑j∈𝒩⁡\(i\)hj\(l\)\),\\tilde\{h\}\_\{i\}^\{\(l\+1\)\}=\\mathrm\{MLP\}^\{\(l\)\}\\Big\(\(1\+\\epsilon^\{\(l\)\}\)\\,h\_\{i\}^\{\(l\)\}\+\\textstyle\\sum\_\{j\\in\\mathcal\{N\}\(i\)\}h\_\{j\}^\{\(l\)\}\\Big\),\(9\)whereϵ\(l\)\\epsilon^\{\(l\)\}is a learnable scalar\.

##### Size\-independent readouts

From the final embeddingshi=hi\(L\)h\_\{i\}=h\_\{i\}^\{\(L\)\}two representations are formed\. The*state*vector is the mean of the node embeddings,hs=1\|Vt\|​∑i∈Vthih\_\{s\}=\\frac\{1\}\{\|V\_\{t\}\|\}\\sum\_\{i\\in V\_\{t\}\}h\_\{i\}, and the*action*vector of a candidate edge is the concatenation of its endpoints,h\(i,j\)=\[hi∥hj\]∈ℝ2​dh\_\{\(i,j\)\}=\[h\_\{i\}\\,\\\|\\,h\_\{j\}\]\\in\\mathbb\{R\}^\{2d\}\. Both have fixed dimension regardless of\|Vt\|\|V\_\{t\}\|and\|Et\|\|E\_\{t\}\|, so a single trained network applies to graphs of any size\.

##### Actor and critic

The actor scores every feasible edge with a three\-layer MLPfθ:ℝ2​d→ℝf\_\{\\theta\}:\\mathbb\{R\}^\{2d\}\\to\\mathbb\{R\}\(hidden widths 128 and 64\) and normalizes over the current edge set,

πθ​\(a=\(i,j\)∣st\)=exp⁡fθ​\(h\(i,j\)\)∑\(u,v\)∈Etexp⁡fθ​\(h\(u,v\)\)\.\\pi\_\{\\theta\}\(a=\(i,j\)\\mid s\_\{t\}\)=\\frac\{\\exp f\_\{\\theta\}\(h\_\{\(i,j\)\}\)\}\{\\sum\_\{\(u,v\)\\in E\_\{t\}\}\\exp f\_\{\\theta\}\(h\_\{\(u,v\)\}\)\}\.\(10\)The critic predicts the state valueVψ​\(st\)V\_\{\\psi\}\(s\_\{t\}\)fromhsh\_\{s\}with an MLP of the same shape\. For SAC and the value\-based algorithms, the same action vectors feed aQQ\-networkQϕ​\(st,a\)Q\_\{\\phi\}\(s\_\{t\},a\)of the same shape, and the value\-based policies selectarg⁡maxa∈Et​Qϕ​\(st,a\)\\arg\\max\_\{a\\in E\_\{t\}\}Q\_\{\\phi\}\(s\_\{t\},a\)\.

### 4\.3Training

The MDP and the architecture do not depend on the learning algorithm\. We train policies with three policy\-gradient methods, REINFORCE\[[47](https://arxiv.org/html/2609.25397#bib.bib47)\], Advantage Actor–Critic \(A2C\)\[[48](https://arxiv.org/html/2609.25397#bib.bib48)\]and Proximal Policy Optimization \(PPO\)\[[49](https://arxiv.org/html/2609.25397#bib.bib49)\], which optimizeπθ\\pi\_\{\\theta\}directly and use the critic as a baseline\. We also train with Soft Actor–Critic \(SAC\)\[[50](https://arxiv.org/html/2609.25397#bib.bib50)\], a maximum\-entropy actor–critic method that learns a softQQ\-function and a stochastic policy, and with two value\-based methods, Deep Q\-Network \(DQN\)\[[51](https://arxiv.org/html/2609.25397#bib.bib51)\]and SARSA\[[52](https://arxiv.org/html/2609.25397#bib.bib52)\], which learnQϕQ\_\{\\phi\}only and act greedily on it withϵ\\epsilon\-greedy exploration during training\. All follow their standard formulations\. As the primary configuration, PPO is described here\. Each training epoch samples a batch ofMMindependent instances from the training distribution, rolls out one episode per instance with the current policy, and stores every transition of these episodes in a bufferℬ\\mathcal\{B\}\. For each transition it computes the reward\-to\-goR^t=∑t′≥tRt′\\hat\{R\}\_\{t\}=\\sum\_\{t^\{\\prime\}\\geq t\}R\_\{t^\{\\prime\}\}\(undiscounted,γ=1\\gamma=1, since the horizon is finite\) and the advantageA^t=R^t−Vψ​\(st\)\\hat\{A\}\_\{t\}=\\hat\{R\}\_\{t\}\-V\_\{\\psi\}\(s\_\{t\}\), normalized to zero mean and unit variance overℬ\\mathcal\{B\}\. The parameters are then updated forKKinner epochs overℬ\\mathcal\{B\}on the clipped surrogate

ℒ=𝔼t​\[min⁡\(ρt​A^t,clip⁡\(ρt,1−ε,1\+ε\)​A^t\)\]−cv𝔼t\[\(Vψ\(st\)−R^t\)2\]\+ce𝔼t\[ℋ\(πθ\(⋅∣st\)\)\],\\begin\{split\}\\mathcal\{L\}=\{\}&\\mathbb\{E\}\_\{t\}\\Big\[\\min\\big\(\\rho\_\{t\}\\hat\{A\}\_\{t\},\\ \\mathrm\{clip\}\(\\rho\_\{t\},1\-\\varepsilon,1\+\\varepsilon\)\\hat\{A\}\_\{t\}\\big\)\\Big\]\\\\ &\-c\_\{v\}\\,\\mathbb\{E\}\_\{t\}\\big\[\(V\_\{\\psi\}\(s\_\{t\}\)\-\\hat\{R\}\_\{t\}\)^\{2\}\\big\]\+c\_\{e\}\\,\\mathbb\{E\}\_\{t\}\\big\[\\mathcal\{H\}\(\\pi\_\{\\theta\}\(\\cdot\\mid s\_\{t\}\)\)\\big\],\\end\{split\}\(11\)with probability ratioρt=πθ​\(at∣st\)/πθold​\(at∣st\)\\rho\_\{t\}=\\pi\_\{\\theta\}\(a\_\{t\}\\mid s\_\{t\}\)/\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(a\_\{t\}\\mid s\_\{t\}\), clipping parameterε\\varepsilon, value coefficientcvc\_\{v\}and entropy coefficientcec\_\{e\}\. The checkpoint with the best performance on a held\-out validation set drawn from the training distribution is retained\. Algorithm[1](https://arxiv.org/html/2609.25397#alg1)summarizes the procedure\. The values of all hyperparameters are listed in Table[2](https://arxiv.org/html/2609.25397#S5.T2)\.

Algorithm 1Training with PPO1:training distribution

𝒟\\mathcal\{D\}, epochs

TT, batch size

MM, inner epochs

KK
2:initialize encoder, actor

θ\\theta, critic

ψ\\psi
3:forepoch

=1,…,T=1,\\dots,Tdo

4:

ℬ←∅\\mathcal\{B\}\\leftarrow\\emptyset⊳\\trianglerightbuffer of transitions collected in this epoch

5:for

m=1,…,Mm=1,\\dots,Mdo

6:sample

\(W,C\)∼𝒟\(W,C\)\\sim\\mathcal\{D\}; build

G0G\_\{0\}by \([5](https://arxiv.org/html/2609.25397#S3.E5)\)

7:while

Et≠∅E\_\{t\}\\neq\\varnothingdo

8:

at∼πθ\(⋅∣Gt\)a\_\{t\}\\sim\\pi\_\{\\theta\}\(\\cdot\\mid G\_\{t\}\)by \([10](https://arxiv.org/html/2609.25397#S4.E10)\); merge

ata\_\{t\}; observe

Rt=R⁡\(st,at\)R\_\{t\}=R\(s\_\{t\},a\_\{t\}\)
9:endwhile

10:

R^t←∑t′≥tRt′\\hat\{R\}\_\{t\}\\leftarrow\\sum\_\{t^\{\\prime\}\\geq t\}R\_\{t^\{\\prime\}\}for every step

ttof the episode

11:append

\{\(st,at,log⁡πθ​\(at∣st\),R^t\)\}t\\\{\(s\_\{t\},a\_\{t\},\\log\\pi\_\{\\theta\}\(a\_\{t\}\\mid s\_\{t\}\),\\hat\{R\}\_\{t\}\)\\\}\_\{t\}to

ℬ\\mathcal\{B\}
12:endfor

13:

A^t←R^t−Vψ​\(st\)\\hat\{A\}\_\{t\}\\leftarrow\\hat\{R\}\_\{t\}\-V\_\{\\psi\}\(s\_\{t\}\), normalized over

ℬ\\mathcal\{B\}
14:for

k=1,…,Kk=1,\\dots,Kdo

15:update

\(θ,ψ\)\(\\theta,\\psi\)by Adam on \([11](https://arxiv.org/html/2609.25397#S4.E11)\) with gradient\-norm clipping

16:endfor

17:ifvalidation epochthenevaluate on the validation set; keep the best checkpoint

18:endif

19:endfor

### 4\.4Inference: stochastic beam search

At inference the trained policy is decoded with*stochastic beam search*of widthBB\(Algorithm[2](https://arxiv.org/html/2609.25397#alg2)\), which keepsBBpartial solutions in parallel\. At every step, each of them samplesmin⁡\(B,\|Et\|\)\\min\(B,\|E\_\{t\}\|\)distinct edges fromπθ\\pi\_\{\\theta\}without replacement\. The resulting children are ranked first by their current bin count and then by cumulative log\-probability, and the bestBBare retained\. Completed solutions are kept aside and the one with the fewest bins is returned\. Sampling rather than taking theBBmost probable edges lets the search reach merges to which the policy assigns low but non\-negligible probability\. Since every beam call is seeded, the decoder is deterministic for a given seed\.

Algorithm 2Inference with stochastic beam search1:items

WW, capacity

CC, trained policy

πθ\\pi\_\{\\theta\}, beam width

BB
2:build

G0G\_\{0\}by \([5](https://arxiv.org/html/2609.25397#S3.E5)\);

𝒫←\{\(G0,0\)\}\\mathcal\{P\}\\leftarrow\\\{\(G\_\{0\},\\,0\)\\\};

ℱ←∅\\mathcal\{F\}\\leftarrow\\emptyset
3:while

𝒫≠∅\\mathcal\{P\}\\neq\\emptysetdo

4:

𝒞←∅\\mathcal\{C\}\\leftarrow\\emptyset
5:foreach

\(G,σ\)∈𝒫\(G,\\sigma\)\\in\\mathcal\{P\}do

6:compute

xix\_\{i\}by \([6](https://arxiv.org/html/2609.25397#S4.E6)\);

π←πθ\(⋅∣G\)\\pi\\leftarrow\\pi\_\{\\theta\}\(\\cdot\\mid G\)by \([10](https://arxiv.org/html/2609.25397#S4.E10)\)

7:sample

k=min⁡\(B,\|E\|\)k=\\min\(B,\|E\|\)distinct edges

a\(1\),…,a\(k\)∼πa^\{\(1\)\},\\dots,a^\{\(k\)\}\\sim\\piwithout replacement

8:for

r=1,…,kr=1,\\dots,kdo

9:

G′←G^\{\\prime\}\\leftarrowmerge

a\(r\)a^\{\(r\)\}in

GG;

σ′←σ\+log⁡π⁡\(a\(r\)\)\\sigma^\{\\prime\}\\leftarrow\\sigma\+\\log\\pi\(a^\{\(r\)\}\)
10:if

E⁡\(G′\)=∅E\(G^\{\\prime\}\)=\\varnothingthenadd

G′G^\{\\prime\}to

ℱ\\mathcal\{F\}
11:elseadd

\(G′,σ′\)\(G^\{\\prime\},\\sigma^\{\\prime\}\)to

𝒞\\mathcal\{C\}
12:endif

13:endfor

14:endfor

15:

𝒫←\\mathcal\{P\}\\leftarrowthe

BBelements of

𝒞\\mathcal\{C\}with fewest nodes

\|V\|\|V\|, ties broken by largest

σ′\\sigma^\{\\prime\}
16:endwhile

17:return

arg⁡minG∈ℱ​\|V⁡\(G\)\|\\arg\\min\_\{G\\in\\mathcal\{F\}\}\|V\(G\)\|⊳\\trianglerighteach remaining node is a bin

## 5Experiments and Results

### 5\.1Benchmark instances

We use the BPPLIB library\[[11](https://arxiv.org/html/2609.25397#bib.bib11)\]and evaluate on*all*instances of its nine complete families \(Table[1](https://arxiv.org/html/2609.25397#S5.T1)\)\. Optimal or best\-known values are taken from BPPLIB\. The families differ widely in item count, capacity and weight structure and are therefore out of distribution for a model trained on uniform 50\-item instances\.

Table 1:BPPLIB families
### 5\.2Baselines and comparators

##### Constructive heuristic

FFD\[[12](https://arxiv.org/html/2609.25397#bib.bib12)\]is the reference constructive heuristic\. BFD produced identical bin counts on our validation data and is omitted from the tables\.

##### Grouping metaheuristic

We implemented a GGA following Falkenauer\[[16](https://arxiv.org/html/2609.25397#bib.bib16)\]\. The population contains 50 packings and is initialized with the FFD packing, the BFD packing and 48 first\-fit packings of random item permutations\. Parents are chosen by tournament selection of size 3\. The grouping crossover keeps the fullest half of the bins of the first parent and reinserts the remaining items by BFD, following the bin order of the second parent\. Two mutation operators, an item swap between two bins and an item move to another bin, are applied with probability 0\.3, and the best 10% of the population is carried over unchanged\. Each run is limited to 2 s per instance, or at most 500 generations\.

##### Learned solvers

We compare our work with the published results of Shi et al\.\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\], who report all nine BPPLIB families\. The comparison includes their bipartite\-GCN method with column generation, with and without the monotonicity cut \(BGCN, BGCNMC\), and the three RL baselines they report\. These baselines are pointer\-network RL \(PTR\), hierarchical RL with graph pointer networks \(HRL\-GPN\) and ranked\-reward MCTS \(RRMCTS\)\.

### 5\.3Metrics and evaluation protocol

Following\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]we report the*per\-instance optimality gap*\(b/opt−1\)×100%\(b/\\mathrm\{opt\}\-1\)\\times 100\\%, wherebbis the number of bins a method uses on an instance andopt\\mathrm\{opt\}is the optimal \(or best\-known\) number of bins of that instance from BPPLIB\[[11](https://arxiv.org/html/2609.25397#bib.bib11)\]\. For each family we report the mean and the standard deviation of this gap over its instances\. We also report the number of instances solved to optimality and the numbers of instances on which the proposed solver uses fewer or more bins than FFD\. Gaps are computed against the fixed BPPLIB optima and are hence independent of hardware\. Since beam decoding is stochastic, every instance is solved with three decoding seeds\{0,1,2\}\\\{0,1,2\\\}\. The reported gap of the proposed solver is that of the seed\-averaged bin count, and optimum counts refer to seed 0 unless stated otherwise\.

### 5\.4Implementation details

All models are trained on synthetic instances withn=50n=50items,C=100C=100and weights drawn uniformly from\{1,…,100\}\\\{1,\\dots,100\\\}, for 2,000 epochs of 16 episodes with a single training seed \(42\)\. Table[2](https://arxiv.org/html/2609.25397#S5.T2)lists the hyperparameters\.

Table 2:Hyperparameters of the primary configuration\.
### 5\.5Design study: encoder and learning algorithm

We trained all 18 encoder×\\timesalgorithm combinations \(GCN, GAT, GIN×\\timesPPO, A2C, REINFORCE, DQN, SAC, SARSA\) with identical budgets and compared the selected checkpoint of each on the 20 in\-distribution validation instances, decoded with the stochastic beam search used in all experiments \(Table[3](https://arxiv.org/html/2609.25397#S5.T3)\)\. DQN and SARSA learn action values only and have no sampling distribution, so beam search does not apply to them\. Under greedy decoding they remain far behind the other models \(27\.10\-30\.05 bins\) and are not considered further\. On these uniform 50\-item instances FFD, BFD and the 2 s GGA all use 26\.20 bins on average against a lower boundL1L\_\{1\}of 25\.15, so the validation set leaves almost no headroom and 26\.20 is the level of the strongest baselines\. Two observations follow\. First, only the GCN and GAT PPO models reach this level, with zero variance across seeds, whereas the REINFORCE, A2C and SAC models end 0\.07\-1\.03 bins above it\. Their policies are less peaked, so the alternatives that the beam samples are more often worse than the most probable merge, and the beam returns them when they tie on bin count\. PPO is therefore the best learning algorithm\. Second, GCN\+PPO and GAT\+PPO tie\. We select GCN for its simpler, parameter\-free aggregation and its smoother training curve\. This GCN\+PPO model is the proposed solver in all remaining experiments and the tables label it “Ours”\.

The choice of encoder is also confirmed on the benchmark\. A beam\-decoded grid on small subsets of Falkenauer T and Scholl 2 placed the GIN models ahead of all others, with GIN\+PPO first on Scholl 2 and third on Falkenauer T \(Appendix A, Table[10](https://arxiv.org/html/2609.25397#A1.T10)\)\. On the benchmark, however, GIN\+PPO trailed GCN\+PPO on most of the families\. The choice made on in\-distribution validation data therefore agrees with full\-benchmark generalization\. Selection on a narrow subset would have been misleading\.

Table 3:Design study: average bins of the encoder×\\timesalgorithm combination on the 20 in\-distribution validation instances \(B=5B=5, mean±\\pmstd over three seeds\)\. References on the same instances: FFD = BFD = GGA \(2 s\) 26\.20, lower boundL1L\_\{1\}25\.15\. Best value in bold\.
### 5\.6Results

Table[4](https://arxiv.org/html/2609.25397#S5.T4)reports the main result of the uniform\-trained GCN\+PPO model, decoded withB=5B=5and three seeds, on all 1,615 instances\. The proposed policy lowers the mean gap of FFD from 2\.66% to 2\.31% and uses fewer bins than FFD on 291 instances against 170 on which it uses more \(1,154 ties\)\. The improvement is concentrated on the high\-headroom families\. On Falkenauer T the gap drops from 14\.69% to 11\.88% with fewer bins on 75 of 80 instances and none lost\. On Scholl 3 it drops from 6\.06% to 4\.40% on all 10 instances, and on Scholl 2 from 3\.01% to 2\.31% \(119 wins, 54 losses\)\. On Falkenauer U and Schwerin 2 the gains are small but positive, but on Schwerin 1 and Wäscher the proposed solver coincides with FFD on every instance\. On the low\-headroom Hard28 and Scholl 1 families it is marginally worse than FFD \(1\.21% vs 1\.20%, and 0\.51% vs 0\.47%\), losing 101 Scholl 1 instances by one bin while winning 54\. In summary, the proposed method improves on FFD in five families, ties in two and is slightly behind in two\. The two sides of this comparison are not symmetric\. Where the proposed policy loses to FFD, it does so by a single bin \(by more than one bin on only 2 of the 1,615 instances\), whereas where it wins it saves up to 12 bins, and at least two bins on 76 instances\. Over the whole benchmark it uses 128,702 bins against 129,080 for FFD\.

The per\-instance results are stable across decoding seeds\. The spread of the family mean gap over the three seeds is at most 0\.46 percentage points \(Schwerin 2\) and below 0\.2 points on seven of nine families\. By count of optimal solutions, however, FFD \(795 of 1,615\) is ahead of the proposed solver \(729; 721 and 748 for the other two seeds\)\. The benchmark is dominated by easy Scholl 1 instances on which FFD is already optimal and the proposed solver occasionally spends one extra bin\. The GGA remains clearly ahead of both on every family \(0\.51% mean gap, 1,243 optima\)\.

Table 4:Zero\-shot results of the proposed solver \(Ours\) on all nine BPPLIB families\. Gap: per\-instance optimality gap \(%\), mean \(for Ours,±\\pmstandard deviation over instances\); lower is better\. “<<FFD” / “\>\>FFD”: instances on which Ours uses fewer / more bins than FFD\. Optima: instances solved to the BPPLIB optimum\. Best of FFD and Ours per family in bold; GGA shown for reference\.Since the model is trained only on 50\-item instances, Table[5](https://arxiv.org/html/2609.25397#S5.T5)breaks the four largest families down by item count\. Two observations follow\. First, generalization to instances up to twenty times larger than the training size does not degrade\. On Falkenauer T the improvement over FFD is robustly maintained across all sizes, at 2\.6–2\.9 percentage points \(13\.08% vs 16\.00% atn=60n=60; 10\.98% vs 13\.80% atn=501n=501\), with fewer bins on all 20 instances forn≥120n\\geq 120, and on Scholl 2 the gap of the proposed solver stays between 2\.2% and 2\.5% at every size while the number of instances won over FFD rises from 20 to 48\. Second, on the low\-headroom Scholl 1 family the balance tips towards FFD asnngrows \(24 wins against 67 losses atn=500n=500\)\. When almost every instance is FFD\-optimal, longer episodes give the stochastic decoder more opportunities to spend one extra bin\. On Falkenauer U the proposed solver is slightly ahead at every size\.

Table 5:Results by item countnnfor the four largest families \(per\-instance gap %\. Ours: proposed solver\)\. “<<” / “\>\>”: instances on which Ours uses fewer / more bins than FFD\.Table[6](https://arxiv.org/html/2609.25397#S5.T6)compares the proposed solver with the learned methods of Shi et al\.\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\], who evaluate all nine BPPLIB families used here with the identical per\-instance gap and deterministic decoding of their policies\. Three findings follow\. First, the pointer\-network baseline PTR essentially reproduces FFD\. It equals FFD on six families and is behind it by at most 0\.4 points on the other three, so our solver attains a lower gap than PTR on six families, ties on Schwerin 1 and Wäscher, and is higher only on Hard28 by 0\.01 points\. Second, our solver is far more stable across distributions than HRL\-GPN and RRMCTS\. Those methods reach near\-zero gaps on the Schwerin families but degrade to 13–14% on Scholl 3, 18–19% on Falkenauer T, 27–28% on Scholl 1 and 38–40% on Falkenauer U and Hard28, whereas the largest gap of our solver is 11\.88% and it stays below 1\.3% on Falkenauer U, Hard28 and Scholl 1\. It attains a lower gap than both on seven of nine families\. Third, against BGCN/BGCNMC, which solve linear and integer programs inside a column\-generation loop at inference time, the proposed method is ahead on the three families with the most structure to exploit \(Falkenauer T 11\.88% vs 12\.57%, Scholl 2 2\.31% vs 2\.36–2\.38%, Falkenauer U 1\.28% vs 1\.34%\), ties on Wäscher, and is behind on Scholl 3 and the Schwerin families, where column generation is particularly effective, and by small margins on Hard28 and Scholl 1\.

Table 6:Comparison with the learned solvers of Shi et al\.\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]on the nine BPPLIB families \(per\-instance optimality gap %, lower is better; their values from Table II of\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]\)\. BGCN/BGCNMC: bipartite GCN with column generation, without / with monotonicity cut\. PTR, HRL\-GPN, RRMCTS: their RL baselines\. Best per family in bold, the multi\-way ties on Wäscher and Hard28 are left unbolded\.
### 5\.7Ablation studies

#### 5\.7\.1Reward function

We compare the per\-step reward of Section[4\.1](https://arxiv.org/html/2609.25397#S4.SS1)with two alternatives\. The*terminal*reward is00at every step and equal to the negative number of bins at the end of the episode\. It is objective\-equivalent to the per\-step reward but sparse\. The*shaped*reward adds a dense potential\-based term to the per\-step reward,R=1\+λ⋅2​ℓi​ℓj/C2R=1\+\\lambda\\cdot 2\\ell\_\{i\}\\ell\_\{j\}/C^\{2\}for merging nodes of loadsℓi\\ell\_\{i\}andℓj\\ell\_\{j\}\. It is the increase of the potentialΦ⁡\(s\)=∑i\(ℓi/C\)2\\Phi\(s\)=\\sum\_\{i\}\(\\ell\_\{i\}/C\)^\{2\}caused by the merge and therefore favours tight local packings \(λ=1\\lambda=1\)\. Table[7](https://arxiv.org/html/2609.25397#S5.T7)compares the per\-step reward with the shaped reward on the full benchmark \(GCN\+PPO, three seeds,B=5B=5\)\. The shaped reward improves the single highest\-headroom family, Falkenauer T \(10\.47% vs 11\.88%\)\. However, it degrades every other family, especially the low\-headroom ones \(Hard28 5\.49% vs 1\.21%; Scholl 1 2\.58% vs 0\.51%\), and finds only 342 optima against 729\. Its overall gap \(3\.81%\) is worse than FFD \(2\.66%\)\. The dense shaping signal biases the policy towards tight local packings that pay off only where the instance structure rewards them\. The sparse terminal reward, in turn, is never better than the per\-step reward\. On the 60\-item Falkenauer T instances the per\-step reward wins 3 instances and loses none \(22\.65 vs 22\.80 bins\)\. We therefore retain the simplest, objective\-equivalent per\-step reward\.

Table 7:Reward ablation on the full benchmark \(GCN\+PPO, three seeds,B=5B=5\): per\-instance gap \(%\) of the per\-step and shaped rewards, with FFD for reference\. Better of the two rewards per family in bold\.
#### 5\.7\.2Training distribution

Since the benchmark families are out of distribution for the uniform\-trained model, we tested two alternatives with the GCN\+PPO configuration: \(i\) a*mixed*curriculum in which each episode draws one of five BPPLIB\-matched distributions \(three uniform ranges, a capped rangeU⁡\[1,0\.63​C\]U\[1,0\.63C\]and a triplet\-like rangeU⁡\[C/4,C/2\]U\[C/4,C/2\]\), and \(ii\)*specialists*trained for 3,000 epochs on the distribution of a target family\. Both were decoded withB=5B=5and a single seed and are compared with the uniform model on the same instances with the per\-instance gap\. Neither improved on the uniform model\. The mixed model was worse on the slice evaluated \(Scholl 1,n=50n=50: 3\.99% vs 0\.53%\)\. The specialists were evaluated on their complete target families and lost to the uniform model on each\. The capped specialist reached 14\.17% on Scholl 2 against 2\.35%, using more bins than the uniform model on 425 of the 480 instances and fewer on none\. TheU⁡\[30,100\]U\[30,100\]specialist reached 2\.07% on the Scholl 1 W4 class against 0\.55%\. TheU⁡\[1,100\]U\[1,100\]specialist coincides with the uniform model and tied on Wäscher\. Matching the training distribution to the target family therefore does not help\. The uniform distribution exposes the policy to the widest variety of local configurations\.

#### 5\.7\.3Hyperparameter tuning

To check that the residual gap to the metaheuristic is not a tuning artefact, we optimized the learning rate, entropy coefficient, number of GNN layers and embedding width of the GCN\+PPO model with Optuna \(TPE sampler, median pruner, 20 sampled trials, 500 epochs each\)\. The objective was theB=5B=5beam bin count on a held\-out validation split disjoint from both the training and the test instances\. The default configuration was included as a reference trial under the same protocol\. The best configuration \(learning rate3\.3×10−43\.3\\times 10^\{\-4\}, 4 layers, width 128, entropy 0\.046\) improved the validation objective by only 0\.04 bins over the defaults\. Retrained for 2,000 epochs and evaluated on the disjoint test split, it used 0\.17 fewer bins than the default model on Falkenauer T and 0\.09 more on Scholl 2 \(Table[8](https://arxiv.org/html/2609.25397#S5.T8)\)\. Both differences are within the run\-to\-run variation of identical settings, which reached 0\.4 bins across four repetitions of one configuration\. The number of layers had the smallest importance \(about 0\.05\), while width, learning rate and entropy coefficient shared the remainder roughly equally\. The defaults are thus near\-optimal, and the gap to the metaheuristic is structural rather than a matter of tuning\.

Table 8:Hyperparameter tuning \(GCN\+PPO, Optuna, 20 sampled trials\)\. Test split disjoint from the tuning objective: first 10 Falkenauer T \(n=60n=60, optimum 20\.0\) and first 15 Scholl 2 \(n=50n=50, optimum 17\.33\) instances; average bins,B=5B=5, three seeds\.

## 6Discussion

### 6\.1The role of headroom

To understand the pattern in Table[4](https://arxiv.org/html/2609.25397#S5.T4), we split the 1,615 instances into two groups according to whether FFD already finds an optimal solution\. On the 795 FFD\-optimal instances the proposed solver cannot win by definition\. It ties on 662 and loses one bin on 133, for a mean gap of 0\.21%\. On the 820 instances where FFD is suboptimal it wins 291, loses 37 and lowers the mean gap from 5\.25% to 4\.35%\. The proposed solver is thus best read as a method that improves FFD where structure leaves room, in particular on the triplet\-structured Falkenauer T instances, where the benefit is maintained up ton=501n=501, rather than as a uniform replacement for FFD\. The two families on which it reproduces FFD exactly, Schwerin 1 and Wäscher, are instructive\. On Schwerin 1 the items lie in\[150,200\]\[150,200\]withC=1,000C=1\{,\}000, and on Wäscher 99\.6% of the item pairs are compatible, so the initial compatibility graph is complete or nearly so\. The normalized degree feature is then constant for most of the episode and becomes informative only when partial bins approach the capacity\. The state carries little structural information beyond the loads, and the policy has little to exploit\.

### 6\.2Relation to metaheuristics and hybrid learned solvers

A grouping genetic algorithm remains ahead of the proposed method on every family \(0\.51% vs 2\.31%, 1,243 vs 729 optima\), and none of the levers we examined, reward, training distribution, encoder or hyperparameters, closes the last few tenths of a bin\. We attribute this to the level of abstraction at which learning is applied\. The GGA searches at the level of whole bins with operators that preserve good groups while our policy constructs solutions by roughlynnlocal pairwise decisions amongΘ⁡\(n2\)\\Theta\(n^\{2\}\)candidates\. The most competitive learned solver for 1D\-BPP\[[35](https://arxiv.org/html/2609.25397#bib.bib35)\]likewise places learning at a higher level, selecting among columns proposed by column generation\. The comparison in Table[6](https://arxiv.org/html/2609.25397#S5.T6)nevertheless shows that a pure end\-to\-end constructor can match or exceed a solver\-augmented method on the most structured families and is considerably more robust across distributions than the hierarchical\-RL and MCTS baselines, while the pointer\-network baseline never moves far from FFD\.

## 7Conclusions and future work

We formulated 1D\-BPP as an MDP on an item\-compatibility graph and developed an end\-to\-end graph reinforcement learning solver whose size\-invariant GNN actor–critic is trained with PPO on 50\-item uniform instances and decoded with stochastic beam search\. A controlled design study and ablations over rewards, training distributions and hyperparameters fixed a deliberately simple configuration, all selected on in\-distribution validation data\. Evaluated zero\-shot on all 1,615 instances of the nine BPPLIB families with three decoding seeds, the single model lowers the mean gap of FFD from 2\.66% to 2\.31%, with gains concentrated on structured, high\-headroom families, attains a lower gap than a column\-generation\-based learned solver on three of the nine families evaluated by both studies, and is markedly more stable across distributions than hierarchical\-RL and MCTS baselines\. A grouping genetic algorithm remains ahead overall, and our analysis attributes the residual gap to the pairwise, constructive level at which learning is applied rather than to tuning\.

When a few extra bins are tolerable, FFD remains the method of choice, and when the best attainable quality is required, a grouping metaheuristic should be used\. The proposed method sits between the two\. It improves FFD on structured instances with a single trained policy, without a per\-instance search and without hand\-designed crossover, mutation or repair operators\. Its only problem\-specific component is the compatibility rule that defines the edges, so the framework can be adapted to constrained variants of the problem by changing that rule alone\.

This flexibility comes at a computational cost\. Although the proposed size\-agnostic GNN policy achieves competitive results without requiring hand\-crafted rules, its inference time, particularly when decoded with stochastic beam search, is currently higher than that of highly optimized heuristic implementations such as FFD\.

This work shows that a new formulation, an MDP on the item\-compatibility graph solved by a single size\-invariant policy, is viable for 1D\-BPP\. The configuration studied here was kept deliberately simple, and both the formulation and the architecture leave room for improvement\. Future work may proceed in three directions\. The first is to raise the level at which learning is applied, by letting the policy either select the next item for an open bin, which reduces the action space from quadratic to linear in the number of items, or construct whole bins as single actions\. The second is to close the computational gap to optimized heuristic implementations by accelerating the graph update mechanism or developing more efficient greedy decoding strategies\. Finally, from a knowledge\-engineering perspective, future research could extend this graph\-based DRL framework to dynamic or stochastic environments, such as real\-time cloud resource allocation or dynamic freight loading\. In such settings, where item\-compatibility graphs are continuously updated with streaming data, the proposed framework has the potential to evolve into a highly adaptive, real\-time intelligent decision support system\.

## Data availability

The BPPLIB instances are publicly available\[[11](https://arxiv.org/html/2609.25397#bib.bib11)\]\. All other materials are available upon request\.

## Acknowledgements

This work is supported by the Scientific and Technological Research Council of Türkiye \(TÜBİTAK\) under Grant No\. 124M974\.

## Appendix AFull design\-study grids

Tables[9](https://arxiv.org/html/2609.25397#A1.T9)and[10](https://arxiv.org/html/2609.25397#A1.T10)give the complete per\-model grids underlying Section[5\.5](https://arxiv.org/html/2609.25397#S5.SS5)\. The greedy grid \(six families, all trained models\) shows the split between the policy\-gradient methods and SAC, DQN and SARSA, and the collapse of greedy decoding to FFD\. The beam grid \(B=20B=20, three seeds\) gives per\-model results on the first 20 Falkenauer T and first 15 Scholl 2 instances, the discriminating subsets used during development\. In Table[9](https://arxiv.org/html/2609.25397#A1.T9)the first block of 18 rows are the uniform\-trained \(V1\) models, the second block the mixed\-trained \(V2\) models, and the last row a generalist model trained on the Scholl 1 distributions \(V3\)\.

Table 9:Greedy \(deterministic, argmax\) decoding: average bins for all trained models on the design\-study evaluation set\. Policy\-based methods \(A2C/PPO/REINFORCE\) reproduce FFD almost exactly; SAC and the value\-based methods \(DQN/SARSA\) fall below it\. V1 = uniform training, V2 = mixed, V3 = generalist\.Table 10:Stochastic beam \(B=20B\{=\}20, three seeds, mean±\\pmstd average bins\) for the policy models on the two discriminating families, sorted by Falkenauer\_T\. FFD and GGA references shown at the bottom\.
## References

- \[1\]S\. Martello, P\. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990\.
- \[2\]Q\. Wang, C\. Tang, Deep reinforcement learning for transportation network combinatorial optimization: A survey, Knowledge\-Based Systems 233 \(2021\) 107526\.[doi:10\.1016/j\.knosys\.2021\.107526](https://doi.org/10.1016/j.knosys.2021.107526)\.
- \[3\]M\. Delorme, M\. Iori, S\. Martello, Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research 255 \(1\) \(2016\) 1–20\.
- \[4\]G\. Wäscher, H\. Haußner, H\. Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 \(3\) \(2007\) 1109–1130\.
- \[5\]N\. Bansal, M\. Eliáš, A\. Khan, Improved approximation for vector bin packing, in: Proceedings of the Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\), 2016, pp\. 1561–1579\.
- \[6\]D\. Bein, W\. Bein, S\. Venigella, Cloud storage and online bin packing, in: Intelligent Distributed Computing V, Vol\. 382 of Studies in Computational Intelligence, Springer, Berlin, Heidelberg, 2011, pp\. 63–68\.[doi:10\.1007/978\-3\-642\-24013\-3\_7](https://doi.org/10.1007/978-3-642-24013-3_7)\.
- \[7\]F\. Marinelli, A\. Pizzuti, W\. Wu, M\. Yagiura, One\-dimensional bin packing with pattern\-dependent processing time, European Journal of Operational Research 322 \(3\) \(2025\) 770–782\.[doi:10\.1016/j\.ejor\.2024\.11\.023](https://doi.org/10.1016/j.ejor.2024.11.023)\.
- \[8\]M\. R\. Garey, D\. S\. Johnson, Computers and Intractability: A Guide to the Theory of NP\-Completeness, W\. H\. Freeman, 1979\.
- \[9\]A\. Scholl, R\. Klein, C\. Jürgens, BISON: A fast hybrid procedure for exactly solving the one\-dimensional bin packing problem, Computers & Operations Research 24 \(7\) \(1997\) 627–645\.
- \[10\]J\. M\. Valério de Carvalho, Exact solution of bin\-packing problems using column generation and branch\-and\-bound, Annals of Operations Research 86 \(1999\) 629–659\.
- \[11\]M\. Delorme, M\. Iori, S\. Martello, BPPLIB: a library for bin packing and cutting stock problems, Optimization Letters 12 \(2\) \(2018\) 235–250\.
- \[12\]D\. S\. Johnson, A\. Demers, J\. D\. Ullman, M\. R\. Garey, R\. L\. Graham, Worst\-case performance bounds for simple one\-dimensional packing algorithms, SIAM Journal on Computing 3 \(4\) \(1974\) 299–325\.
- \[13\]E\. G\. Coffman, J\. Csirik, G\. Galambos, S\. Martello, D\. Vigo, Bin packing approximation algorithms: Survey and classification, in: P\. M\. Pardalos, D\.\-Z\. Du, R\. L\. Graham \(Eds\.\), Handbook of Combinatorial Optimization, Springer, 2013, pp\. 455–531\.
- \[14\]K\. Fleszar, K\. S\. Hindi, New heuristics for one\-dimensional bin\-packing, Computers & Operations Research 29 \(7\) \(2002\) 821–839\.
- \[15\]G\. Dósa, The tight bound of first fit decreasing bin\-packing algorithm is FFD\(I\)≤\\leq11/9 OPT\(I\) \+ 6/9, in: Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Vol\. 4614 of Lecture Notes in Computer Science, Springer, 2007, pp\. 1–11\.
- \[16\]E\. Falkenauer, A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics 2 \(1\) \(1996\) 5–30\.
- \[17\]T\. Küçükyılmaz, H\. E\. Kızılöz, Cooperative parallel grouping genetic algorithm for the one\-dimensional bin packing problem, Computers & Industrial Engineering 125 \(2018\) 157–170\.
- \[18\]C\. Munien, S\. Mahabeer, E\. Dzitiro, S\. Singh, S\. Zungu, A\. E\.\-S\. Ezugwu, Metaheuristic approaches for one\-dimensional bin packing problem: A comparative performance study, IEEE Access 8 \(2020\) 227438–227465\.
- \[19\]Y\. Bengio, A\. Lodi, A\. Prouvost, Machine learning for combinatorial optimization: A methodological tour d’horizon, European Journal of Operational Research 290 \(2\) \(2021\) 405–421\.
- \[20\]N\. Mazyavkina, S\. Sviridov, S\. Ivanov, E\. Burnaev, Reinforcement learning for combinatorial optimization: A survey, Computers & Operations Research 134 \(2021\) 105400\.
- \[21\]N\. Vesselinova, R\. Steinert, D\. F\. Perez\-Ramirez, M\. Boman, Learning combinatorial optimization on graphs: A survey with applications to networking, IEEE Access 8 \(2020\) 120388–120416\.
- \[22\]O\. Vinyals, M\. Fortunato, N\. Jaitly, Pointer networks, in: Advances in Neural Information Processing Systems \(NeurIPS\), 2015\.
- \[23\]I\. Bello, H\. Pham, Q\. V\. Le, M\. Norouzi, S\. Bengio, Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv:1611\.09940 \(2016\)\.
- \[24\]E\. B\. Khalil, H\. Dai, Y\. Zhang, B\. Dilkina, L\. Song, Learning combinatorial optimization algorithms over graphs, in: Advances in Neural Information Processing Systems \(NeurIPS\), 2017\.
- \[25\]W\. Kool, H\. van Hoof, M\. Welling, Attention, learn to solve routing problems\!, in: International Conference on Learning Representations \(ICLR\), 2019\.
- \[26\]M\. Nazari, A\. Oroojlooy, L\. V\. Snýder, M\. Takáč, Reinforcement learning for solving the vehicle routing problem, in: Advances in Neural Information Processing Systems \(NeurIPS\), 2018\.
- \[27\]D\. Li, Z\. Gu, Y\. Wang, C\. Ren, F\. C\. M\. Lau, One model packs thousands of items with recurrent conditional query learning, Knowledge\-Based Systems 235 \(2022\) 107683\.
- \[28\]A\. Zhao, T\. Li, L\. Lin, A dynamic multi\-modal deep reinforcement learning framework for 3D bin packing problem, Knowledge\-Based Systems 299 \(2024\) 111990\.[doi:10\.1016/j\.knosys\.2024\.111990](https://doi.org/10.1016/j.knosys.2024.111990)\.
- \[29\]Y\. Xu, Z\. Yang, GraphPack: A reinforcement learning algorithm for strip packing problem using graph neural network, Journal of Circuits, Systems and Computers 33 \(8\) \(2024\) 2450139\.[doi:10\.1142/S0218126624501391](https://doi.org/10.1142/S0218126624501391)\.
- \[30\]W\. Wu, C\. Fan, J\. Huang, Z\. Liu, J\. Yan, Machine learning for the multi\-dimensional bin packing problem: Literature review and empirical evaluation, arXiv:2312\.08103 \(2023\)\.
- \[31\]C\. Zhang, Y\. Wu, Y\. Ma, et al\., A review on learning to solve combinatorial optimisation problems in manufacturing, IET Collaborative Intelligent Manufacturing 5 \(1\) \(2023\) e12072\.
- \[32\]N\. Dahmani, A\. Nazir, I\. Taleb, S\. M\. S\. Bukhari, Reinforcement learning based intelligent optimisation for bin packing problems: A review, Array 28 \(2025\) 100616\.[doi:10\.1016/j\.array\.2025\.100616](https://doi.org/10.1016/j.array.2025.100616)\.
- \[33\]J\. Fang, Y\. Rao, Q\. Luo, J\. Xu, Solving one\-dimensional cutting stock problems with the deep reinforcement learning, Mathematics 11 \(5\) \(2023\) 1028\.
- \[34\]X\. Huang, X\. Wang, Y\. Pu, C\. Li, W\. Liu, Optimizing one\-dimensional bin packing for conveyor belt logistics via pointer\-network\-based A2C and heuristics, Scientific Reports, in press \(2026\)\.[doi:10\.1038/s41598\-026\-63499\-8](https://doi.org/10.1038/s41598-026-63499-8)\.
- \[35\]F\. Shi, Y\. Meng, J\. Liu, L\. Tang, A combination feature\-based reinforcement learning approach via mathematical optimization, IEEE Transactions on Automation Science and Engineering 22 \(2025\) 12455–12469\.[doi:10\.1109/TASE\.2025\.3544431](https://doi.org/10.1109/TASE.2025.3544431)\.
- \[36\]D\. Sensarma, S\. S\. Sarma, A graph theoretic approach for minimizing storage space using bin packing heuristics, International Journal of Advanced Computer Science and Applications \(IJACSA\) 8 \(2\) \(2017\)\.[doi:10\.14569/IJACSA\.2017\.080205](https://doi.org/10.14569/IJACSA.2017.080205)\.
- \[37\]L\. V\. Kantorovich, Mathematical methods of organizing and planning production, Management Science 6 \(4\) \(1960\) 366–422\.
- \[38\]P\. C\. Gilmore, R\. E\. Gomory, A linear programming approach to the cutting\-stock problem, Operations Research 9 \(6\) \(1961\) 849–859\.
- \[39\]H\. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research 44 \(2\) \(1990\) 145–159\.
- \[40\]J\. M\. Valério de Carvalho, LP models for bin packing and cutting stock problems, European Journal of Operational Research 141 \(2\) \(2002\) 253–273\.
- \[41\]J\. González\-San\-Martín, L\. Cruz\-Reyes, C\. Gómez\-Santillán, et al\., Comparative study of heuristics for the one\-dimensional bin packing problem, in: O\. Castillo, P\. Melin \(Eds\.\), Hybrid Intelligent Systems Based on Extensions of Fuzzy Logic, Neural Networks and Metaheuristics, Vol\. 1096 of Studies in Computational Intelligence, Springer, Cham, 2023, pp\. 293–305\.[doi:10\.1007/978\-3\-031\-28999\-6\_19](https://doi.org/10.1007/978-3-031-28999-6_19)\.
- \[42\]D\. Silver, A\. Huang, C\. J\. Maddison, et al\., Mastering the game of Go with deep neural networks and tree search, Nature 529 \(7587\) \(2016\) 484–489\.
- \[43\]H\. Hu, X\. Zhang, X\. Yan, L\. Wang, Y\. Xu, Solving a new 3D bin packing problem with deep reinforcement learning method, arXiv preprint arXiv:1708\.05930 \(2017\)\.
- \[44\]T\. N\. Kipf, M\. Welling, Semi\-supervised classification with graph convolutional networks, in: International Conference on Learning Representations \(ICLR\), 2017\.
- \[45\]P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, Y\. Bengio, Graph attention networks, in: International Conference on Learning Representations \(ICLR\), 2018\.
- \[46\]K\. Xu, W\. Hu, J\. Leskovec, S\. Jegelka, How powerful are graph neural networks?, in: International Conference on Learning Representations \(ICLR\), 2019\.
- \[47\]R\. J\. Williams, Simple statistical gradient\-following algorithms for connectionist reinforcement learning, Machine Learning 8 \(3–4\) \(1992\) 229–256\.[doi:10\.1007/BF00992696](https://doi.org/10.1007/BF00992696)\.
- \[48\]V\. Mnih, A\. P\. Badia, M\. Mirza, et al\., Asynchronous methods for deep reinforcement learning, in: Proceedings of the 33rd International Conference on Machine Learning \(ICML\), Vol\. 48 of PMLR, 2016, pp\. 1928–1937\.
- \[49\]J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, O\. Klimov, Proximal policy optimization algorithms, arXiv preprint arXiv:1707\.06347 \(2017\)\.
- \[50\]T\. Haarnoja, A\. Zhou, P\. Abbeel, S\. Levine, Soft actor\-critic: Off\-policy maximum entropy deep reinforcement learning with a stochastic actor, in: Proceedings of the 35th International Conference on Machine Learning \(ICML\), Vol\. 80 of PMLR, 2018, pp\. 1861–1870\.
- \[51\]V\. Mnih, K\. Kavukcuoglu, D\. Silver, et al\., Human\-level control through deep reinforcement learning, Nature 518 \(7540\) \(2015\) 529–533\.[doi:10\.1038/nature14236](https://doi.org/10.1038/nature14236)\.
- \[52\]G\. A\. Rummery, M\. Niranjan, On\-line Q\-learning using connectionist systems, Tech\. Rep\. CUED/F\-INFENG/TR 166, Cambridge University Engineering Department \(1994\)\.