Learning to solve Class-Constrained Bin Packing Problems via Encoder-Decoder Model
Authors: Hanni Cheng
Ya Cong
Weihao Jiang
Shiliang Pu
Venue: ICLR 2024 poster (2024)
Keywords: Combinatorial Optimization
Class-Contrained Bin Packing Problems
Graph Convolution Network
Cluster Decode
Primary area: general machine learning (i.e., none of the above)
TL;DR: We introduce a vector BPP variant called Class-Constrained Bin Packing Problem and  propose a learning-based Encoder-Decoder Model to solve various kinds of CCBPP with a very small gap from the optimal.

Abstract: Neural methods have shown significant merit in solving combinatorial optimization (CO) problems, including the Bin Packing Problem (BPP). However, most existing ML-based approaches focus on geometric BPP like 3DBPP, neglecting complex vector BPP. In this study, we introduce a vector BPP variant called Class-Constrained Bin Packing Problem (CCBPP), dealing with items of both classes and sizes, and the objective is to pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold. To enhance the efficiency and practicality of solving CCBPP, we propose a learning-based Encoder-Decoder Model. The Encoder employs a Graph Convolution Network (GCN) to generate a heat-map, representing probabilities of different items packing together. The  Decoder decodes and fine-tunes the solution through Cluster Decode and Active Search methods, thereby producing high-quality solutions for CCBPP instances. Extensive experiments demonstrate that our proposed method consistently yields high-quality solutions for various kinds of CCBPP with a very small gap from the optimal. Moreover, our Encoder-Decoder Model also shows promising performance on one practical application of CCBPP, the *Manufacturing Order Consolidation Problem* (OCP).

Published as a conference paper at ICLR 2024
LEARNING TO SOLVE CLASS-CONSTRAINED BIN PACKING PROBLEMS VIA ENCODER-DECODER MODEL
Hanni Cheng
Ya Cong
Weihao Jiang
Shiliang Pu
Hikvision Research Institute, Hangzhou 310051, China (chenghanni, congya, jiangweihao5, htw.aagg...iiiiikkiiiiioooooom
ABSTRACT
Neural methods have shown significant merit in solving combinatorial optimiza- tion (CO) problems, including the Bin Packing Problem (BPP). However, most existing ML-based approaches focus on geometric BPP like 3DBPP, neglecting complex vector BPP. In this study, introduce vector BPP variant called Class-Constrained Bin Packing Problem (CCBPP), dealing with items of both classes and sizes, and the objective is pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold. To enhance the efficiency and practicality of solving CCBPP, we propose a learning- cerning-based Encoder- Incoder-Decoder Model. The Encoder employs Graph Convolu- tion Network (GCN) to generate meat-map. representing probabilities of different items packing together. The Decoder decodes and fine-tunes the solution through Cluster Decode and Active Search methods, thereby producing high-quality solu- tions for CCBPP instances. Extensive experiments demonstrate that our proposed method consistently yields high-quality solutions for various kinds CCBPP with very small gap from the optimal. Moreover, Encoder-Decoud Model also shows promising performance on one practical application of CCBPP, the Manu- facturing Order Consolidation Problem (OCP).
INTRODUCTION
The Bin Packing Problem (BPP) is classic combinatorial optimization (CO) problem with nu- merous practical applications in various industries, such as manufacturing, logistics, and resource allocation. Approximate heuristics methods and the exact algorithms have traditionally been used to find good solutions, but they may either lack solving efficiency or generalizability. Recently, variety of machine learning (ML) based methods (Kwon et al., 2020; Ma et al., 2021: Cheng et al., 2023; Jiang et al., 2021: Zhao et al., 202la;b; Zhang et al.. 2020; 2023) have been proved to be effective means to deal with complex CO problems including BPP with appealing advantages. These learning- based methods outperform both exact solvers and approximate heuristics in terms of solution efficiency as well as generalization ability.
There are primarily two generalizations of bin packing, geometric bin packing and vector bin pack- ing (Christensen et al., 2016). The majority of the learning-based BPP solvers focus on geometric BPP like offline and online 3D bin packing problem (3DBPP), which usually refers to packing set of auboid-shaper items along with x. y. and z axes respectively, into the minimum number of bins in an axis-aligned fashion. These methods usually leverage Attention Networks or Convolution Neural Networks as the Encoder to better represent the space constraints and learn to construct a solution sequentially via reinforcement learning (RL) which learns the solver from the generated packing quences (Duan et al., 2018; Zhang et al., 2021; Zhao et al., 2021a;b: Jiang et al., 2021). On the other hand, vector BPP with multiple properties and complex constraints have received limited attention in the neural CO problems field thus far. A typical example of vector BPP is the ConstCoont Bin Packing Problem (CCBPP), which deals with items of classes and sizes, and the objective is to pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold.
"Corresponding Author

---

Published as a conference paper at ICLR 2024
Different Properties
Carnectiiity Matrix Probabilities
Bins
Encoder
Decoder
Item Graph
Connection Heal-Map
Packing Solution
Figure 1: The pipeline of the Decoddr-De Model.
Our work aims learn novel leamiig-based model that can effectively solve various kinds of CCBPP that have multiple properties and complex constraints. In the context of CCBPP, only the packing sequences need be noted, without the position and orientation that need be considered in 3DBPP. However, an optimal packing result always corresponds to numerous packing sequences since shuffling the order of items within each bin does not affect the packing solution but will directly alter the packing sequence. Thus, it brings complexity when relying solely learning from packing sequences. To overcome these challenges, we introduce the connection matrix as a label to represent whether different items are packed together in the optimal result. If two items packed together, the corresponding value in the matrix is 1, otherwise, its value is O. The connection matrix providing richer information compared to the generated packing sequences.
In this paper, we propose a learning-basee Encoder-Decodee Decoder Model to get an approximate solution of CCBPP, illustrated in Fig. 1. Our approach involves the construction of graph based item information, as the sizes and classes of the items can be effectively represented through a graph structure. The training labels are defined the true connection matrix depicting relationships among various items. GCN is leveraged to train an Encoder so that the connectivity matrix with probabilities, also be treated as heat-map, of the instance can be generated. After the Encoder is well-trained, we introduce Cluster Decode algorithm to decode the heat-map matrix to an item sequence. Moreover, the test instances may suffer from significant differences in the distribution from training samples, which may lead to relatively poor performance. Therefore, Active Search technique is utilized during the decoding fine-tune the final solution, exploiting the instance- specific characteristics to ensure solution quality. Our Model is different from conventional Encoder- Decoder structures to solve CO problems (Vinyals et al., 2015; Kool et al., 2019; et al., 2019) that separated parts with different purposes, which makes the
the Encoder and the Decoder Encoder easier to learn from the connection matrix, and it will more flexible to be applied in real-word scenarios. Overall, the main contributions summarized as follows:
We give clear definition of CCBPP, and introduce practical application of CCBPP, the Manufacturing Order Consolidation Problem (OCP) detail. We show that CCBPP and OCP can be formulated as special variants of vector BPP.
We introduce a novel model to solve packing problems by first encode the properties and dominant constraints by GCN to generate the connectivity probabilities of different items, and decode the best solution according to the particular attributes of one instance. As far we know, we are the first to propose a learning-bast method solve complex vector BPP.
We conduct extensive experiments on various settings of CCBPP synthetic datasets and real-world OCP datasets, and the results show that our algorithm can obtain better solutions than other benchmarks, while also spending less time.
RELATED WORK
The ID bin packing problem (IDBPP) is one of the most well-known problems in combi- natorial optimization, and related research dates back to the 1960s (Kantorovich, 1960). Due to the NP-hard nature of IDBPP, many heuristic approximation algorithms have been designed and their worst-case performance analysis has also been explored (Coffman et al., 1996). For example, the Next Fit (NF) algorithm, the First Fit (FF) algorithm, and the Best Fit (BF) algorithm are the most well-known greedy algorithms to solve 1DBPP
IDBPP
2

---

Published as a conference paper at ICLR 2024
CCBPP CCBPP is special variant of vector BPP. Many authors have studied the CCBPP and proposed various algorithms to solve it. Shachmai & Tamir (2001) introduced the CCBPP with applications to data placement problem. Later on, Xavier & Miyazawa (2006) presented vari- ous approximation algorithms for the online and offline versions of CCBPP which is motivated by applications video-on-demand systems. Shachnai & Tamir (2002) presented algorithms for the online CCBPP problem when all items have unit sizes. Epstein et al. (2010) followed up on the previous works that improved upon existing algorithms and offered study of the approximation of the CCBPP. Lin et al. (2013) proposed heuristic approach for the online version of this problem. Most of these works focus on specific application of CCBPP, and they mainly provide the the- oretical analysis of the approximation scheme, while our method is a learning-based algorithm on general CCBPP. Recently, Borges et al. (2020) presented a Branch-and-Price framework to solve the CCBPP with two different branching schemes, da Silva & Schouery (2023) proposed branch-and- cut-and-price framework to solve cutting stock problems including CCBPP. These two frameworks exact algorithms, which are different from ours.
Learning-basse methods to solve BPP mainly focus on geometric BPP like offline and online 3D bin packing problems. Duan et al. (2018) proposed multitask frame- work based on Selected Learning to solve 3D flexible bin packing problem. Zhao et al. (2021a); Jiang al. (2021) leveraged deep reinforcement learning (DRL) method to solve online 3DBPP. Later, Zhao et al. (2021b) tried to enhance the practical applicability of online 3DBPP via learning on packing configuration trees. For offline settings of BPP, Zhang et al. (2021) proposed a new end- to-end learning model based on celf-attention-basee encoding and DRL algorithms for BPP, and Zhu al. (2021) proposed a data-driven tree search algorithm (DDTS) tackle the large-scale offline 3DBPP.
Neural methods for BPP
3 PROBLEM DESCRIPTION
Bin Packing Problem In the Class-Constrained Bin Packing Problem, given positive integers B, C, Q and a set (1,..., of items along with their size 8; N+ and class & E [1,...., Q} of item i, one must partition the set of items so that the sum of the item sizes in each part at most B and the number of different classes in each part is at most C while keeping the number of parts to a minimum. Thus, B is the size of the bin, C' is the number of different classes that a bin can hold and Q is the number of classes of all the items. The objective of CCBPP is to minimize the number of bins: minimize Σラ Vj.
Single-class constrained BPP and multi-class constrained BPP are two kinds of general CCBPP. In single-class constrained BPP, one item belongs to only one class, Data placement (Golubchik et al., 2000) and Production planning (Davis et al., 1993) are typical single-class constrained ver- sions of BPP. Multi-class version means one item belongs to multiple classes, Co-Painting (Peeters & Degraeve, 2004) and Manufacturing Order Consolidation Problem discussed below are typical applications of multi-class constrained BPP.
Order Consolidation Problem The Manufacturing Order Consolidation Problem is practical application of CCBPP in the domain of supply chain management which will also be discussed in this paper. Specifically, a manufacturing order (item) involves multiple components (classes) sup- plied by component feeder. The feeder has a fix-size thus it can only provide limited KINDS of components in one production process. Various orders can be combined into a new order (packing into a bin) to be produced, as long the total kinds of components required for their production do not exceed the feeder's supply capacity. The primary objective of OCP is to minimize the to- tal amount of orders after the consolidation process, which can greatly save time for equipment switching and improve productivity. More details of OCP can be found in Appendix B.2.
4 METHODOLOGY
4.1 FRAMEWORK
The overview of our framework is illustrated in Fig. 1. The input data is the properties of items that should be packed, e.g. the classes and sizes of items in CCBPP or the size of components one order contains in OCP. Firstly, construct a graph according to the variables and constraints of
3

---

Published as a conference paper at ICLR 2024
the problems, and then the imput graph is encoded by well-defined Graph Convolution Network to generate a heat-map, which represents the probabilities of items packing together. Cluster Decode is then leveraged to decode the heat-map into sequence format and output the final solution according to the characteristics of the particular sample with Active Search. In the following sections, we will introduce the Encoder and the Decoder in detail.
Edge
Comontioo Hus
Farking Sequiiia
Palliag Silakon
Packing Solation
Arsetto
Mguu Ne cliedd Facumators
Grophe
Sctive
Calculate Cost Clel -Mel
toleting
A00 A, (005)) 1/V ink
(a) Encoder
(b) Decoder
An illustration of the Encoder and the Decoder. The Encoder takes the well-constructed graph as input and outputs the heat-map which shows the probabilities of items packing together. The Decoder decodes the heat-map into a packing sequence, along with the Active Search fine- tune the result according to the characteristics of the input instance.
Figure 2:
4.2 ENCODER
In the domain of CCBPP, it is essential to acknowledge that various items may share the same class, implying relationships between them. Since graph is structure amounting to a set of objects in which some pairs of the objects are in some sense "related" (Fraughnaugh, 1997), it can be leveraged to represent this problem where these items are the vertices and their class relationships the edges. This approach enables to harness the power of Graph Convolutional Network as our learning model, allowing to effectively capture the intricate patterns inherent in CCBPP. GCN uniquely equipped to leverage both the attributes of vertices and the connections between them, making them a well-suited choice for addressing the complexities of this problem. The details of the Encoder shown in Fig. 2a.
The network is trained by supervised learning and the output the network is the heat-map. The structure of GCN and the training details will be presented in the following.
4.2.1 GRAPH CONVOLUTION NETWORK
We format the CCBPP as a full connected undirected graph EV containing the node set V and edge set E.
In our GCN input, node attributes v,, E Rd represent item properties, such as size and class. Edge attributes Ze R represent the relationships between items. Similar class affiliations suggest tendency for items to be packed together, hence we use class cosine similarities as edge features. To account for items without shared classes, zero cosine similarities
replaced with small constant c. The GCN output provides probabilities of two items being packed together. At the beginning, the node inputs 2, and the edge inputs F, are linearly projected into different vectors, af R and eL E " respectively, H is the feature dimension, i V and (i.j) E.
2 = Ay + by
(I)
0 A + b
(2)
where A, E HxD and A E "x1 Then the projected node and edge embeddings fed into L Graph Convolution layers. Let of and e/ denote the node feature vector and the edge feature vector respectively, the features at layer I can be defined as follows:
4

---

Published as a conference paper at ICLR 2024
attnl exp(Woee 2
Σ
exp (ep(Wo (-1)
(3)
(Lm))E
of of o ReLU(BN(WW
Σ
attny 3 1)
(4)
(Lm)EE
e = o ReLU W/o W
(5)
where W _ O represents the element-wise multiplication and @ represents the clement-wise division. Skip-connection layer (He et al., 2016) and Batch Normalization layer (loffe Szegedy, 2015) are consisted in Equation (4) and (5). The structure of GCN is motivated by Bresson & Laurent (2018).
The last layer edge embedding o then leveraged compute the probabilities of different items being packed together, which can also be treated as a heat-map over the connectivity matrix of different items. The heat-map output is widely used solve Traveling Salesman Problem (TSP) (Fu et al., 2021; Joshi et al., 2019), one of the most well-known CO problems. The packing probability Pi.j of item and item can be calculated follows:
Pi. (ep(ReLUWWoe))
(6)
exp(ReLU(Woet))
where W6 E I8 HxH and Pij E [0, 1].
4.2.2 NETWORK TRAINING
The network is trained via supervised learning and the ground-truth label can be generated through cutting stock (Gilmore & Gomory, 1961), which will be discussed in detail in Appendix D.I. The ground-truth labels can then be converted into a connection matrix where each element Ps.5 denoted whether item and item j are packed into one container, for true and for false, and Pt.j. (i. E E is the output of GCN.
In order better get cluster characteristics of the heat-map. the loss should contain both the pre- diction errors and cluster biases. Specifically, the loss function includes two parts, the weighted cross-entropy loss Lee and the modular loss Lmm
Tee
Σ Pr.s log pi + (1 -Di.)) log(1 pi.j)wo
V
1 V|V Pl.j Pi.j Pi.
Σ
Lm
Lee tries calculate the distance between the predicted probability and the ground-truth value. To avoid the positive and negative sample imbalance, we weighted Teee where wo = N2-2N and
N²
X² wi = 2N We and Wi are balanced coefficients relative to the edges belonging or not belonging to the ground-truth (Liu & Zhou, 2007). Minimizing I.m means maximizing the probabilities that should be packed together indicated by ground-truth, which leverages modularity Louvain (Blon- del et al., 2008). Modularity measures the degree which items in the same cluster are more densely connected than they are to items in other clusters, which is consistent with the objective of packing problems. The overall loss is defined as Liot Lee XLm where coefficient that balances the two losses.
4.3 DECODER
The heat-map generated by GCN encapsulates valuable cluster information on the items in the CCBPP. It provides probabilistic indications of item associations, with higher probabilities reflect- ing stronger correlations. Motivated by the First Fit (FF), the well-known greedy algorithm to solve 1DBPP, we first convert the heat-map into permutation that determines the packing sequence, then
5

---

Published as a conference paper at ICLR 2024
the FF algorithm is utilized generate the final packing solution. Decoding the heat-map into quence also makes possible to optimize the solution via reinforcement learning (RL), which will be discussed in Section 4.3.2.
The whole decode procedure illustrated in Fig. 2b. In the beginning. several sequences are sampled from the generated heat-map by the Cluster Decode algorithm, which is highly parallelized. Following this decoding phase, the bin packing results are subsequently derived from the packing sequences via FF. The best result will be chosen and the network will be updated by backpropagation of the selected solution, hence the generated heat-map will be changed. After several rounds of network updates, the quality of the packing solution will be significantly improved.
4.3.1 CLUSTER DECODE
Since we obtain the packing probabilities according to the heat-map, decoding strategies can be leveraged to generate sequence from the heat-map matrix, and the final solution is then obtained by FF. While greedy decoding and sample decoding. commonly employed in TSP, typically focus on the last item and overlook other items, packing problems require comprehensive consideration of all packed items and the aggregation of relevant information. Cluster algorithms such as K-Neurest Neighbors can be leveraged to divide the items into several parts, but the divided parts of items may not be able to be packed in one bin, thus the final solution may be very different from K.
Bix
t1.
the
Weight Unpached
Select Strengest Probabilitees
Selocted
Figure 3: Procedure of the Cluster Decode
To address the packing constraints more effectively, the Cluster Decode algorithm is proposed to make full use of the generated heat-map and the relevant packing status. The algorithm ranks the items one by one, with each item's selection being determined by the maximum average connectivity probabilities with the items already placed in the latest bin, as depicted aggregation information in the heat-map is better represented in the form of a sequence, so that the constraints will be considered during the decoding process while the information of the packing bins is also considered. The detailed Cluster Decode algorithm is described in Appendix C. At the beginning, one item is picked at random and the index set as the first the sequence, the item is put into the jth bin via FF. Then all bins traversed and the latest open the newly selected item has the greatest possibility of being packed in the latest bin, the next item is picked by the average connectivity probabilities of all the items in Bn, represented by heat-map P. The sequence is generated until all N items are visited.
Fig.
this way, the
B, is found. Since
4.3.2 ACTIVE SEARCH
should be noted that while Cluster Decode provides both the packing sequence and the corre- sponding packing solution, there exists a notable discrepancy between the obtained solution and the optimal solution since the distribution of the training samples and the test samples may not be iden- tical. In order to get more search guidance and react towards the solutions decoded by the Cluster Decode, reinforcement learning can be leveraged to fine-tune the packing sequence according to the solutions seen far. Compared with supervised lcarning algorithms, reinforcement learning algorithms are guided by environmental reward signal so that allows near-optimal solutions to be found without expert guidelines.
Motivated by Yu et al. (2016) and Hottung et al. (2022), we exploit RL-based Active Search to fine- tune the pre-trained network. Since only few samples are leveraged for fine-tuning, froze most of the graph network and update only one layer embedding with RL loss function based on Policy Gradient (Williams, 2004). For each instance, solution æ be repeatedly sampled by Cluster

---

Published as a conference paper at ICLR 2024
Decode whose cost is (()) -) the opposite number of the occupied bins. The no-fixed parameters w are adjusted to minimize L(w):
((w) E=[(C(m) b (o
where 6 denotes the average reward of the batch data and pa (T( = I pe pa w) (Kwon et al., 2020), Po here is the probability of of generating a packing sequence based on the heat-map according to the Cluster Decode strategy mentioned above. Note that only the parameters w are instance specific, while all other model parameters are identical for all instances.
PERFORMANCE EVALUATION
In this section, we first report the performance of our proposed Encoder- Model in solving two kinds of general CCBPP, single-class constrained BPP and multi-class constrained BPP as de- scribed in Section 3. Then we will conduct a case study of one typical application of general CCBPP, the Manufacturing Order Consolidation Problem. Finally, we conduct ablation studies to verify the effectiveness of the Encoder, Cluster Decode algorithm, and the effect of Active Search itcrations.
We compare our algorithm with different heuristic algorithms and learning-bases algorithms. The baseline heuristic methods include Random packing, First Fit Decreasing (FFD), which is one of the most well-know greedy algorithms to solve IDBPP, and two typical population based algorithms, Genetic Algorithm (GA) and Ant Colony Optimization algorithm (ACO) implemented by scikit- opr', whose modeling details included in Appendix 1. As for learning-based methods, since there is no learning-basse -based related work about CCBPP, we re-implement Pointer Network ( (Vinyals al., 2015) for CO problems with Policy Gradient (Bello al., 2017) (PointNet in the following tables) as a baseline. The Greedy and Sampling are strategies to obtain solution after Cluster Decode. Greedy strategy means we select the best solution after Cluster Decode, and sampling means we sample 32 solutions during the Cluster Decode and report the best. GCN-Cluster in the tables below means the Sercoder-Decoder Model in this paper, Active Search (AS) is also compared with the Greedy and Sampling strategies. Note that exact solvers like OR-tools (Perron & Furnon, 2022) and gurobi (Bixby. 2007) cannot obtain the solution within a limited time. For example, costs several hours to obtain solution of single-class constrained BPP when Q = 10, C' 3. and besides, it is difficult to reproduce the exact algorithms provided in Borges et al. (2020) and da Silva & Schouery (2023), so we omit these results. The experiments are conducted on Linux server with GeForce_RTXs GPU and AMD EPYC 7542 32-Core Processor CPU@2.9GHZ
5.1 GENERAL CLASS-CONSTRAINEE BIN PACKING PROBLEM
For general CCBPP, we conduct numerical experiments with simulated data. Since there are no known benchmarks for the CCBPP available in the literature, the datasets are generated following the convention of Borges et al. (2020) and da Silva & Schouery (2023). The sizes of items are random integers ranging from 10 to 25 while the bin capacity B is 100. In single-class version, the number of different classes available Q E {10, 20, 30} and the class constraint value C' E [3,5). 5}. In the multi-class version, the class constraint value C. is 5. the number of different classes available Q E (10, 20} and each item belongs to M classes, M E {2, 3}. 6400 training instances and 200 test instances are generated via the cutting stock algorithm. For all the training and testing instances of general CCBPP, the optimal value is 20. Details of data generation are described in Appendix D.
Table and Table 2 shows the performance evaluation of single-class constrained BPP. It can be shown that for all the settings, our algorithm outperforms all other baselines. FFD is not suitable for CCBPP and performs even worse than Random Packing in most cases. Heuristic methods GA and ACO also obtain competitive solutions, but the time cost is higher. Note that the scikit-opt we use here is implemented with parallelization and caching techniques, so it runs more efficiently. Point Networks have achieved competitive performance on many routing problems (Bello et al., 2017), they do not perform well on our problems probably because the sequential decision model does not catch the relationship between items. Compared with Greedy and Sampling strategies, Active Search with RL further improves the quality of the solution by fine-tuning the network according to the characteristics of each test instance, meanwhile, the running time is also getting longer.

---

Published as a conference paper at ICLR 2024
Table 1: Results of single-class constrained BPP when C' = and Q {10, 20, 20,30). Time(s) the average time to solve single instance and the unit is second, Bins is the average cost of total bins, Gap refers to the gap between the optimal solution.
Q = 10
Q = 20
Q = 30
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
21.395
6.98%
0.0095
22.04
10.20%
0.0117
22.365
11.33%
0.0106
FFD
21.58
7.90%
0.0109
22.375
11.88%
0.0109
23.09
15.45%
0.0126
GA
20.99
4.95%
14.51
21.00
5.00%
16.43
21.00
5.00%
17.86
ACO
20.81
4.05%
92.00
20.935
4.68%
93.89
21.00
5.00%
96.85
Gorreyytt
21.41
7.05%
0.0181
21.88
9.40%
0,0181
22.11
10.33%
0.019
Paampingg Sampling
21.07
5.35%
0.40
21.03
5.15%
0.41
21.06
5.30%
0.67
GCN-Cluster. Greedy
21.00
5.00%
0.045
21.03
5.15%
0.051
21.29
6.45%
0.036
OCN-Cluster, Sumpling
20.965
4.83%
0.40
21.00
5.00%
0.41
21.00
5.00%
0.62
GCN-Cluster, AS(Ours)
20.74
3.70%
14.14
20.91
4.55%
10.52
20.98
4.90%
14.05
Table 2: Results of single-class constrained BPP when C' = 5 and Q E {10, 20, 30}
Q 10
Q 20
Q = 30
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
21,005
5.03%
0.0095
21.02
5. 5.10%
0.0120
21.03
5.15%
0.0103
FFD
21.00
5.00%
0.0118
21.08
5.40%
0.0098
21.405
7.03%
0.0109
GA
20.63
3.15%
13,96
20.86
4,30%
14.47
20.935
4.68%
15.42
ACO
20.785
3.93%
93.11
20.85
4.25%
105.08
20.83
4.15%
93.82
PointNet-Greed
21.07
5.35%
0.0156
21.00
5.00%
0.023
21.21
6.05%
0.0156
PoimtNet-Sampllng
20.99
4.95%
0,33
21,00
5.00%
0.7609
21.00
5.00%
0.667
GCN-Cluster, Greedy
21.00
5.00%
0.036
21.00
5.00%
0.055
21.00
5.00%
0.0052
GCN-Cluster, Sumpling
20.945
4.73%
0,23
20,99
4.95%
0.73
20.99
4.95%
0.44
GCN-C CCN-Cluster. AS(Ourr))
20.47
2.35%
10.14
20.77
3.85%
10.52
20.82
4.10%
14.05
Table 3 shows the results of multi-class constrained BPP, our algorithm outperforms all other base- lines for all the settings, with more significant leading than that of single-class constrained BPP. Compared to the results of single-class constrained BPP in Table 2, the gap between all results and the optimal is larger and gradually increases as M becomes larger. The results illustrate the diffi- culty of solving the multi-class version of CCBPP, especially when M gets larger. From the results listed above, can be inferred that our model has more prominent results when the input problem has more complex constraints such as multi-class constrained BPP.
Table 3: Results of multi-class constrained BPP when C 5, Q (10 and M E (2.3)
Method
10,C 5, Mf
5,
Q
20, 5 M
Bins
Gap
Timefs)
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Bins
Gup
Time(s)
Kandom
21.305
9.03%
0.0169
25.33
36.65%
0.0161
25.82
29.10%
0.0107
43.36
116.30%
0.0255
FED
22.105
10.53%
0.022
26.50
32.50%
0.0256
27.67
38.35%
0.026
44.26
121.30%
0.0354
GA
4.98%
52.29
21.785
27.875
39.38%
ACO
20.97
4.85%
106.83
21.78
8.90%
131.36
21.93
9.65%
112:22
26.83
34.15%
119.64
Poletyet-CGreedy
21888
9.40%
0,0153
25,898
17.98%
0.872
25.11
25.55%
0,029
41.26
106.309
0.044
PointNet Sampling
21.00
5.00%
0.53
23.36
16.80%
0.7208
23.70
18.50%
0.8537
37.48
87.40%
1.46
Clnser Cready
11.00%
25.303
17.88%
16.10%
52,095
030739
SCN-Cluster, Sampling
20.99
4.95%
0.462
22,275
11.38%
0.640
22.095
10.18%
0.726
28.38
11.90%
L111
GCN- CCNN-Clster, AStOurr)
20.91
4,55%
40.04
21.62
8.10%
38,77
21.515
7.58%
41.6
25.915
29.58%
58.21
5.2 CASE STUDY: ORDER CONSOLIDATION PROBLEM
For the Order Consolidation Problem, our datasets consists of the synthetic dataset with ground- truth and real supply chain dataset in September 2022. The real-world data contains orders in 24 days of September and orders ranging in size from 123 to 178 each day. The synthetic dataset is generated via cutting stock algorithms (Gilmore & Gomory, 1961) based on real-world data, which means the items in a sequence are created by "cutting" the bin so that the sequence can be perfectly packed and restored to the bin. Since the space utilization is 100%, the packing result can be treated as the ground-trun truth. In this experiment, we extract real orders to fulfill the feeder to get perfect space utilization, and the number of bins is set random from 3 to 14 to make the order numbers similar to the real ones. We generate orders of 2000 days for training and orders of 200 days for testing, the average ground-truth of the test labels is 9.11.
8

---

Published as a conference paper at ICLR 2024
The results of synthetic data and real-world data listed in Table 4. For two kinds of data, only one GCN is trained with 2000 synthetic data by cutting stock algorithms, and the trained network is employed on these two datasets, test synthetic datasets with 200 instances and real-world datasets with 24 instances. Since we already know the ground-truth of the synthetic data, the gap between different methods and the optimal solution be obtained, whereas the gap of real-world data is omitted because the true labels cannot be calculated.
Table 4: Results of OCP on different datasets
Synthetic data
Real-world data
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
11.705
28.48%
0.038
17.68
0.050
FFD
11.865
30.24%
0.041
17.79
0.052
GA
10.93
20.00%
98.01
17.00
/
180.02
ACO
9.76
7.13%
113.16
15.33
233.42
PointNet-Grredy
12.53
37.54%
0.05
18.88
0.42
PoimtNet-Sumpling
11.66
28.00 28.00%
1.5
17.62
12.5
GCN-C Cluster, Crredd
10.08
10.65%
0.043
14,92
0,078
GCN-Cluste Clusterr Sampling
9.610
5,49%
0.60
14.46
0,52
GCN-Cluster, AS (Ours)
9.325
2.36%
21.6
14.29
21.0
Results from Table show that algorithm outperforms all baselines. Although the running time of Random and FFD is short, the solution quality does not show any advantages. The time cost of heuristic methods GA and ACO is too high and the results are also not competitive. GCN can exhibit a high degree of clustering so it has shown good performance in our experiments. Active Search with RL further improves the quality of the solution by fine-tuning the network according to the characteristics of each test instance, meanwhile, the running time is also getting longer. Our algorithm can get an average of 9.325 bins with gap of the best solution of 2.36% on synthetic data and average of 14.29 bins real-world data, respectively. Compared with the results general CCBPP, our model also shows significantly promising performance in practical applications.
5.3 ABLATION STUDIES
We evaluate the effects of different parts of our Encoder-Decodee Model, and the results as follows:
Appendix E.1.1 The heat-map generated by the GCN Encoder provides more information than the others for the final result.
Appendix E.1. The Cluster Decode algorithm does have a very positive impact on the performance of the whole framework.
Appendix 1.1. The learning curve of Active Search decreases more and more slowly when the number of iterations increases. A compromise may need be made between solution quality and running time when the algorithm is applied in practice.
6 CONCLUSIONS
In this paper, we introduce and formulate a special variant of complex vector BPP, the Class- Constrained Bin Packing Problem, which has not been extensively studied in existing operational research. In particular, we propose a learning-based Encoder-Decoder Model to solve the BPP with multiple properties and more complex constraints. The GCN Encoder generates heat-map that shows the probabilities of items packed together, then the Cluster Decode is leveraged to se- quential decode the heat-map and fine-tune the solution according to the characteristies of the test sample with Active Search. Extensive experiments demonstrate that our methodology obtains high- quality solutions with very small gap between the optimal while performing better than existing approaches various settings of general CCBPP. Additionally, experiments also demonstrate that our Secoode--eccode Model shows promising performance on OCP, one practical application of CCBPP. For future research, are interested in trying to improve the generalities of our algorithms to different sizes and distributions of CCBPP. Applying our Deoooddr Model to other ap- plications of CCBPP is also interesting direction.

---

Published as a conference paper at ICLR 2024
REFERENCES
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. ArXiv, abs/161 1.09940, 2017.
Bob Bixby. The gurobi optimizer. Transp. Re-search Part B, 41(2):199-17,,22 2007.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks, Journal of statistical mechanics: theory and experiment, 2008 (10):P10008, 2008.
Yulle G. F. Borges, Flávio Keidi Miyazawa, Rafael Crivellari Saliba Schouery, and Eduardo C. Xavier. Exact algorithms for class-constrained packing problems. Comput. Ind. Eng., 144: 106455, 2020.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets, 2018.
Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learn- ing to aolve large-scale tsp instances. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp.
PMLR, 25-27 Apr 2023.
Henrik I. Christensen, A. Khan, Sehastian Pokutta, and Prasad Tetali. Multidimensional bin packing and other related problems A survey. 2016. URL https: //tp//apppi.pee/ / semanti www.setiaccaaollaa...... cacholar. Brg/Corpuse 9048170.
Henrik I. Christensen, A. Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev., 24:63-79, 2017. 2017 URL
https: / /api..... semanticschol
org/ Corppsrrpssp 32825008.
Egj Coffiman, M. Garey, and D. Johnson. Approximation algorithms for bin-packing an updated survey. PWS Publishing Co., 1996.
Igor Crévits, Said Hanafi, Ali Ridha Mahjoub, Raouia Taktak, and Christophe Wilbaut. A special case of variable-sized bin packing problem with color constraints. 20/9 6th International Confer- ence on Control, Decision and Information Technologies (CoDIT), pp. 1150-1154, 2019. URL https: /aa::///pppi.e semant icscholars pegg/CorpusDD 2018333900
Renan F. F. da Silva and Rafael C. S. Schouery. branch-and-cut--nd--pie algorithm for cutting stock and related problems, 2023.
Wayne J. Davis, Duane L. Setterdahl, Joseph G. Macro, Victor Izokaitis. and Bradley Bauman. Recent advances in the modeling, scheduling and control of flexible automation. Proceedings of 1993 Winter Simulation Conference (WSC 193), pp. 143-155, 1993.
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang. Yinghui Xu, and Jiangwen Wei. A multi-task selected learning approach for solving 3d flexible bin packing problem. arXiv preprint arXiv: 2018
Leah Epstein, Csanád Imrch, and Asaf Levin. Class constrained bin packing revisited. Theor. Comput. Sci., 411:3073-3089 2010.
Kathryn Fraughnaugh. Introduction to graph theory. Networks, 30:73, 1997.
Zhang-Hur Fu, Kai-Bin Bin Qiu, and Hongyuan Zha. Generalize small pre-trate pre-trained model arbitrarily large tsp instances. In AAAI, 2021.
Rce Gilmore and Gomory. A linear programming approach to the cutting stock problem. Operations Research, 1961.
Leana Golubchik. Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, and An Zhu. Approx- imation algorithms for data placement on parallel disks. ACM Trans. Algorithms, 5:34:1-34:26, 2000.
10

---

Published as a conference paper at ICLR 2024
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
André Hottung, Yeong-Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems, 2022.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, 2015.
Yuan Jiang, Zhiguang Cao, and Jie Zhang. Learning to solve 3-d bin packing problem via deep reinforcement learning and constraint programming. IEEE transactions on cyberneties, 2021.
C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv:1906.0122) [cs, stat], 2019.
Leonid V. Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6:366 422, 1960.
Hans Kellerer and Ulrich Pferschy. Cardinality constrained bin-packing problems. Annals of Operations Research, 92:335-345 1999. URL https:h/apaa......e sttpppp...smmiccccclllaaaaaaaaaa CorpusID:2896329L..
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2019.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Seungjai Min, and Youngjune Gwon. Pomo: Policy optimization with multiple optima for reinforcement learning. ArXiv, abs/2010.16011,, 2020.
Dongda Li, Changwei Ren, Zhaoquan Gu, Yuexuan Wang, and F. Lau. Solving packing prob-
lems by conditional query learning. 2019, URL https: //ap://appppp semanticscholliee aorlllrrrrrr//rooo .rrg/
CorpusID: 2119599622
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In NeurlPS, 2021.
Tsai-Duan Lin, Chiun-Chich Hsu, and Li-Fu Hsu. Optimization by ant colony hybrid local search for online class constrained bin packing problem. Applied Mechanics and Materials, 311:123- 128, 2013.
X. Y. Liu and Z. H. Zhou. The influence of class imbalance on cost-sensitive learning: An empirical study. In International Conference on Data Mining, 2007.
Manuel López-lbãñez. Ant colony optimization. In Annual Conference Genetic and Evolutionary Computation, 2010.
Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In NeurlPS, 2021.
Melanie Mitchell. An introduction to genetic algorithms. 1996.
Marc Peeters and Zeger Degraeve. The co-printing problem: A packing problem with color constraint. Oper. Res., 52:623-633. 2004.
Laurent Perron and Vincent Furnon. Or-tools, 2022. URL httttt//deeeelpperrss gow.ge...lper...oge........ com/ opt imization/.
Hadas Shachnai and Tami Tamir. Polynomial time approximation schemes for class-constrained packing problems. Journal of Scheduling, 4:313-338, 2001.
Hadas Shachnai and Tami Tamir. Tight bounds for online class-constrained packing. Theor. Comput. Sci., 121:103311 2002.
11

---

Published as a conference paper at ICLR 2024
Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-sage: Scale neta-learing scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. arXiv preprint arXiv:2330.0000:0
2023.
Laurens van der Maaten and Geoffrey E. Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9:2579-2605, 2008.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NIPS, 2015.
Ronald J. Williams. Simple statistical cradient-followingg algorithms for connectionist reinforcement learning. Machine Learning. 8:229-256, 2004.
Honguk Woo, Hyunsung Lee, and Sangwoo Cho. An efficient combinatorial optimization model using learning-to-rank distillation. CoRR, abs/2201 .00695, 2022. URL https://arxiv
org/abs/22/ 22011 00695.
Eduardo C. Xavier and Flávio Keidi Miyazawa. The class constrained bin packing problem with applications to video-on-demand. Theor. Comput. Sci., 393:240-259, 2006.
Zhen Xiao, Qi Chen, and Haipeng Luo. Automatic scaling of internet applications for cloud
computing services. IEEE Transactions Computers, 63:1111-1123, 2014. URL https: //api.
wwtpllarrrrr//a.eo wwwp/ooorroi.ie.....o :8119779:1
Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. Seggan: Sequence generative adversarial nets with policy gradient. In AAAI Conference on Artificial Intelligence, 2016.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Systems, 33:1621-1632, 2020.
David Zhang, Corrado Rainone, Markus Peschl, and Roberto Bondesan. Robust scheduling with gflownets. arXiv preprint 2tt.:23322.044466 2023.
Jingwei Zhang, Bin Zi and Xiaoyu Ge. Attend2pack: Bin packing through deep rein-
forcement learning with attention. ArXiv, abs/2107.04333, 2021. URL https://aa //api. semanticscholas
Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. Online 3d bin packing with con- strained deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 741-749, 2021a.
Hang Zhao, Yang Yu, and Kai Xu. Learning efficient online 3d bin packing on packing configuration trees. In International Conference on Learning Representations, 2021b.
Qianwen Zhu, Xihan Li, Zihan Zhang, Zhixing Luo, Xialiang Tong, Mingxuan Yuan, and Jia Zeng. Learning to pack: A data-driven tree search algorithm for large-scale 3d bin packing problem. Proceedings of the 30th ACM International Conference on Information & Knowledge Manage- ment, 2021.
12

---

Published as a conference paper at ICLR 2024
A MORE INTRODUCTION OF CCBPP
A.1 FROM ACADEMIC VIEW
Bin packing problem (BPP) can be divided into two main categories, geometric BPP (2D and 3D BPP), and vector BPP (Christensen et al., 2017). The difference between these two problems is whether we should consider the geometrical constraints. In the vector BPP research field, there are plenty of works proposed to solve vector BPP with different constraints (Christensen et al., 2017; Epstein et al., 2010; Kellerer & Pferschy, 1999). Among them, Glass-Constrrinee BPP a typical variant. These research mainly focus approximation heuristics (Shachnai & Tamir, 2001) exact solutions (Borges et al., 2020). Unfortunately, corming-baseds methods have not been applied in this field so far.
A.2 FROM APPLICATION VIEW
In general. BPP can be viewed as resource allocation problem with resources from two kinds, incompatible resources and compatible resources (shared resources). The vanilla vector BPP only considers incompatible resources, i.e. all items are consuming accumulative resources. Actually, there are plenty of real-world applications corresponding an operation machine can only process 2 kinds of operation (compatible resource) with limited materials (incompatible resources) (Crévits et al., 2019). This is quite common in many real-world applications, list some of these follows.
both kinds of resources. For example,
Automatic Scaling in Cloud Computing (Xiao al., 2014). One server hold several kinds of applications, each is consuming computing resources S.PU/Memory/Banwwithh)
Daleo--n--eemnn (Golubchik et al., 2000; Xavier & Miyazawa, 2006). The network loading incompatible, but the data-file is shared among different inlinc-users..
Data-Placement Problem
Production Planning (Davis et al., 1993; Peeters & Degraeve, 2004). The raw material demand by each order is incompatible, while the production can be operated on the same machine from different orders.
Co-painting Problem (Peeters & Degraeve, 2004). Item consuming the same color can share the same painting oil container while with different demand in amount.
Steel Mill Slab Problem (Crévits et al., 2019). Different orders with the same production route can be operated on the same machine long as their cumulative length does not exceed the slab-size.
These applications listed above are all typical Class-Consiin Constrained Bin Packing Problems. The opti- mization of these applications can bring numerous economic value by improving the efficiency.
13

---

Published as a conference paper at ICLR 2024
B MILP FORMULATIONS
B.1 CCBPP
We present below an Integer Linear Programming formulation for the CCBPP as following Borges al. (2020), in which we consider 2D vector æ of size N x N, 2D vector of size N and a vector of size N, all of the binary variables such that for all i E {1, N.. and j E {],,.., N}. Fiy a binary variable to indicate whether the ith item is packed in the jth container and yj is also binary to show if the jth container is occupied. 2jk is 1 if class k is included in the jth container for j E (1, ...: N). For single-class constrained BPP, 2jk one-hot vector, and for multi-class constrained BPP, there are M ones in 2jk for (1, [1....N] N).
minimize Σ Uj
subject to
N
8 Tij S j E (1,
E=1
2yh C A j E (1,2,3..., N}
Fij S Zjo v i,j E 21, N)
N
Tij 1 A iE (1,2,3..., N}
j=1
B.2 OCP
The details order consolidation are depicted Fig. 4, A manufacturing order (item) involves multiple components (classes) supplied by component feeder. The feeder has fix-size thus it can only provide limited KINDS of components one production process. Various orders can be combined into new order (packing into a bin) be produced, components required for their production do not exceed the feeder's supply capacity. The primary objective of OCP to minimize the total amount of orders after the consolidation process. The consolidation of orders will significantly reduce the equipment switching time, making it imperative minimize the number orders after consolidation optimize operational efficiency.
long as the total kinds of
Notably, the OCP presents heightened complexities compared to the general CCBPP due to the involvement of a substantial number of components and the potential inclusion of multiple com- ponents within single order. This distinctive characteristic renders the attainment of high-quality solutions for OCP more challenging comparison to the general CCBPP
Components with Different Sizes
Fixed Size of C Components Feeder (ppaack)
Components
Ordlor 001
Oreior: 002
Ordor 00G
Order 004
Ord
Ortice 006
Orders
Consolidated Orders
Orter-001
Oxder-O0G
Oo
Ordar=002
Ordaa:00G
Figure 4: An illustration of OCP. Order-001 and 002, order-003 and 005, order-004 and 006 can be merged since the components collection after consolidation meet the constraints.
14

---

Published as a conference paper at ICLR 2024
The whole process of OCP is illustrated in Fig. 5, which depicts the scenario of multiple orders {I....,N) represented as printed circuit boards (PCBs) requiring the assembly of various compo- nents. The number of included components of all orders is Q At the beginning of the production process, blank PCBs are placed onto the working space a Surface Mount Technology (SMT) machine. Subsequently, robotic arm picks up corresponding components from the feeder, placing them onto the PCBs. After finishing the current order, the SMT will be reset and switched for the next order. Notably, each kind of component & occupies specific "bandwidth" 8y within the feeder. The feeder has fixed size C' in bandwidth thus it can only provide limited kinds of components for one production process, while the supply of each kind of component can be ample in amount (B x)), depicted in Fig. 5. Specifically, several orders can be combined into new order to be produced, as long as the cumulative bandwidth the component collections required for their production does not exceed the feeder's bandwidth limit C.
Companetta Foodir
5
Productimn Orders
Cemponent aardhowe
> Ample Supply Componeatss
NVLLE
Machine
Figure 5: Feeders in PCB consolidation process
N
minimize
Σ Vj
subject to:
2jk 8k S j f1.,, N}
k=1
Zij I 2jm 4 i,j E (1,2,3... N), E
N
Tij = ViE (1,2,3.., Σ
Compared with the formulation of CCBPP, the class order belongs to is subset, not value of 21, Q} which means one order may belong to multiple classes simultancously. The limit of shared resource B is equal infinity and there only class constraints in the problem.
15

---

Published as a conference paper at ICLR 2024
C DETAILS OF CLUSTER DECODE
Here we list the algorithm details Cluster Decode mentioned in Section 4.3.1.
Algorithm Cluster Decode
Require: The heat-map P E RNXN,, the remaining items List set L = {1, .... Nj. N empty bin set B1, B,,,,..... B =
Ensure:
the packing items' sequence 5
0 2: Randomly pop an item, from L
Initialize items sequence
3: Add item,'s 's index to the sorted
4: while L * 0 do
5: Pack item, into jth bin according to FF algorithm
6: Add the index of item; into Bj
7:
for m N...1 do
b. find the latest open bin
8: if Bm + 0 then
9:
break
end if end for
11:
Calculate the average connectivity probabilities of items in Bm score average(P(kkkk E Bm))
Get the item index i with the highest score (sgoe (k)lk 2)
14:
Pop the item, with index from L Add item,'s 's index to the sorted list
15:
16: end while
16

---

Published as a conference paper at ICLR 2024
D EXPERIMENT DETAILS
D.1 DATA GENERATION
All Classes
Full Bin
Cutting into Orders
Full Bin
3
5
7
Included Clasus
Cutting into Items
3 5
Figure 6: Ground-trutt label generation of CCBPP and OCP by cutting stock algotithm.
is difficult obtain optimal solutions by exact solvers like OR-tools since it costs almost several
hours to obtain one solution of single-class constrained BPP when Q 10, C = 3 in our settings. As result, we need to construct quantities of "perfect" solutions other ways. Motivated by item sequences generation for online 3D Bin Packing Problems (Zhao et al., 202 2021b;a), our ground-truth labels can also be obtained by cutting stock (Gilmore & Gomory, 1961).
For general CCBPP, we first generate a sequence of valid items whose size threshold is Smin Smax following uniform distribution and the sum of which is equal to the bin size B, as shown in Fig. 6. Then we randomly choose C classes over total Q classes and assign the C classes to the generated valid items. In this way, the items may be perfectly packed and restored to the bin, and the utilization is 100%. In all the single-class constrained BPP and multi-class constrained BPP settings, we generate 20 perfect sequences which means the optimal packing bin number of all the items 20. The number of items total 20 bins may vary different instances, we choose the maximum number of items in all instances N as the number constructed graph nodes and pad the other instances with O. The pseudocode of our dataset construction algorithm is described in Algorithm 2.
For OCP, we generate synthetic dataset according to the distributions of real-worke datasets. The real-world data contains orders in 24 days of September and orders ranging in size from 123 to 178 each day. The components in each order contain a range from 955 to 1234, and there total of 2480 components included in all orders. The sizes of different components occupied are ranging from to 6, and most of them are or 2. The maximum size of the feeder is 282, as shown in Fig. 6.
The distribution the real data may differ from the distribution of the generated data used to train the model. However, in practical applications, we analyze the distribution of real data as much as possible and fit the most approximate dataset for training.
D.2 EXPERIMENT HYPPER-PARAETTE
For the graph neural network, the number of GCN layers Lgen and the number of MLP layers Lmmp is 3. The learning rate Ir is 5e - 5 with le - weight decay, the 0 in edge features are replaced by 6 = 0.3, and the loss balance coefficient X = 0.3 Our network is trained for 20 epochs. It costs 2 hours to train the single-class constrained BPP and hours to train the multi-class constrained
BPP model.
For the Active Search, update the parameters of the MLP's last layer, while keeping other param- eters frozen. For sampling, 32 solutions per instance are sampled from the Cluster Decode procedure and report the best. The learning rate Ir is 5e 3 with 1e 4 weight decay, and for each instance, the search epoch is set as 30 for single-class constrained BPP experiments, and 50 for multi-class constrained BPP and OCP experiments.
17

---

Published as a conference paper at ICLR 2024
Algorithm 2
Dataset Construction
Require: Valid item size threshold Smin Smar, bin capacity B, number of classes one bin can hold C, total number of classes Q. number of cutting bins K.
1: function CONSTRUCTION OF ITEMS COLLECTION
2: for j= L..K do
3:
initialize the used space of one bin Sueed O, valid item list Lvalid 0 initialize class set Craisd which contains C? classes out of the total number Q while Sused Σ B do
4:
5:
6:
generate one item where the size 8; satisfies Smin I 8; S Smaz, and C₁ E Cealid
7:
if Sused + 8; B then
8:
Sused+ 84 add the item into Cealid
9:
10:
else if Sused + = B then add the item into Coalid break
12:
else
14:
Sused 0 Lvalid
15:
end if end while
16:
17:
end for
18:
return Loatid
19:
end function
For the baseline heuristic methods, the parameters of GA are 50 populations in the initial and 300 iterations. The distance matrix of ACO is set as the inverse value of the cosine similarity matrix and the number of populations and iterations are set as 50 and 100, respectively.
The parameters of PointNet are set as follows: the number encoding layers is 2, and the number of multi-head is 4. The learning rate Ir is 1e 4 with 1e 4 weight decay.
D.3 DETAILS OF BENCHMARK ALGORIHHMS
D.3.1 GENETIC ALGORITHM AND ANT COLONY OPTIMIZATION MODELING
Genetic Algorithm (GA) (Mitchell, 1996) is computational model searching for optimal solu- tions by simulating the natural evolution process with natural selection and genetic mechanism of Darwinian biological evolution theory. Genetic algorithms take all the individuals in kind of popu- lation and use randomization techniques to guide efficient search of an encoded parameter space. Among them, selection, crossover, and mutation constitute the genetic operation of the genetic al- gorithm. The parameter encoding, setting of the initial population, design of fitness function, design of genetic operation, and setting of control parameter, form the core of the genetic algorithm.
In computer science and operations research, the ant colony optimization algorithm (ACO) (López- Ibáñez, 2010) is probabilistic technique for solving computational problems that can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the be- havior of real ants. The cheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.
The output of both GA and ACO are sorted sequences. After the items' sequences are generated, different packing schemes such as First Fit (FF), Best Fit (BF), and Next Fit (NF) can be leveraged to pack the items in specific order so that the packing solution can be obtained. The input and output of GA are both full permutations of items to be packed and sizes and class information are needed to match the permutations to the final result. Specifically, M full alignments as initial population are randomly generated, and the maximum number of evolutionary generations T is set. Then we need to set the adaptivity function, whose input is the sequence and information of items and output is the packing solution. Finally, the loop ends when the genetic evolution repeats T rounds or reaches the iteration condition.
18

---

Published as a conference paper at ICLR 2024
X3
X4
<
X5
X2
Figure 7: A pointer network architecture introduced by Vinyals et al. (2015)
For the ACO algorithm, the inputs include information about the items and also the distance matrix, which indicates the likelihood of choosing a path, the shorter the path the more likely it is that two
items will be packed together. Here the distance matrix we set as the opposite number between the cosine similarity of each item class, i.e. the more similar the items are each other and the smaller the distance between them, the more likely they are to be packed together.
D.3.2 POINTNET MODELING
The Pointer Network is proposed leverage the attention mechanism to solve the sorting problem of an input sequence. The traditional seq2seq model is not able to solve the problem that the vocabulary of the output sequence changes with the length of the input sequence. In some tasks, the input is strictly dependent on the input, the output can only be selected from the input. In this case, the traditional seq2seq model ignores the priori information that the input can only be selected from the output. Pointer Networks elements and the input elements is calculated by the attention mechanism. The element with the largest attention value will be a pointer to point to the input element. Note that each input element can only be pointed to one time avoid the repetition output sequence.
proposed solve this problem. The relationship between the output
the output element. Actually, each output element is similar
PointNet is widely used in routing problems where the output can directly be treated as one per- mutation of the input nodes. In the packing problem, since one packing solution corresponds to varies output sequences, supervised learning is inappropriate for solving Reinforeement Learning provides an appropriate paradigm for training neural networks for combi- natorial optimization, especially because these problems have relatively simple reward mechanisms that could even used at test time (Bello et al., 2017). The input of the Pointer Network is N items along with the size and class information, and the output is one specific permutation of all items. The packing solution can finally be obtained with the aid of FFD.
BPP.
19

---

Published as a conference paper at ICLR 2024
E
MORE EXPERIMENT RESULTS
E. ABLATION STUDIES
E.1.1 BENEFITS THE ENCODER
The visualization of the heat-map is shown in Fig. 8. Orange points in Fig. 8 are the items visualized by t-SNE (van der Maaten & Hinton, 2008), embedding technique that is commonly used for the visualization of nigh-dimensional data in seatter plots, the grey lines of the right figure represent the true label, which means two items packed together in the optimal solution. The grey lines the left figure show the connection of items when the value of the heat-map is larger than 0.2. It can be seen that these two figures show great similarities, which means our heat-map contains crucial information on the true labels.
Link Strength Heatmap
Link Strength of labels
Figure 8: Visualization of heat-map
To verify the heat-map trained by GCN does have benefits to final result, we compare different kinds of heat-map along with the Cluster Decode proposed in the Section 4.3 along with Active Search, and Table 5 and Table 6 list the results of CCBPP and OCP, respectively. Equal probability here means the elements in the initial heat-map all equal Ωे and N is the number of items in one instance. Cos similarity in the following table is the cosine similarity of the class features of each item. PointNet (Vinyals al., 2015) here also leveraged the loss function is the same as ours. Results show the heat-map our GCN generated outperforms all the others both CCBPP and OCP while the time overhead differs very little. GCN is best suited to capture the relationships of the items, and the heat- heat-map map generated by GCN obtains more information via the true labels, thereby contributing significantly the final results.
Encoder output heat-map,
Table 5: Comparisons on different seat-maps on CCBPP
Q= = 10, C = 5
Q = 20, C 5
Method
Gap
Time(s)
Gap
Time(s)
Equal probs Cluster Decode
4.65%
12.94
20.98
4.90%
13.81
Cos similarity Cluster Decode
20.95
4.75%
12.37
20.98
4.90%
12.94
PointNet + Cluster Decode
21.00
5.00%
12.82
21.00
5.00%
12.98
GCN Cluster Decode
20.47
2.35%
10.98
20.77
3885%
13.48
Table 6: Comparisons different heat-maps on OCP.
Synthetic Data
Real-world Data
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Equal prob Cos similarity + Cluster Decode
Cluster Decode
12.145
33.31%
21.50
18.75
33.69
12.135
33.20%
21.39
18.67
35.77
PointNet + Cluster Decode
10.80
18.55%
21.61
15.45
33.12
GCN Cluster Decode
9.325
2.36%
21.26
14.29
21.88
1.1 How CLUSTER DECODE ALGORITHM AFFECTS THE RESULT?
In this part, we want to figure out how the Cluster Decode algorithm proposed in Section 4.3.1 affects the result. Note that all decoding algorithms are combined with Active Search. Table 7 and
20

---

Published as a conference paper at ICLR 2024
Table 8 list the CCBPP and OCP results of different heat-map decode schemes. Greedy Decode means the next item of one sequence has the maximum connectivity probability with the last item in the heat-map, whereas Sample Decode means the next item will be sampled according to the connectivity probability of the last item. The Greedy and Sample Decode schemes are different from the Greedy and Sampling strategies for obtaining solutions mentioned in Section 5. The parameters here are the same as mentioned in Appendix D.2. The result shows our Cluster Decode (Algorithm 1) achieves better solution quality than the Greedy Decode with similar time cost on synthetic data, which may due to the cluster information and packing state our decode scheme takes into account. As for real-world data, the results of Greedy Decode and Cluster Decode remain the same, which may be because the size of the test samples is too small. Sample Decode shows poor results in this part, which may owing to the values in the heat-map do not differ much, and Sample Decode may bring noise to the final result. It can be proved from this experiment that the Cluster Decode algorithm does have a very positive impact on the performance the whole framework.
Table 7: Comparisons of different decode schemes on CCBPP
Q
10,
5
Q = 20, C' =
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Greedy Decode
20.51
2.55%
10.16
20.94
4.70%
13.14
Sample Decode
20.965
4.83%
14.27
20.99
15.52 4.95%
Cluster Decode
20.47
2.35%
10.14
20.77
3.85%
13.48
Table 8: Comparisons different decode scheme on OCP
Synthetic Data
Real-world Data
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Greedy Decode
9,450
3.73%
21.9
14.29
19.5
Sample Decode
11.97
31.39%
30.2
18.54
/
28.5
Cluster Decode
9.325
2.36% %
21.6
14.29
/
21.0
E.1.3 WHAT IS THE UPPER LIMIT OF THE FRAMEWORK?
In this section, we want to take OCP as an example and explore the impact of the number of AS iterations on the final result. It can be shown from Table 3 that the average results of synthetic data and real-world data are 9.325 and 14.29 when the search epoch is 50, how will the results change if the number of epochs is further increased?
Synthetic Dataset
Real-world Dataset
14.5
sample size 32
sample size = sample
sample
14.5
14.4
9.4
14.2
9.3
opoch
opoch
Figure 9: Learning curves of Active Search, with decode sample size 32 and 64.
Fig. shows the learning curve of the Active Search with RI, the sample size set as 32 and 64 which means 32 or 64 solutions are sampled, and the best one is reported. Note that there are only 32 physical cores in the experimental server. The decline of final results becomes much slower as the number of iterations increases, whereas the running time always increases linearly. Results of the synthetic dataset and real-world dataset are 9.285 and 14.125 when epoch 200, and the running time per instance is nearly 90s when the sample size is 32 and 180s when the sample size 64, which is sometimes infeasible in worl-world scenarios. A compromise may need to be made between solution quality and running time when the algorithm is applied in practice.
21

---

Published as a conference paper at ICLR 2024
E.2 IDBPP RESULTS
IDBPP is a special case of CCBPP where Q is I and C is also 1. We want to figure out how the Model works on IDBPP. The setting of IDBPP is the same as CCBPP where the capacity limit B is 100. We consider two kinds of size settings here. For the small-scale items, the sizes range from 10 to 25, and for the large-scale items, the sizes range from 25 to 50. Note that the sizes of small-scale items and large-scale items are all integers in this experiment.
Table shows the packing results of small items and large items. From the table, we can see our model can achieve the best results while spending less time than heuristic ones GA and ACO, and the gap to the optimal result is very small.
Comparing the results of different search strategies Greedy, Sampling, and AS, we can conclude that directly using the greedy algorithm can already get a promising result, which shows the repre- sentation ability of the heat-map for IDBPP is remarkable. After adding AS, the resulting quality can still be significantly improved, which shows that the effect of the search also very obvious for 1DBPP. In IDPPP, only sizes of items are given and there are class constraints the relationship between different items is hard to get, but our GCN can still obtain the cluster information via the heat-map labels. The results of IDBPP show the generalizability of our algorithm.
Table Results of IDBP, for small items, the sizes are ranging from 10 to 25, and for large items, the sizes are ranging from 25 to 50. The optimal value of the bin is 20 for both datasets.
For small-scale items
For large-scale items
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
21.00
5.00%
0.009
22.39
11.95%
0.0075
FFD
21.00
5.00%
0.011
22.17
10.85%
0.0084
20.59
2.95%
8.26
21.00
5.00%
7.02
ACO
20.77
3.85%
20.77
21.00
5.00%
75.99
PointNet-Grreddy
21.00
5.00%
0.011
22.34
11.70%
0.0082
PointNet-Sampling
21.00
5.00%
0.34
21.65
8.25%
0.26
GCN-Cluster,
GCN -Cluster, Greedy
20.79
3.95%
0.031
20.86
4.30%
0.032
GCN-Clusted Sampling
20.44
2.20%
0.21
20.36
1.80%
0.18
GCN-Cluster, AS(Ours)
20.24
1.20%
5.14
20.27
1.35%
4.13
E.3 GENERALIZATION TO DIFFERENT DISTRIBUTIONS
We investigate the generalization capability of our algorithm to the problem instances generated from different distributions. Since different C. Q and M mean different problems, we mainly explore the generalization of item sizes. We sample s from normal distributions N Nu,, o²) where and a are the expectation and the standard deviation. Two normal distributions. s ~ N(15, 52) and (200, 52) are adopted here. The test datasets of these two distributions are generated at random, not by cutting stock, so the optimal number is unknown. Another uniform distribution (25, 50) generated also by cutting stock is also tested here, and the optimal bins of the uniform distribution are 20.
Table 10 and Table 11 list the results of CCBPP when 5 10 and C = 20. The GCN model is trained on the uniform distribution U(10 without any fine-tuning. For uniform distribution s (25, 50). our method does not show advantages with heuristic algorithms GA and ACO, it may be due to the sizes of larger uniform distribution do not have any overlap with the training distribution. For the other two normal distributions, ours performs better than others, but with weak ad advantage. It may further improve the generalization capability if we better design the structure of our Graph Neural Networks, which we leave to future work.
E.4 RESULTS ON LARGE-SCALE BENCHMARKS
We conducted experiments on N = 300 and N = 500, as shown in Table 12 and Table 13. The dataset is also generated following Appendix.D.I and the optimal bins are 30 and 50 respectively. The results show that our proposed method still has advantages compared to other baselines. Larger- scale experiments when N > 1000 not conducted present due to the resource limitation.
22

---

Published as a conference paper at ICLR 2024
Table 10: Results from different distributions when C' = and Q 10.
g-n (225,50)
(20, 5P)
((55, 52)
Method
Bins
Gap
Time(s)
Gap
Time(s)
Bins
Gap
Time(s)
Random
22.44
12.20%
0.0070
40.655
0.0152
0.012
FFD
22.15
10.75%
0.0095
40.15
0.0179
30.12
0.016
GA
21.00
5.00%
13.18
39.875
17.2
29.74
14.45
ACO
21.00
5.00%
93.86
39,945
105.08
29.74
97.83
PoineNet-Grreddy
22.34
11.70%
0.0098
40.63
0.023
30.07
0.019
PointNet-Sumpling
21.68
8.40%
0.33
40.23
0.7609
29.89
0.63
GCN- GCN-Cluster, Creedy
22.29
11.45%
0,036
40.08
0.055
30.05
0.0052
GCN-Cluster, Sampling
21.91
9.55%
0.23
39.81
0.73
29.67
0.60
GCN- CCN--Cluter, AS(Ours)
21.00
5.00%
10.14
39.74
10.52
29.59
14.05
Table 11: Results from different distributions when C' = 5 and Q 20.
(25, 50)
(20, 5))
(155
5?)
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
22.405
12.03%
0.0070
40.95
0.0152
30.33
0.0124
FRD
22.115
10.58%
0.0164
40.60
0.018
30.53
0.016
GA
21.00
12.21
21.33
29.75
18.67
ACO
21.00
5.00%
96.74
40.19
94.81
29.65
89.31
PointNet-Greedy
22.34
11.70%
0.012
40.87
0.024
30.08
0.020
PointNet-Sampling
21.69
8.45%
0.415
40.48
0.77
29.85
0.77
GCN-Cluster, Greedy
22.08
10.40%
0.040
40.87
02024
30.08
0,020
Sampling
8.40%
0.72
29,84
0.62
GCN-Cluster, AS(Ours)
21.00
5.00%
12.02
39.85
15.91
29.60
/
16.33
There are some excellent works in the direction of combinatorial optimization that transplant models trained on small-scale problems solve large-scale ones (Li et al., 2021; Fu et al., 2021; Son et al., 2023), which should be inspiring and helpful to solve large-scale CCBPP with lower time complexity for the future research.
Table 12: Results when N 300.
Q 10,
Method
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
31.25
4.17%
0.0136
31.07
3.57%
0.0134
FFD
31,050
3.50%
0.0141
31.125
3.75%
0.0145
GA
30.58
1.93%
27.99
30.62
2.07%
29.753
ACO
30,625
2.08%
163.87
30.595
1.98%
179.704
PointNer-
31.09
3.63%
0.034
31.19
3.97%
0.0305
PointNet-Sampling
31.00
3.33%
0.3757
31.00
3.33%
0.5056
GCN--Cluter Greedy
31.00
3.33%
0.0644
30.995
3.32%
0.0702
GCN-Cluse Cluster, Sampling
30.925
3.08%
0.6250
30.93
3.10%
0.6911
GCN-
GCN-Clusted Cluster, AS(Ours)
30.545
1.82%
21.0235
30.57
1.90%
20.16
Table 13: Results when N = 500.
Method
Q 10,
= 5
Q
20,
C
5
Bins
Gap
Time(s)
Bins
Gap
Time(s)
Random
$1.86
3.72%
0.0409
51.93
3.90%
0.0409
FHD
$1.4150
283%
0.0308
51.76
3.52%
0.13155
GA
50.90
1.80%
72.65
51.00
2.00%
76.65
ACO
50.97
1.94%
388.10
51.00
2.00%
418.45
PointNet-Greedy
51.91
3.82%
0.0509
52.06
4.12%
0.0509
PointNet-Sampling
$1.22
2,44%
0.7997
51.46
2.92%
0.8793
-CCustrr Greedy
51.4650
2.93%
0.1300
51.6450
3.29%
0,1388
GCN MCN--Cluee -Cluster, Sampling
51,0050
2.01 %
1,4969
51.02
2.04%
1,5866
GCN Cluster, AS(Ours)
50.84
1.68% %
63.72
50.99
1.98%
64.52
E.5 THE ENCODER-DECODEE FOR OTHER PROBLEMS
Our proposed Encoder- Deceder Model also has the potential to generalize to other problems, try to prove that on multi-diimensoonal knapsack problem (MDKP). The mullti-dimensional knap- sack problem is classic optimization problem in which set of items with multiple attributes or
23

---

Published as a conference paper at ICLR 2024
dimensions (such as weight, volume, value) must be selected maximize given objective while satisfying certain constraints. Since there only one bin in MDKP and we only need to decide whether one item should be packed in or not, the heat-map in the model can be treated as vector in this problem, and the Decoder is the same as the greedy strategies. The features of the vertices are the properties of the items, and the edge features filled with
In this section, we use the performance (the achieved value in knapsack) by GLOP implemented in the OR-tools (Perron & Furnon, 2022) as baseline. The value/weight greedy, Reinforcement Learning, and Learning-to-Ran are used as comparisons following Woo et al. (2022), gumbel trick an efficient sequence sampling method also proposed in Woo et al. (2022).
Table 14: Results MDKP on different datasets, N and k denote the number of items and the size of knapsack resource dimensions, respectively. e denotes the correlation of weight and value of items. Time the average time to solve a single instance and Gap represents the ratio to the GLOP algorithm.
3_ S0,
3.
10,
-
10 0.
300
o
-30 0.0
00000
1075
10350
-325
[31
1004
1134
120%
113
1305
123
[00075
1D35
Goady
00309
0.00553
100 K/
+4.0%
DrK0ns
102475
4100
136
B16C47
9231/9
91.19
0.30
$3.3%
1:31
101.075
0,95
94.379
236
182659
3.5G
RD
$73499
0,922
96.44
DUC
5100
1984
91.00
5404
08229
0.04
102259
0.004
00013
00007
0305
0180
00011
10311
OCN-Castel
09.459
0017
92000
0.003
(0L.59
1000
101.00
5406
10300%
0.844
0.41
Table 14 shows the results of datasets with different scales. GCN-Greedy, GCN-Gumbel, and GCN- AS provided in Table 14 the results of training the network and introducing different search algorithms. As mentioned above, only one bin included in MDKP, the heat-map we get here only one-dimensional data, and the value represented in the data is the probability of this item being packed into the knapsack. According to this one-dimensional representation, some search algorithms can be combined obtain the final result. From the results, we can see that the results of AS are greatly improved compared with Greedy and Gumbel Search, but the time cost is relatively large. Gumbel search can also improve the results by introducing a certain random mechanism, yet the improvement is not obvious. It can be concluded from Table 14 that our framework GCN-AS achieves the best results on all datasets, while the time cost is the lowest among all the learning- based methods.
As increases, all methods show longer inference time, but the increment gap of GLOP is much larger than other methods. Our method shows superior performance over GLOP as N = 50 with less come-consuming. The greedy algorithm shows a very good advantage in running time and solution quality, especially when complexity of RL is very high. Our algorithm shows even better results than all other algorithms on both solution quality and running time compared smaller N.
0.0. RL and RD achieve good performances when 0.9 but the time
24


Reviews:
[{"review_id": "7Qxykd9t1A", "reviewer": "Reviewer_aXcu", "summary": "Authors propose a new learning-based solver for Class-Contrained Bin Packing Problem (CCBPP). CCBPP is commonly applied to planning optimization problems. As a good solution requires clustering of items in the same class, existing sequential learning-based algorithms struggle. Authors propose a GNN-based model, which is pre-trained on synthetic data with ground truths. The model is further fine-tuned with policy gradient. In order to account for the fact that good solutions should cluster items in the same class, a decoding algorithm that prioritizes items clustered to existing open bin is proposed. Experimental results demonstrate that the proposed algorithm outperforms reasonable heuristics, typical population-based algorithms, and standard Pointer Networks.", "questions": "In equation (8), wouldn't it numerically more tractable to optimize the log probability $\\sum_{i,j} \\hat{p}_{i,j}  \\cdot \\log p_{i,j}$, rather than sum of probabilities as in (8)? I understand this has nice interpretation as modularity, but often, probabilities are harder to optimize with gradient descent than log-probabilities, because sigmoid has near zero gradient for most of its domain.\n\nI was also not sure how Policy Gradient shall be applied on ClusterDecode. Authors say $p_\\theta$ in Policy Gradient equation (Section 4.3.2) correspond to Cluster Decode, but according to Appendix C, Cluster Decode is mostly deterministic algorithm (other than the choice of the first item). Hence, conditioned on the choice of the first item, the probability will be 1 for chosen item at the state, and 0 for not chosen items.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality, Significance: While many of the learning-based combinatorial optimization methods employ sequential models, CCBPP is a problem sequential models may not be best suited. Authors demonstrate that indeed the proposed method, which accounts for the clustering of items in the heatmap, outperforms previous sequential methods. This is an original contribution that will help the research community to think differently. As the use of GNNs & heatmaps are common in other methods, innovations in this paper, such as cluster decoding would also easily transfer to other problems in the future work. \n\nQuality: Authors follow best practices in the literature. First, they use GNN to model the interaction between variables, which has become standard in neural combinatorial optimization algorithms. Then, they use heatmap for decoding, which is becoming standard for TSP and related problems. The choice of supervised pre-training is also very well-suited, because difficult problems with known ground-truth shall be easily generated. The proposed method also makes a good improvement over Pointer Network baseline. Experiments cover both synthetic and real-world data.\n\nClarity: The main ideas of the paper is mostly straightforward to follow, although I had some questions.", "weaknesses": "While the paper makes some methodological contributions such as GNN modeling of the problem and cluster-aware decoding algorithms, the significance of these proposed methods are contingent on the significance of CCBPP problem. As I am not an expert on bin packing and related problems, it is difficult for me to evaluate the significance of CCBPP. Also, other attendees of this conference may feel similarly. When authors present the paper, attendees wouldn't be interested in the talk unless they are convinced of the usefulness of CCBPP. While authors discuss CCBPP applications in Section 3, I would encourage authors to elaborate more on their significance in order to convince this conference's audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "174iTUCgQ6", "reviewer": "Reviewer_HxmL", "summary": "This paper studies the Class Constrained Bin Packing Problem (CCBPP), which is a typical example of the vector Bin Packing Problem. The authors propose an encoder to predict the connectivity probabilities of different items and a fine-tuned decoder to output the solution. Experiments demonstrate that the proposed method outperforms baselines on several benchmarks.", "questions": "1. What is the technical novelty of the proposed method?\n2. What is the motivation of using the heatmap to classify items?\n3. Can the authors evaluate the proposed method on large-scale benchmarks?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tTo the best of my knowledge, this paper is the first learning-based method to address Class-Constrained Bin Packing Problems.\n2.\tExperiments demonstrate that the proposed method outperforms baselines on several benchmarks.", "weaknesses": "1. This paper studies a typical example of the vector Bin Packing Problem. The authors may want to explain the significance and generality of the studied problem in detail.\n2. This paper proposes an encoder-decoder model to solve Class-Constrained Bin Packing Problems. However, many existing learning-based methods for solving combinatorial optimization problems are based on Encoder-Decoder Models as well [1, 2, 3]. The authors may want to explain the novelty of their proposed method over existing works in detail.\n3. The authors propose to use a graph neural network to generate a connection heatmap for classifying items into different packs. However, the motivation of using a heatmap to classify items rather than directly learning a node classification model is unclear.\n4. Discussion on related work of other learning-based approaches for bin packing problems is missing.\n5. The baselines are insufficient. Although the authors compare their method against the pointer network, recent work has proposed several improved models of the pointer network [4, 5]. The authors may want to compare their method with these baselines.\n6.  It would be more convincing if the authors could evaluate their method on large-scale benchmarks, such as bin packing problems with over 1,000 items. \n\n[1] Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. \"Pointer networks.\" Advances in neural information processing systems 28 (2015).\n\n[2] Li, D., et al. \"Solving Packing Problems by Conditional Query Learning.\" International Conference on Learning Representations (ICLR) Conference 2020.\n\n[3] Zhang, Jingwei, Bin Zi, and Xiaoyu Ge. \"Attend2pack: Bin packing through deep reinforcement learning with attention.\" arXiv preprint arXiv:2107.04333 (2021).\n\n[4] Kool, Wouter, Herke van Hoof, and Max Welling. \"Attention, Learn to Solve Routing Problems!.\" International Conference on Learning Representations. 2018.\n\n[5] Nazari, Mohammadreza, et al. \"Reinforcement learning for solving the vehicle routing problem.\" Advances in neural information processing systems 31 (2018).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oMOA17exHS", "reviewer": "Reviewer_2rkj", "summary": "1.In this paper author proposed a vector BPP variant called Class-Constrained Bin Packing Problem (CCBPP), dealing with items of both\nclasses and sizes, and the objective is to pack the items in the least amount of bins respecting the bin capacity and the number of different classes that it can hold.", "questions": "1.Justify the need of encoder architecture proposed by Fraughnaugh, 1997 used here what advantages it has in the proposed work implementation.\n2.Math mentioned in the decoder archticture in figure 2 should be mentioned in detail.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The pipeline encoder and decoder is quite unique work.\n2. Presented results are compared with recent state of art techniques in detail.\n3.More scope for the future researchers.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JGBkGaRGB8", "reviewer": "Reviewer_Rj4P", "summary": "This paper presents a neural network solver for the bin packing problem. The neural network model is built under the encode-decoder framework, where the encoder network is a graph neural network to modulate the problem, and the decoder module contains heuristics, neighborhood search, and RL-like active search. Experiments are conducted on", "questions": "* Can you plot the gap vs time for different methods?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem of bin packing problem and its variants are important and worth studying.\n* The methodology presented in this paper seems technically sound.\n* The authors conduct extensive experiments on different variants of the bin packing problem. The design of data generation with ground-truth labels in the order consolidation problem is interesting. \n* This paper is well-written and easy to follow.", "weaknesses": "* The encoder-decoder pipeline is quite common in machine learning solvers for combinatorial optimization problems. The authors make some specific adaptations for the bin packing problem, while in general, the results are not too surprising under such a framework. \n* It will be better to have more insights into the bin packing problem and what machine learning can help to inspire future researchers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QiFR35wuSU", "reviewer": "Reviewer_hLWM", "summary": "The authors aim to solve a special 1D-BPP with class constraints. First, train a heatmap to represent the probability. Second, use a decode strategy to generate a solution from the heatmap while satisfying the constraints. In addition, it could be finetuned with RL.\n\nI admit it is a new problem, but the action space is much smaller than traditional 3D-BPP.", "questions": "\"we use class cosine similarities as edge feature\" How to calculate the edge feature? \n\nWhat's the size number N set in the experiments?\n\nWhat's the dataset used for finetuning in experiments? \n\nIs it a fair comparison with the baseline method without the finetuning dataset?\n\nWhy did the active search improve so significantly? \n\nCould you clearly explain how to select items? how do choose the current bin to place the selected items while satisfying constraints?\n\nCould other constraints be considered rather than just class numbers?\n\nThe constraints seem not as complex as the constraints in 3D-BPP. In the seq2seq problem, it could be easily handled by the mask function.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem is new and the authors proposed a framework (which might be already used in TSP and VRP)  to solve the problem well.\n\nThe authors conduct comprehensive experiments. \n\nThe ablations study is provided.", "weaknesses": "The used heatmap method is not new and a similar method has been used in TSP and VRP.\n\nThe studied topic CCBPP and problem is less-studied and uncommon to see.\n\nThe method is not explained well and clearly in the main body such as cluster decode and active search.\n\nThe active search seems to be fine-tuning with RL. I do not see anything novel. \n\nThe paper is not easy to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)