Learning to Solve an Order Fulfillment Problem in Milliseconds with Edge-Feature-Embedded Graph Attention
Authors: Jingwei Yang
Qingchun Hou
Xiaoqing Wang
Yang Wei
Yuming Deng
Hongyang Jia
Ning Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Combinatorial Optimization
Machine Learning
Modern Supply Chain Management

Abstract: The order fulfillment problem is one of the fundamental combinatorial  optimization problems in supply chain management and it is  required to be solved in real-time for modern online retailing. Such a problem is computationally hard to address by exact mathematical programming methods.  In this paper, we propose a machine learning method to solve it in milliseconds by  formulating a tripartite graph and learning the best assignment policy through the proposed edge-feature-embedded graph attention mechanism. The edge-feature-embedded graph attention considers the high-dimensional edge features and accounts for the heterogeneous information, which are important characteristics of the studied  optimization problem. The model is also size-invariant for problem instances of any scale, and it can address cases that are completely unseen during training. Experiments show that our model substantially outperforms the baseline heuristic method in optimality. The online inference time is milliseconds, which is thousands of times faster than the exact mathematical programming methods.

Under review as a conference paper at ICLR 2022
LEARNING TO SOLVE AN ORDER FULFILLMENT PROBLEM IN MILLISECONDS WITH EDGE-FEATURE- EMBEDDED GRAPH ATTENTION
Anonymous authors Paper under double-bling blind review
ABSTRACT
The order fulfillment problem is one of the fundamental combinatorial optimiza- tion problems in supply chain management and it is required be solved in real- time for modern online retailing. Such a problem is computationally hard to ad- dress by exact mathematical programming methods. In this paper, we propose a machine learning method to solve it in milliseconds by formulating a tripartite graph and learning the best assignment policy through the proposed edge-feature- embedded graph attention mechanism. The edge-feature-emte femeauuue--ebeddeedd graph atten- tion considers the high-dimensional edge features and accounts for the heteroge- neous information, which important characteristics of the studied optimization problem. The model is also size-invariant for problem instances of any scale, and it can address cases that are completely unseen during training. Experiments show that our model substantially outperforms the baseline heuristic method in optimal- ity. The online inference time is milliseconds, which thousands of times faster than the exact mathematical programming methods.
INTRODUCTION
The current decade has witnessed rapid development of online retailing, which generally has a very large operation scale and poses new challenges to supply chain management. One of the most important problems in the online retailing is the real-time order fulfillment decision, which aims to find the most cost-effective order-warehouse assignment after the customers place the orders online. The decisions are required to be made in real time, because the fulfillment system must complete hundreds of orders per second (Acimovic & Graves 2015 Xu et al., 2009). A good fulfillment policy could reduce expenses by millions of dollars for large online retailers such as Alibaba and Amazon.
The order fulfillment problem in its most general form is follows: There are number of orders and a number of warehouses. Each order contains several items, which are at different inventory levels and have different sale-forbidden dates in these warehouses. Any warehouse be assigned to serve any order, incurring delivery transportation cost and inventory management cost that vary depending the locations of the orders and the types of items. An order be split into multi- ple packages that are committed by different warehouses due to practical constraints, such as the shortage of inventory. A group of identical items in any order is defined as a suborder, which the smallest assignment unit in this problem. The retailer seeks to find the optimal warehous assignment policy that minimizes the overall cost in the order fulfillment.
The order fulfillment problem falls into the category of generalized assignment problems, which is an NP-hard combinatorial optimization (Kundakcioglu & Alizamir (209) (An extra note on gener- alized assignment problem is listed in the Appendix A. Traditional approaches to this problem can be divided into exact methods and heuristics. The exact methods guarantee finding optimal so- lutions by using branch-anddbous (MIP), but they generally require a long time to solve and are even computationally intractable for large-scale cases. Because the order fulfillment is real-time decision task in the online retailing,
search (B&B) with mixed-integer programming formulation
'The sale-forbidden date is usually months ahead of the expiration date. Any item going beyond the sale- forbidden date can no longer he sold.

---

In this paper, will for the first time apply ML solve the real-time order fulfillment deci- sion problem by developing a graph mapping solution framework. A size-invariant graph model developed to learn the hidden information on the heterogeneous graph. A novel graph attention mechanism is proposed to consider the high-dimensional edge features in the represented optimiza- tion problem. The specific contributions are threefold: (1) formulate the real-time order fulfillment decision problem with constraints of the modern online retailing and supply chain industry; (2) pro- pose a tripartite heterogeneous graph representation of the order fulfillment problem and develop graph Under review as a conference paper at ICLR 2022
the exact methods are unable meet the allowed maximum computation time (tens of millisec- onds). The heuristics are typically a set of specialized rules and are currently used in the industry because of the low computational cost(Sethanan & Pitakaso 2016 D' D'Ambrosio et al. 2020). As trade-off, the optimality is sacrificed and once the conditions of the problem change, the rules must be re-designed carefully, which costs lot of manpower.
Recently, machine learning (ML) has made much progress on solving combinatorial optimization problems (Bengio et al., 2018), e.g., using supervised or reinforcement learning solve the trav- elling salesman problem (TSP) and the vehicle routing problem (VRP) in an end-to-end approach (Vinyals et al. 2015 Kool & Welling, 2018: Lu et al. 2020). According to the research, ML meth- ods can achieve stronger policies than heuristics without requiring specialized human knowledge. The computational cost of MI. inference is extremely low. The MI. methods are also self-adaptive to the changes on the problem conditions, because they are end-to-end methods from the original data to the solutions. This progress motivates us to explore whether order fulfillment in the supply chain industry can be addressed by ML methods.
However, the nature of the order fulfillment problem size-variant and contains heterogeneous information. Different scales of problem instances have varying numbers of orders, items and warchouses. How can we properly transform the combinatorial optimization problem into the in- put/output of an ML model? How can we design an ML model that can effectively solve the varying scales of problem instances? These questions pose great challenges to our work.
an ML-bbased solution framework; and (3) propose size-invariant and adge-feature-ember attention to learn the hidden information the heterogeneous graph.
RELATED WORK AND GAPS
Generally, applying ML on combinatorial optimization can be divided into two approaches. The first approach is to improve the branch-and-bound algorithm in the MIP formulation by using ML. for variable branching (Alvarez et al., 2017). node selection (He et al. 2014) and so on. Although approach, the
these methods can guarantee exact solutions by relying on the branch-and-boud acceleration is limited. Our focus is the other type of method, the end-to-end learning approach (Bengio et al. 2018), which learns the optimization policy directly from the problem instances.
The end-to-end MI. models for combinatorial optimization require careful design, because both of the problem input and output vary in size (Bengio et al. 2018). This circumstance means that the ML model must be able to address the data sizes that completely unseen during training. To tackle this problem, the pointer network (Ptr-Net) is introduced based on the sequence-to-ssquenee model (Vinyals al. 2013 Bello et al. 2017]. The Ptr-Net directly uses an attention mechanism as a "pointer" to select a member of the input sequence as the output, regardless of the varying output dictionary sizes that depend on the problem instances. According the experiments, the model performs well on the convex hull problem and TSP beyond the maximum sizes that they are trained on. (Hu al.] (2017): Duan et al. (2019) further apply the Ptr-Net on the bin-packing problem to determine the optimal sequence in which the items are packed into bins. Apart from Per-Net, Kool&& & Welling (2018) solves the TSP based entirely on the attention mechanism similar to the Transformer architecture (Vaswani et al. 2017). The input data is the (z. v) coordinates of all of the nodes, and the model calculates the attention between every pair of nodes. Finally, a sequence of nodes is generated as the optimal result. However, current studies based on Ptr-Net are mainly designed for sequential decisions, which might not fit the pattern for the studied assignment problem. According to Vinyals et al. (2016); Hu et al. (2017). the use of the RNN as encoder in Ptr-Net makes it difficult to represent long input sequences and suffers heavily from the order of the input data.
2

---

Under review as a conference paper at ICLR 2022
The graph-base models, e.g., the graph convolutional network (GCN) and graph attention network (GAT)(Veličkovie et al. 2018), have also been applied in several studies, because many optimization problems can be represented problem and TSP by embedding the graph with a structure2vec network and iteratively adding the best node construct the solution using reinforcement learning. |M al. (2019) proposes the graph Ptr-Net by using graph embedding as the input of Ptr-Net to solve the TSP. Li et al. (2018) first uses GCN to generate large number of candidate solutions to the combinatorial optimization. Then, guided tree search is performed to refine the solution. However, most mentioned studies address homogeneous graphs without high-dimensional edge features, such the TSP and VRP problems, where the input is set of (ar, y) coordinates. In the studied problem, the features of orders, items and warehouses are heterogeneous and the relationships between them are important, such as the tiered pricing rules between orders and warehouses, and the inventory between items and warehouses with different sale-forbidden dates. Current studies lack proper consideration of these important high- dimensional edge features and the heterogeneous information between different types of nodes and edges.
graph. Dai et al. (2017) attempts to solve the minimum vertex cover
PROBLEM STATEMENT
The mathematical formulation of the studied order fulfillment problem for modern online retailing is formulated in (Ia)-(Ih). Table lists the notation. For better understanding, a brief introduction on the generalized assignment problem is given in Appendix A.1, which is the basics of the order fulfillment problem.
min Zkd
ΣΣ
(10) ki Iki + C(1) ki Whi)
+ ΣΣΣ REK JEJ FE
Prctze
(la)
REK TET
s.t.
2kd Tkis
Wk K. Vi
(1b)
Σ Fkl = 1,
E
(1c)
KEK
dRst O1zE1
HKEK,IEN
(1d)
IET
Σ (EL(-))
dRa S Skjtz
VKEK
(le)
Tg. D + wkss 2
Σ
W Σ
dais
Ak AKEK E.W
(1f)
(EL().))
TET
Fuze + Ekge -kaje
Skye
Σ
dgits
vk vk E E J,
(Ig)
1EIl..5)
+ Fkst + kzj
Ckjt
= -Sktt
Σ
Ak VKEKVJEII11 dRus Ck
(1h)
(EL(-))
The objective of the optimization problem (Ia) is to minimize the overall fulfillment cost, including the delivery cost and the inventory management cost, by making the optimal assignment between warehouses and suborders. The delivery cost consists of the first weight cost and additional unit cost according to the tiered pricing rule in the logistics. The inventory management cost denotes the loss of the cargo value, which is the result of the items that become sale-forbidden.
Constraint (1b) denotes that if warehouse serves any suborder in order i, then Jx 1. Constraint (Ic) denotes that any suborder should be served by one and only one warchouse.
Constraint (Id) denotes that the sum the selected items before differenn sale-forbidden periods in warehouse A must equal the gross item quantity of the suborder l. Constraint (Ie) means that any item ý cannot be out-of-stock. Constraint (1f) represents the tiered pricing system in logistics, where the right-hane hand side of the equation is the total weight of the served part of order by warehouse k. Constraints (Ig)-(1h) represent the item picking sequence in the warehouse. Because any item going into sale-forbidden periods can no longer be sold, they must be picked from near to far.
3

---

Under review as a conference paper at ICLR 2022
Table Notation List
PART
DESCRIPTION
Sets
I,L,J,K,T T: The set of orders, suborders, items, warehouses and time periods
D: The first weight of any package in tiered pricing rules
Oj: The item quantity in the suborder [
W,, Pj: Weight and purchase price of item j J
Constants
( CCI) The first weight cost and additional unit cost of package i)
Fkje: The forecasted sale amount of item j E J in warehouse
period E T
Skje: The inventory of item j in warehouse & IK
that becomes sale-forbidden beyond period
Jek E {0. 1): Whether warehouse E serves order E T, 1: YES, O: NO
dete E R+: The quantity of items in suborder served by lt E KK
Auxiliary variables
that becomes sale-forbidden beyond period t
whi E R The additional weight package (k i)
kje E R+ The quantity of item j E warehouse l E K that becomes sale-forbidden in period E 'T'
Ekje E R+: The lack of inventory in Skjz considering picking sequence
Decision variables
2kt E {0, 1): Whether warehouse k K serves suborder E IL, 1: YES, O: NO
1 Any suborder E L belongs to unique order i I and has group of identical item J. 2 The package (k, i) denotes that part of or all the suborders in order I are served by the warehouse K and are delivered as one package.
Note that 2ke is the key decision variable, and it represents the assignment between warehouses and suborders. When we make decision, two constraints are the most important: (1) Each suborder should be assigned only one warehouse, represented by (Ic); (2) The item inventory in the signed warehouse must not be less than the demand of the suborder, represented by (1d)-(1e). Other variables and constraints item picking sequence; and Tki, Uki used to represent the difference between the first weight and the additional weight in the tiered pricing rules.
auxiliary. For example, dgtt, kkjy fujt used mainly represent the
SOLUTION FRAMEWORK
In the proposed solution, we first map this problem into a tripartite heterogeneous graph as the input to the graph ML model, which has the advantage of being permutation-invarian to the input order. Then, we design the weweeefeaauueeeeeeeeeee graph. Last, we use the attention between the hidden state of the orders and warehouses to make the assignment, which can fit cases with varying sizes of orders, items and warehouses.
graph attention
learn the hidden state of the
During the offline training, the exact B&B method is applied to solve the problem instances to generate the optimal assignment results as the training labels. In the stage of online inference, we directly predict the suborder-warehouss assignment through the graph MI model. Because the proposed graph ML model is size-invariant, can generalize to cases larger sizes that have never been seen during training.
4.1 TRIPARTITE GRAPH REPRESENTATION
First, we novelly represent the order fulfillment problem with tripartite graph in Figure Ia where vectors h, e represent the features of nodes and edges, respectively. Compared to the sequential representation, the graph representation has the advantage of being sermutation-ivarriant, which means that different input data orders correspond to the same graph. The three disjoint sets in the graph the orders (decomposed into suborders), items and warehouses.
4

---

Under review as a conference paper at ICLR 2022
Input graph
onder 1
order [1]
suborders l;;
Fddg-fccatur--mmoodde GAT
Eff
demand
N x hierarchy
FF nodes
edges
items h
fulfillment cost
6Tk
Output graph
Inventory
sule lorbiaddnn dales eja
suborders
warchouses
Assignment
warchouses
(a) Tripartite graph representation
(b) Graph-based based model
Figure 1: The tripartite graph representation and the graph-based machine learning model
Different sets of nodes have different features. The feature h2 E R. E L suborder node is an N N-dimensional one-hot vector, representing the order that belongs to. The suborders under the same order share the same feature. denotes the maximum size of orders the model is designed to handle. The feature h& RM, & K. of warehouse node k is an M -ddimensional one-hot vector, representing the different warehouse identification codes (ids). M denotes the maximum size of the warehouses that the model is designed handle. The feature hj [P,, W E of item node is a two-dimensional vector that consists of the purchase price and weight of the corresponding item.
The edges between different of nodes also represent different information. The feature est [C()) ,C(())
]. & E K, I L(i..) between suborder and warehouse & represents the tiered delivery cost. Note that the first weight and additional weight cost from one warehouse to the suborders under the same order are identical. The feature etj = j E J, E J) of the edges hetween suborder and item represents the quantity of items that each suborder contains. The feature Ækj [Skjo. Fkjo.... .... Skit, F.lt k E K,j E J of edges between warehouse k and item j is vector with the length of x [T], which represents the inventory and forecasted saleplan in different sale-forbidden dates.
4.2 THE GRAPH-BASER MACHINE LEARNING MODEL.
To learn the hidden states from the original tripartite graph and to make an assignment, we propose hierarchical graph-based machine learning model in Figure [b] The model consists of three impor- tant components. The first component is the edge-feature- www.--aauueeebbeeeee embedded GAT layer, which follows the work of Velickvić et al. (2018) but uses novel attention mechanism to learn the high-dimensional edge features and the heterogeneous information in the graph. Next, a feed forward (FF) layer makes nonlinear transformation of the node and edge features. Last, "assignment" layer generates the assignment between suborders and warehouses by computing the attention coefficients of each pair. is worthwhile to note that the attention mechanism used throughout the model and no transfor- mation depends on the size of the graph, which makes the model able to address varying sizes of orders. items and warchouses.
4.2.1 EDCF- GAT LAYER
The input to the edge- filee-ffatur--ebbddee GAT is set of node feature vectors (hi, hy, hx) and edge feature vectors {ety, eu: exj), Vl L, j E J, e K. Here, we will use the transformation of nodes that represent suborders hy VI TL illustrate how we properly embed the edge features.
5

---

Under review as a conference paper at ICLR 2022
First, we embed the edge features in the computation of the attention coefficients. For any node I L, we compute the attention coefficients between h1 and hj. h2 as follows:
jjj = (h,, h Etj) - a (ViL (hill halpy/leee (e))) Vi EJ
(2)
C/ score hu, etx) (V&l [br]]/a [lx)) vk K
(3)
Here, the attention mechanism is a single feed-forward layer with the nonlinear activation function a. VIL. and VKI. denote the weight vectors with respect heterogenous node pairs. For any and & E IK, the weight vectors remain the same and thus are invariant to the sizes of the node sets. represents the concatenation operation. The attention coefficients indicate the importance between any two nodes considering the edge feature that links them and are computed only if the nodes are connected the graph. The coefficients are then normalized across the same type of neighborhood nodes using the softmax function:
exp(cr)
Jyj = softmax, (c;)) = Ejer exp(cr))
Vj EJ
(4)
exp(c()) wl: E K
softmax
(5)
ΣvEK exp(ci))"
Second, we embed the edge features into nodes using a linear combination by the attention coeffi- cients to update hu, Vl E LL:
||
h = hi
Σ > LECK
an (hellee))))
Σ an (h, JeJ
(6)
Two things should be noted in (6). First, the updated node feature is concatenated with three parts. The first part is the self-feature, while the others are the combination of the feature of items and warehouses. The reason is that the graph we address contains heterogeneous information and should be treated appropriately. Second, the edge feature is again concatenated with the node feature apart from that 2 3 One special case can illustrate the necessity behind this step. Consider node that has only one neighborhood. The attention coefficients will always be 1.0 for this neighborhood, regardless what the edge feature is. If we do not concatenate the edge feature according to the method of ( lose the information (3) have already embedded the edge features, the concatenation of edge features in (6) can further strengthen the explicit representation of the edge information.
the edge between them. For other cases, although (2)
By applying the transformation method (2)-(6) on nodes hj, Vj E J and h2, vk E K, we obtain the updated node feature h, and hgg which, in combination with hi forms the output of the layer.
4.2.2 FEED-FORWARD LAYER FOR NODES AND EDGES
Note that the edge-feature-emmeddee GAT layer only makes a linear combination of features in equation (6). Therefore, further use feed-forward layer transform the features of nodes and edges with nonlinearity. We still take the nodes that represent suborders as an example, of which the updated feature after the GAT layer is his The transformation through the feed-forward layer is as follows:
h = (Wihi) E
For the edges, the GAT layer does not make a transformation and thus we have the following trans- formation for the edges that connect any suborder | L:
ē₁j (Wn.e Vj JJ
(8)
e (K..E)) Vk K
(9)
where WI.,, Wx. are the transformation matrices for the edges between suborders and items, sub- orders and warchouses. Note that for any suborder node and the connected edges, the weight matrix W1. WI., WKL. are the same and are thus invariant to the size of node set.
The outputs of FFN are (hr, F and {ēt,, ēik: ēxy J. VI L,j J, E K. They formulate a new graph with the same topology as the input graph and will be used as the input for the next hierarchy for further transformaton.

---

Under review as a conference paper at ICLR 2022
4.2.3 ASSIGNMENT LAYER
To assign suborders warehouses in size-variant cases, we again use the attention mechanism as a "pointer" Vinyals et al. (2015) to point each suborder to the appropriate warehouse. First, we calculate the attention coeffccients on the output graph between each pair of suborder I and warehouse & using the dot product:
CJk: score (h,, h2) h hg, AI ELLKKK
(10)
Next, apply the softmax function to normalize over all of the warchouses and, for any suborder node 1 L, we use the pik as a distribution over the warchouses.
exp(ci)
Pik = (cft = ΣREK exp(cu:
(11)
The largest probability arg maxkez Piu: is the selected suborder-warehouse assignment by the ML model. Note that in this step, there weight matrix to be trained and thus, the approach is invariant to the sizes of the suborders and warchouses.
4.3 OFFLINE MODEL TRAINING
In the stage of offline model training, we use supervised learning. The cross-entropy is applied as the loss function. The total loss in instance should account for all of the suborders as follows:
loss ΣΣ YR log(pts)
(12)
TET. KEK
where yıu the real label that denotes whether suborder / is assigned to warehouse Real labels are generated by using the exact B&B method to solve the MIP (Ia)-(1j) under different input instances.
4.4 ONLINE MODEL INFERENCE
In the stage of online inference, each input case is formulated into the tripartite graph, and the offline- trained graph-based model is directly used to compute the attention coefficients between each pair of suborders and warehouses. To guarantee the feasibility in the online order fulfillment decision, the most important constraints (Ic)-(le) must be satisfied. We use the following masking procedure in finding the largest probability arg maXkeK Pu:: (1) Select the suborder I = arg max; O₁; (2) The warehouse node k KK with insufficient inventory (O; > ΣiET Skjt) not allowed to be visited; (3) Find the best warehouse k arg maxtek Pia and reduce the inventory of item j from the nearest sale-forbidden date until the quantity equals O₁.
EXPERIMENTS
5.1 DATASETS, BASELINES AND METRICS
We generate one training and three testing datasets with varying scales. The ML model is trained only on the training set and then tested on the three test sets. The training dataset contains 100,000 instances of the order fulfillment problem with the optimal assignment results as labels, which are obtained by solving the MIP formulation (Ia)-(1h) using the open-source SCIP optimization suite Gleixner et al. (017). The problem size in the test cases is larger than that the training dataset.
We report four baselines in the experiments. The first is the exact branch-and-boume (B&B) method. The second the heuristic method that currently applied in practice (The detailed algorithm described in appendix A.2.) The third bascline is to the Ptr-Net based supervised learning, which is also our first attempt facing the order fulfillment problem. To compare the effect of con- sidering the high-dimensional edge features and heterogeneous information in our model, we add the fourth baseline by replacing the adge-feature-embedee graph encoders with the original GAT network Veličković al. (2018) in solution framework.
The evaluation metrices are the computation time and the gap in the total cost between the model's result and the optimal solution (obtained by SCIP with time limit of 15 minutes). The total cost
7

---

Under review as a conference paper at ICLR 2022
Table 2: Description datasets and experimental results
DATASET
DESCRIPTION
METHOD
COST GAP
INFERENCE (IME(ms)
Size: 100,000 I[ ~ 20 [ 30 40 40 |K 4 8
TARIN
Exact B&B
0%
450
Size: 10,000 6 ~ 20
Heuristic
12.6%
1.8
TEST
Ptr-Net 15.6%
31
J 40
GAT
16.4%
2.5
K| 4 8
Our method
2.1% %
2.7
Exact B&B
0%
3,200
Size: 10,000 20 50
heuristic
11.9%
2.7
TEST 2
Ptr-Net 14.8%
78
J 70 ~ 90
GAT
16.1%
4.9
K| 8
Our method
2.5%
5.1
Exact B&B
0%
62,000
Size: 100 II 50 100
heuristic
11.4%
5.8
TEST
Ptr-Net
13.8
210
J 100 120
GAT 15.1%
12
[K] 12 ~ 20
Our method
3.0%
13
187
40%
48%
4.%
20%
-10%
Hemm
Piche
6M
Oareted
Hourde
mch
(a) Results test set 1
(b) Results test set 2
(c) Results test set 3
Figure 2: Boxplot of inference results on test sets
is computed using equation (1a) based the order fulfillment result. A smaller gap means better assignment policy.
COStmodel COSTMIP
gap
(13)
COSTMIP
5.2 ARCHITECTURE AND HYPERPARAMETER
In the experiments, apply N graph encoders, without using extensive hyperparameter search and the multi-head mechanism. The nonlinear activation function in both the edge-feature- embedded GAT layer and the FFN layer is the exponential linear unit (ELU) Clevert et al." (2015). During the training, we apply dropout ratio of 0. to the FFN inputs. The model is trained with the Adam optimizer with learning rate of 0.003 and batch size of 256.
5.3 RESULTS
The details of the datasets and the results of the experiments summarized in Table 2 Figure compares the performance of all of the methods on the test datasets. Figure gives an example of the model-predicted assignment result from the 3rd test case.
8

---

Under review as a conference paper at ICLR 2022
(a) Inferred assignment result by our model
(b) Optimal assignment result by solving
Figure 3: An example case with 60 orders (92 suborders, orange points) and 14 warehouses (blue points). The cost gap this example is 3.52%.
From the results, we note that our method achieves the smallest cost gap and substantially outper- forms the heuristic method, Ptr-Net and the original GAT without embedded edge features. In Figure 2, we find that our method also has the smallest variance at the stage of inference, which means bet- ter robustness. In test sets 2 and 3, where the sizes of the problem instances are completely unseen during training, our method still has the best performance extrapolating.
The inference time of these methods is also compared. We note that, although the heuristic method has the lowest computational cost because of its simple rules, our method is able to make inference in several milliseconds. Compared to directly solving MIP, method achieves tens of thousands of times of acceleration in the computation time and meets the criteria for real-time applications. The reason behind this outcome is that the graph encoders compute the assignment results through matrix multiplications. In contrast, the exact B&B method iteratively searches the results in the feasible region and is thus much slower than method.
The reason for the bad performance with the original GAT network is obvious, because the important high-dimensional edge features are ignored in the model. However, is worthwhile note that Ptr-Net does not perform well in the studied task. We think that three reasons might lead to this result. First, Ptr-Net uses an RNN encode the input data, which heavily influenced by the sequence order and length. For example, in the second test case, the length of the input sequence approximately 800, which could be too long for the RNN learn the hidden states, Second, the assignment problem is not sequential decision problem that differs from TSP and VRP, which is incompatible with the structure of Ptr-Net. Third, the output of Ptr-Net is generated one-by-one, depending the previous output sequence, which leads to larger inference time.
CONCLUSIONS
In this paper, we propose a machine learning framework to solve the order fulfillment problem-a special type of combinatorial optimization-foo real-time decisions in online retailing. Experiments show that our method substantially outperforms the baseline heuristic method and the cost gap be- tween MIP optimal solution is less than 5%. Our method also realizes thousands of times of acceler- ation compared with directly solving the MIP, which meets the criteria for real-time online decision milliseconds. To meet the characteristics of the studied problem, the edge-feanure-emeedde graph encoder is developed, which takes the high-dimensional edge features and heterogeneous in- formation into the graph attention mechanism and can address problem instances with varying input lengths and output dictionary sizes.
Apart from solving the studied order fulfillment problem, we envision that the embedded heterogenous graph attention be further applied in other combinatorial optimization problems such as the TSP, VRP and the generalized assignment problem, where our method can include consideration of the high-dimensional nonlinear route other complex scenarios.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Jason Acimovic and Stephen C Graves. Making better fulfillment decisions on the fly in an online retail environment. Manufacturing Service Operations Management, 17(1):34-51, 2015.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-basd -baed approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195, 2017.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In ICLR (Workshop), 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: a methodological tour d'horizon. arXiv preprint arXiv: 1.06/28, 2018.
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07288) 2015.
Reuven Cohen, Liran Katzir, and Danny Raz. An efficient approximation for the generalized assign- ment problem. Information Processing Letters,
2006.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In NIPS' 17 Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6351-6361, 2017.
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang, Jiangwen Wei, and Yinghui Xu. A multi-task selected learning approach for solving 3d flexible bin packing problem. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1386- 1394, 2019.
Claudia D' Ambrosio, Silvano Martello, and Michele Monaci. Lower and upper bounds for the non- linear generalized assignment problem. Computers & Operations Research, pp. 104933, 2020.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko. Tight approxima- tion algorithms for maximum general assignment problems. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06. pp. 611-620, USA, 2006. Society for Industrial and Applied Mathematics. ISBN 089871 16057.
Ahmed Ghoniem, Tulay Flamand, and Mohamed Haouari. Exact solution methods for a generalized assignment problem with location/allocation considerations. INFORMS Journal Computing, 28(3):589-603 602, 2016.
Ambros Gleixner, Leon Eifler, Tristan Gally, Gerald Gamrath, Patrick Gemander, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Matthias Miltenberger, al. The scip optimization suite 5.0. 2017.
He He, Hal Daume lii, and Jason M Eisner. Learning search in branch and bound algorithms. In Advances in Neural Information Processing Systems 27, volume 4, pp. 3293-3301, 2014.
Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, and Yinghui Xu. Solving a new 3d bin packing problem with deep reinforcement learning method. ArXiv, abs/1708.05530, 2017.
Wouter Kool and Max Welling. Attention solves your tsp. arXiv preprint arXiv: (00::::8330.888 2018.
O. Erhun Kundakcioglu and Saed Alizamir. Generalized assignment problem. pp. 1153-1162.
Springer US, Boston, MA, 2009. ISBN 978-0-387-74759-.. doi: 200. Utt.htttss://doo
1007 1ttp:///100.10000000000--------0
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial copiiaaiaialoooimiiitiiiio with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp- 539-548, 2018.
Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-basee based iterative method for solving vehicle routing problems. In ICLR 2020 : Eighth International Conference on Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2022
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv: Learning. 2019.
Lale Özbakir, Adil Baykasoğlu, and Pinar Tapkan. Bees algorithm for generalized assignment prob- lem. Applied Mathematics and Computation, 215(11):3782 3795, 2010.
Kanchana Sethanan and Rapeepan Pitakaso. Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems with Applications, 45:450-459, 2016.
Thomas C. Sharkey and H. Edwin Romeijn. Greedy approaches for class of nonlinear generalized assignment problems. Discrete Applied Mathematics, 158(5):559 572, 2010. ISSN 0166-218X. doi: https://do..or//00.00000 dam. 11. 11.002. URL http://war
sclencedirect. com
BX09004388
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp.
2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. / wtt.ee/eoormmm///./ee.00..
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NIPS'I5 Proceedings of the 28th International Conference Neural Information Processing Systems Volume 2, pp- 2600, 2015.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. In ICLR 2016 International Conference on Learning Representations 2016, 2016.
Wei Wu, Manuel Iori, Silvano Martello, and Mutsunori Yagiura. Exact and heuristic algorithms for the interval min-max regret generalized assignment problem. Computers & Industrial Engineer- ing, 125:98-110 10, 2018.
Ping Josephine Xu, Russell Allgor, and Stephen C Graves. Benefits of reevaluating real-time order fulfillment decisions. Manufacturing Service Operations Management, 11(2):340-355 2009.
A APPENDIX
A.1 GENERALIZED ASSIGNMENT PROBLEM
The simplest form called the assignment problem, in which the knapsack for items is uncapac- itated. The assignment problem is a special case of the minimum cost flow problem and can be formulated as a linear programming problem without using integers. Several exact and fast algo- rithms have been developed such the Hungarian method, the auction algorithm. Compared to the assignment problem, the generalized assignment problem has capacitated knapsacks and other real-world constraints, which make vary difficult to solve.
The generalized assignment problem describes the assignments between items and bins, where the bins have a capacity limit. There could exist other complex constraints for the items and bins. The problem can be formulated as mixed integer program:
m
n
min Zi
CijZij
(14a)
j=1
s.L.
WifZij S 4i i= 1,,.,,
(14b)
/=1
Σ 2ij = 1,
I....nn
(14c)
11

---

Under review as a conference paper at ICLR 2022
f(2i) 0, g(4)) = 0, 2g {0,
1, .... M. 1, ..., n,
(14d)
= ... m. = 1, ...9 n1
(14c)
m. m. ....,
(14f)
In the above formulation, we have items and m bins. For bin i, each item has cost Gú and weight wij. A solution an assignment from items bins. The objective is to minimize the cost of the assignment. The constraint (14b) denotes that any bin i has a capacity t.. The constraint (14c) denotes that any item can only assigned to one bin. The equation (14b)-(14e) are the funda- mental constraints in the generalized assignment problem, while (14d)-(14e) represent other general constraints for the problem.
The explorations the exact method to solve the generalized assignment problem are mainly based on decomposition techniques. [Wu et al. (2018) applies Benders decomposition and Lagrangian relaxation reduce the scale of the MIP problem. Ghoniem et al. (2016) considers the total space allocation constraints and modifies the branch-and-e and-price method. According to the paper. it costs half an hour to reach nearly-optimat solution with only 15 items and 25 knapsacks.
Several heuristics are developed for the generalized assignment problem as well. Sharkey & Romeijn (2010); Cohen et al. (2006) use greedy methods translate the algorithm for the knap- sack problem into an approximation method for a generalized assignment problem. |Fliischrr et al.) (2006) further proves the performance of the proposed heuristics by justifying optimal gap less than T/e. Sethanan & Pitakaso (2016); Özbakir et al. (2010) use differential evolution and the bees algorithm respectively, with the help of local search techniques. An average optimality gap of 12.5% is achieved. The downside of heuristics is that the approach requires an enormous amount of human knowledge and might not reach the state-of-art performance.
12

---

Under review as a conference paper at ICLR 2022
A.2 HEURISTIC METHOD FOR THE ORDER FULFILLMENT PROBLEM
The algorithm below is the current heuristic method for the order fulfillment problem. The remaining inventory near sale-forbidden dates among different warehouses is the first priority, because the cargo value loss usually larger than the delivery fee. Next, the delivery fee for each warehouse compared, while considering the tiered pricing rule, and the relationships between the orders and suborders. Finally, the corresponding item inventory is reducted from the best selected warchouse.
Algorithm 1: Heuristic method for the order fulfillment problem
Result: 2kl
P ==
while * 25 do
K' = 00
w2 0, Vk: K
i arg max; (iet(s.) O
for E L(i,.) do // Select the best warehouse
if k- arg max E1ET Skje
E T(t [T| 1), S.L.S > then
else
for k E K. s.t. ELST Skjz > Og do
if k E K'' then
if w/ + W,Orp 01 - then
Chi =
else
CKI = c(l) (wk + Wo - D)
end
else
W/ - then
CRI c(0
else
CHI cie
(ll) (W,O D)
end
end
end
k arg mink Oid
WK. = K'
Wp + W2O,
end
2 =1 // Reduct inventory
T== O₂
for t E T do
i
< ri Skje then
Skjt = Skjt T1: F1
else
n = r Skyti Skyt
end
end
end
= T'
end
13


Reviews:
[{"review_id": "sfT2qjVnVfZ", "reviewer": "Reviewer_qjBL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The first strength of the paper is that it is built upon best practices found in last 3 years of research on ML-based Combinatorial Optimization: imitation learning when a good expert is available, GNN for feature extraction, and GAT for the architecture choice. Authors should've referenced Gasse et al https://arxiv.org/abs/1906.01629 and Nair et al https://arxiv.org/abs/2012.13349 which use the similar strategy for the more generic MIP problem, however. \n\nThe second strength of the paper is the practicality of the problem addressed. This version of the fulfillment problem has nontrivial components such as order decomposition to sub-orders and sale-forbidden dates. Therefore, I expect the proposed method to generalize well for practical problems in the real world. There aren't enough discussions on why this particular version of the problem was chosen, however. I encourage authors to include more discussion on what versions of fulfillment problems are popular in which applications, and how representative the given problem formulation is.\n\nOne notable weakness of this paper is the experimental setup. First, some of the important details are missing. Authors only mention that training dataset consists of 100k instances and there are three test cases, but don't really mention anything about from where the data & problem came, or what their characteristics are, other than the problem size itself. Second, it is unclear how strong baselines are. SCIP has a variety of parameters to optimize- authors don't mention which parameters they used. Depending on parameters of the heuristic, SCIP would make a different tradeoff between accuracy & efficiency, and therefore it would be more informative if SCIP's performance at variety of levels of efficiency could be reported. Third, since exact B&B is the expert policy, \"learning to branch\" type of algorithms like Gasse et al https://arxiv.org/abs/1906.01629 and Nair et al https://arxiv.org/abs/2012.13349 which learn directly from each branching decision of the expert are critical baselines to have. Fourth, the heuristic baseline needs more explanation on what heuristics are available on the literature, and why this particular version of the heuristic was chosen. Without such discussion, we cannot really learn about the comparison with the heuristic. Authors also mention the heuristic is \"currently applied in practice\"; this hints authors might be describing a production system. In that case, more description of the system will be needed.\n\nSome of the technical claims are questionable. Authors mention that the model requires no transformation that depends on the size of the graph, which allows the model to generalize to varying sizes of orders, items, and warehouses (Section 4.2). But since that suborder node features are one-hot-vectors across the fixed number of nodes $N$, and warehouses are represented as one-hot over $M$, it is unclear to me whether this claim is technically correct. The number of parameters would depend on $N$ and $M$, and we would need to set it as the largest number we expect in the future. And I believe the mapping of orders/warehouses to these $N$ and $M$ should be done carefully. For example, if we simply assign 1, 2, ..., |I| as order indices, then embedding vectors for large indices close to $N$ wouldn't be trained well. What do authors do to make sure embedding vectors for all $N$ and $M$ indices are trained well?\n\nI am curious how often does the model output a feasible solution. Although Section 4.4 describes how the model sequentially samples predictions to output feasible action, it may run into \"dead end\" which no more feasible output exists. The same question goes to other baseline algorithms as well. Unless all models always produce feasible solutions, it'd be useful to have additional column on the fraction of feasible solutions.\n\nMinor comments: \n* Figure 3 doesn't really tell anything, (a) and (b) look just the same. I suggest authors to describe exactly what we should look into in this plot.\n* The notation $N$ is overloaded for the maximum number of orders as well as the layer of graph encoder.", "summary_of_the_paper": "Authors propose to solve an order fulfillment problem with imitation learning backed by GNNs. The specific version of the fulfillment problem is nontrivial: discussed has a hierarchy in order (an order can be decomposed into sub-orders), and items become forbidden over time. SCIP package is used as the expert policy, and authors employ behavior cloning. The specific model they use is a Graph Attention Transformer on the tripartite graph of orders, items, and warehouses. Compared to a reasonable heuristic, Pointer Network, and GAT which ignores edge features, the propose method yields much lower inference latency. ", "summary_of_the_review": "The paper employs a methodically sound approach on a practically important problem. However, important details of the experiments as well as reasonable baselines are missing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "n3jS7I3z2U", "reviewer": "Reviewer_pGWk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strength:\n\n- The model seems novel and is interesting.\n\n- The problem is well motivated: using efficient machine learning models to solve the originally NP-hard combinatorial order fulfillment problem.\n\n- The reported performance seems promising. The cost gap is only 2 - 3% compared to the optimal solution, and the inference time is minimal, similar to previous heuristic approaches. \n\nWeakness:\n\n- The authors should describe how they generated the 100,000 training dataset instances. I could not find the generative process. Please let me know if I missed it. Is there any unmentioned pattern in the training dataset, or the problem instances can be arbitrary? Please try to discuss any potential limitation.\n\n- In addition, if as the authors implied, the model performs well even on unseen problem instances (test 2 and 3), they should consider release the algorithm for generating the synthetic training datasets, because then people can simply train the same model and apply it to their own order fulfillment problems.\n\n- Table 2: is the listed inference time for every instance problem in the test set?\n\n- Have the authors tried their model on some real world datasets?", "summary_of_the_paper": "This paper proposes a heuristic graph based machine learning model, which can be used to solve the class of order fulfillment problems. The original mixed integer programming problem is known to be NP-hard, and thus computationally intractable. The authors treat each instance of the order fulfillment problems as a tripartite graph, which serves as the input of the proposed model. \n\nThe proposed model consists of three parts: a graph attention network (GAT) to embed the features, a feed forward (FF) layer, and an assignment layer generating the output. ", "summary_of_the_review": "I think the idea of converting an order fulfillment problem to a tripartite graph, which is then fed to a GAT, is interesting. However it is hard to know if the model could generalize well to other synthetic datasets or real world problems, since the authors only used one synthetic training dataset in their experiments, and the generative process is unknown.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_zQhCgB0-wv", "reviewer": "Reviewer_PyJm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths**\n\n- Motivation: a very interesting and challenging problem that is worth considering for ML methods.\n- Clarity: overall, the paper is well-written and easy to read.\n- Experiments: the proposed GNN works well on instances larger than those seen in training and compares favorably to the baselines.\n\n**Weaknesses**\n\n1. Knowing max number of orders (section 4.1) goes a bit against your claim about size-invariance of the proposed model.\n\n2. Datasets: what is the instance generation procedure? Has it been used to generate hard instances of the order fulfillment problem in the literature before? Without an answer to both of these questions, it is difficult to put your results in context.\n\n3. Baseline heuristic: In appendix A.2, you say that Algorithm 1 “is the current heuristic method for the order fulfillment problem”; can you cite a source for this statement? Where does this heuristic come from?\n\n4. Inference time for Exact B&B in Table 2: is the time reported for this method the total time it requires to prove optimality? If so, then the inference time reported for exact B&B is unfair. You should instead track the incumbent solutions it finds over time and measure the cost gap at different time limits, e.g., the cost gap of exact B&B if it is given 10ms only, then 20ms only, etc. It is often the case that MIP solvers will find a near-optimal feasible solutions early on, then use most of the remaining time to prove optimality. However, your paper focuses on the former aspect not the latter, hence my suggestion here. \n\n5. Sample complexity: you use 100k training instances but no results are reported for smaller datasets. How much data does your GNN need to achieve good performance? This is particularly important because you require optimal solutions as labels!\n\n**Other questions/comments**\n\n6. Section 4.4. Does the “masking procedure” always work, i.e., is a feasible solution guaranteed?\n\n7. Figure 3 is not very useful as there are many edges and it is impossible to see how the two solutions differ. I recommend either removing this figure or finding a better visualization of the differences between solutions.\n\n**Typos**\n\n- Eq. (1c): I think the subscript in the sum should have the same K as the one in notation Table 1 (1st row).\n- Table 2: “TARIN” —> “TRAIN”", "summary_of_the_paper": "A Graph Neural Network (GNN) model is designed to enable the supervised learning of optimal solutions for an order fulfillment problem in supply chain management. This is a problem that must be solved in real-time, making a GNN whose forward computations are quick an attractive option.\n\nThe proposed GNN model has three types of nodes corresponding to orders, items, and warehouses. Edges between the nodes of different types represent relationships between them (e.g., an item is in an order). Nodes and edges may have feature vectors representing additional information, e.g., the identity of a warehouse or certain costs on the edges. The GNN is designed to take these features into account.\n\nThe model is trained using optimal solutions as labels in a binary classification formulation. Predictions are post-processed to guarantee a feasible solution in the constraints of the order fulfillment problem.\n\nExperimental results on randomly generated instances show that a GNN trained on small instances of this problem performs well even on larger instances, yielding near-optimal solutions in a short amount of time compared to simple GNN solutions, a non-ML heuristic, and an exact solver.", "summary_of_the_review": "There is an challenging and important problem here and a promising method. However, the experiments are rather limited in scope. The modeling contribution is interesting but it is unclear if it generalizes to other combinatorial optimization problems. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5bUcD7bvPM9", "reviewer": "Reviewer_ciU3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths**\n- The paper presents a new approach (inspired by previous work) using ML for the order fulfillment problem, which I can imagine appears in practice in online retail\n- The paper makes suitable and mostly principled modifications to existing architectures to be suitable for the order fulfilment problem, especially integrating edge features and making the model suitable for a combination of different node types (orders, suborders and warehouse).\n- The problem is clearly and formally specified through a mathematical formulation\n- The model is clearly explained on the right level of abstraction for the reader familiar with graph neural networks\n- Experiments illustrate potentially good results, achieving good quality solutions in time orders of magnitude faster than MIP solving, and with better quality than a heuristic. It would be interesting if the paper could explore why the quality of the solution is much better than the heuristic, which seems a reasonable strategy.\n\n**Weaknesses**\n- The positioning of the paper is somewhat unclear to me: does this paper present an existing problem or introduce/formalize a new problem? Does it address a real application (as suggested by 'heuristic used in practice', in which case I'd like to see more details on where/how it is used in practice, to judge the relevance) or is it fictional and mainly about the methodology (this is the impression I get from the related works section)?\n- The motivation is a bit weak in my opinion: why do we require solving in 'tens of milliseconds', i.e. 'realtime', whereas (I assume) fulfillment takes at least a few hours? Even with 'hundreds of orders' per seconds, we could solve many instances in parallel and get 2-3% better solutions (= 2-3% lower cost which I think is a lot in practice!) by using SCIP for 60 seconds instead of the model.\n- The empirical evaluation is incomplete: SCIP gives better results whereas the model is faster, so it is unclear what is preferred. Both methods should *at least* be compared using the same computation time (e.g. SCIP may find solutions with 2-3% gap early as well), and ideally a full time vs performance curve should be reported.\n- Whereas a graph network, in principle, is permutation invariant and can scale to any size, the model still depends on the permutation of orders for the one-hot feature indicating the order, which also limits the maximum number of orders the model can handle.\n- Some claims are unsupported or incorrect, e.g. \"The order fulfillment problem is one of the fundamental optimization problems in supply chain management\" could at least use a reference, \"tens of thousands times faster\" does not accurately reflect the results (200-5000x).\n- Some parts are unclear/not explained or introduced, e.g. tiered pricing rules and some relevant details are unclear/missing, e.g. how are the parameters for the 100.000 training instances (and the test instances) generated?\n- Overall, the paper presents a relatively straightforward application of an existing idea (graph neural network with supervised learning). Whereas the problem requires suitable modifications to the standard GNN/GAT, this is not the first paper to handle node types and edge features (e.g. first hit on Google gives [1]) and the method is relatively straightforward.\n\n**Minor comments/questions**\n- I think the paper means 'neighbor' in some cases where 'neighborhood' is written.\n- TARIN -> TRAIN (Table 2)\n- Why is a SCIP time limit of 15 minutes needed since according to Table 2 instances of that size are solved in 0.45 seconds on average?\n- If a time limit is used and has effect, I suggest not to call SCIP results optimal\n\n[1] Frederik Diehl, Applying Graph Neural Networks on Heterogeneous Nodes and Edge Features, NeurIPS 2019 Graph Representation Learning Workshop", "summary_of_the_paper": "This paper presents a graph based deep learning model for solving the order fulfillment problem of assigning retail (sub-)orders to different warehouses for fulfilment. It formulates the problem as a Mixed Integer Problem (MIP, although I think it is fully integer) which can be solved using a (open-source) MIP solver such as SCIP. Following up on related work, the authors train a graph neural network, specifically designed to incorporate edge features and different types of nodes, to predict the optimal solution, using supervised learning on a dataset of 100.000 generated instances solved with SCIP. Empirically, on three different test problem sizes, the trained model provides solutions within 2-3% to the results found by SCIP, while being a 2-4 orders of magnitude faster. ", "summary_of_the_review": "Overall, this is a nice paper that applies an interesting learning based approach (inspired by previous works) to the order fulfillment problem, with encouraging results. However, I think the paper needs to improve in multiple aspects to address the mentioned weaknesses: positioning, motivation and empirical evaluation. Even then, I am not sure if ICLR is the most suitable venue as I consider this a relatively straightforward application to the order fulfillment problem, admitting that it does require suitable modifications to the graph neural network architecture (but nothing groundbreaking in my opinion). Whereas ICLR welcomes applications as well, I think in that case it should consider a problem which is more established and thus has stronger baselines from other papers, such that it really convinces on the need/benefits of using ML.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A GNN model is developed for the supervised, real-time learning of optimal solutions for an order-fulfillment problem. GNNs with fast forward computations are naturally one good choice given the real-time nature of the problem.

While the complexity of the problem and formulation were generally appreciated by the referees, there were major concerns about the experimental setup, datasets, technical claims, sample complexity, and suitability for ICLR. Overall, the paper does not seem ready for publication in ICLR, and the authors are encouraged to consider and work on the reviews carefully.
Decision: Reject