Matrix encoding networks for neural combinatorial optimization
Authors: Yeong-Dae Kwon
Jinho Choo
Iljoo Yoon
Minah Park
Duwon Park
Youngjune Gwon
Venue: NeurIPS 2021 Poster (2021)
Keywords: combinatorial optimization
reinforcement learning
POMO
matrix encoding
traveling salesman problem
flow shop problem

Abstract: Machine Learning (ML) can help solve combinatorial optimization (CO) problems better. A popular approach is to use a neural net to compute on the parameters of a given CO problem and extract useful information that guides the search for good solutions. Many CO problems of practical importance can be specified in a matrix form of parameters quantifying the relationship between two groups of items. There is currently no neural net model, however, that takes in such matrix-style relationship data as an input. Consequently, these types of CO problems have been out of reach for ML engineers. In this paper, we introduce Matrix Encoding Network (MatNet) and show how conveniently it takes in and processes parameters of such complex CO problems. Using an end-to-end model based on MatNet, we solve asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems as the earliest neural approach. In particular, for a class of FFSP we have tested MatNet on, we demonstrate a far superior empirical performance to any methods (neural or not) known to date.

Matrix Encoding Networks for Neural Combinatorial Optimization
Yeong-Dae Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, Youngjune Gwon
Samsung SDS
(y.d.kwon, jinho12.choo, yooo,. minah86, park, dw21 wark.park, gyj.gwon)@samssung
Abstract
Machine Learning (ML) help solve combinatorial optimization (CO) prob- lems better. A popular approach to use a neural net to compute on the parame- ters of a given CO problem and extract useful information that guides the search for good solutions. Many CO problems of practical importance can be specified in matrix form of parameters quantifying the relationship between two groups of items. There is currently no neural net model, however, that takes in such matrix- style relationship data as an input. Consequently, these types of CO problems have been out of reach for ML engineers. In this paper, we introduce Matrix Encoding Network (MatNet) and show how conveniently takes and processes parame- ters of such complex CO problems. Using an end-to-end model based on MatNet, we solve asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems the earliest neural approach. In particular, for class of FFSP we have tested MatNet on, we demonstrate a far superior empirical performance to any methods (neural not) known to date.
Introduction
Many combinatorial optimization (CO) problems of industrial importance are NP-hard. leaving them intractable to solve optimally at large scale. Fortunately, researchers operations research (OR) have developed ways to tackle these NP-hard problems in practice, mixed integer programming (MIP) and meta-heuristics being two of the most general and popular approaches. With the rapid progress in deep learning techniques learning (ML) has emerged. ML has been applied in both ways successfully (1, as helper for the traditional OR methods aforementioned as independent CO problem solver trained in an end-to-end fashion.
the last several years,
approach based on machine
One way to leverage MI. for solving CO problems is to employ "front-end" neural net, which directly takes the data specifying each problem. The neural net plays a critical role of analyzing all input data whole, from which it extracts useful global information. In an end-to-end ML-based approach, such global information may be encoded onto the representations of the entities making up the problem. Greedy selection strategies based these representations are then longer too nigh-sighted, allowing globally (near-) optimal solutions to be found quickly. Existing OR methods can also benefit from incorporating the global information. Many hybrid approaches already exist that leverage information extracted by a neural net, both in ML-MIP forms 2 3 and ML-heuritic forms 5 6
The literature on neural combinatorial optimization contains many different types of the front-end models, conforming the variety of data types upon which CO problems are defined. Yet, there has been no research for a model that encodes matrix-type data. This puts a serious limitation on the range of CO problems that an ML engineer can engage. Take, for example, the traveling salesman problem (TSP), the most intensely studied topic by the research community neural combinatorial
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

optimization. Once we lift the Euclidean distance restriction (the very first step towards making the problem more realistic), the problem instantly becomes a formidable challenge that has never been tackled before because it requires a neural net that can process the distance matrix
The list of other classical CO problems based data matrices includes job-shop/ftow-shog schedul- ing problems and linear/quadratic assignment problems, just to name a few. All of these examples are fundamental CO problems with critical industrial applications. To put in general terms, imagine CO problem made up of two different classes of items, À = {āI..... , and ß (ō1,... .,y ). where M and N are the sizes of Á and B respectively. We are interested in the type where features of each item are defined by its relationships with those in the other class. The data matrix we want to encode, D E IR MRN, would be given by the problem Where its (i. )th element represents a quanti- tative relationship of some sort between pair of items (ā,, b,). The sets À and B are unordered lists, meaning that the orderings of the rows and the columns of D are arbitrary. Such permutation invari- ance built into our data matrices is what sets them apart from other types of matrices representing stacked vector-lists or a 2D image.
In this paper, we propose Matrix Encoding Network (MatNet) that computes good representations for all items in Á and B within which the matrix D containing the relationship information is en- coded. To demonstrate its performance, we have implemented MatNet as the front-end models for two end-to-end reinforcement learning (RI.) algorithms that solve the asymmetric traveling sales- man (ATSP) and the flexible flow shop (FFSP) problems. These classical CO problems have not been solved using deep neural networks. From our experiments, we have confirmed that MatNet achieves near-optimal solutions. Especially, for the specific FFSP instances we have investigated, our MatNet-based approach performs substantially better than the conventional methods used in operations research including mixed integer programming and meta-heuristics.
2 Related work
A neural net can accommodate variable-length inputs as is needed for encoding the parameters of CO problem. Vinyals et al. [9], one of the earliest neural CO approaches, have introduced Ptr- Nets that use a recurrent neural network (RNN) [10] as the front-end model. Points on the plane arranged into sequence, and RNN processes the Cartesian coordinates of each point one by one. Bello et al. 11 continue the RNN approach, enhancing the Ptr-Net method through combina- tion with RI. Nazari al. (12) further improve this approach by discarding the RNN encoder, but keeping the RNN decoder to handle the variable input size.
The graph neural network (GNN) 13 is another important class of encoding networks used for neural CO, particularly on (but not limited to) graph problems. GNN learns the message pass- ing policy between nodes that can be applied to arbitrary graph with any number of nodes. Khalil et al. (7) are among the firsts to show that a GNN-based framework can solve many different types of CO problems on graph in uniform fashion. Li et al. [15] extend the work by switching to a more advanced structure of graph convolutional networks (GCNs) 16). Manchanda et al. [17] demonstrate efficient use of GCN that can solve CO problems on graphs with billions of edges. Kar- alias and Loukas 18 use unsupervised learning on GNN to improve the quality of the CO solutions.
Encoding networks most relevant to our work are those based on the encoder of the Transformer [19]. Note that this encoder structure can be viewed as a graph attention network (GAT) (20 operating on fully connected graphs. Using this type of encoder, Kool et al. [21 encode Cartesian coordinates of all nodes given by the problem simultaneously and solve the TSP and many other related routing problems. Kwon et al. [8] use the same encoder as Kool al. but produce solutions of significantly improved quality with the use of the RL training and the inference algorithms that are more suitable for combinatorial optimizations.
'One could, in principle, consider general GNN approach such Khalil et al. 7 that can encode any arbitrary graphs. However, as can be seen from the comparison the TSP results Khalil et al. >8% error on random 100-city instances) with some of the state-of-the-arr ML results (e.g., Kwon et al. [, <0.2% error), a general GNN is most suitable for problems that deal with diverse graph structures, not those with fixed, dense graph structures (such as matrices).
"The relationship can have multiple (f) features, in which case we are given f number of different data matrices D' D2. D?..... D For simplicity we only use f=1 in this paper. but our model covers f>1 cases as well. (See Appendix A.I).

---

MatNet architecture is designed to encode a bipartite graph, will be explained in detail in the following section. Although none support embedding of a single matrix like MatNet, many inter- esting deep learning works exist that rely bipartite graph embeddings or matrix embeddings. Gasse el al. [2 learn effective branch-and-bound variable selection policies for solving MIP in- stances, where constraints and variables of an MIP instance form bipartite graph weighted by constraint coefficients. Gibbons et al. [23] solve weapon-target assignment problem, classic CO problem that is presented with bipartite graph. Duetting al. [24] find good auction policies given a matrix that describes the value that each bidder assigns to each auctioning item.
Model architecture
MatNet can be considered a particular type of GNN that operates on complete bipartite graph with weighted edges. The graph has two sets of nodes, A = {ai,..., am and B = (bi,...,bn, b and the edge between a, and by has the weight e(a,, by) Dij. the (i, element of D, as illustrated in Figure
D 11
b
a2
bz
MatNet is inspired by the encoder architecture of the Attention Model (AM) by Kool et al. [21). but because the AM deals with a quite dif- ferent type of a graph (fully connected nodes and edge weights), we have made significant modifications to it. The encoder of the AM follows the node-embedding framework of graph attention networks (GATs) (20). where a model is constructed by stacking multiple (L) graph attentional layers. Within each layer, a node v's vector repre- sentation h, updated to K2 using aggregated representations of its neighbors as in
:
bN
aM
D NN
Figure I: A complete bi- partite graph with weighted edges.
Kg = F(h. (hw E N..)..
(3.1)
Here, No is the set of all neighboring nodes of c. The (learnable) update function F is composed of multiple attention heads, and their aggregation process utilizes the attention score for each pair of nodes (v, w). which is a function of hy and heg.
MatNet also generally follows the GATs framework, but it differs in two major points: (1) It has two independent update functions that separately apply to nodes in A and B. (2) The attention score for pair of nodes (a,; by) is not just function of ha; and hag, but the edge weight e(a;, b,) well. The update function in each layer of MatNet can be described as
W/ = FA (Naz, ((ha,, e(a;, bj)) by E B)) for all E A,
(3.2)
h/ Fo (Ro,, (hha e(a,, a E A}) for all by E
3.1 Dual graph attentional layer
The use of two update functions FA and FB Eq. (3.2) somewhat unorthodox. The GAT's frame- work requires that the update rule I be applied uniformly to all nodes because it loses its universality otherwise. In our case, however, we focus a particular type of problem, where the items in Á and B belong to two qualitatively different classes. Having two separate functions allows MatNet to develop a customized representation strategy for items in each class.
The two update functions are visualized as a dual structure of a graph attentional layer depicted stack of L graph attentional layers, and each layer is
in Figure aa. The MatNet architecture made of two sub-blocks that implement FA and Fg. The two sub-blocks are structurally identical, where each one similar to the encoder layer of the AM, which in turn based on that of the Transformer model [19]. Note, however, that while both the AM and the Transformer model use the simple self-attention for encoding, MatNet requires a clear separation of queries (nodes in one set) and the key-value pairs (nodes in the other set) at the input stage to perform cross-attentions. For de- tailed descriptions of computing blocks used in Figure 2 a), we refer the readers to the Transformer architecture [19].
3

---

(a)
(b)
FA
FB
Add & Norm
Norm
MatMul
Feed Forward
Feed Forward
Softmax
Add & Norm
Add & Norm
L x
Trainable
Multi-Head Mixed-Score Attention
Multi-Head Mixed-Score Attention
Element-wise Func.
Sext
Sint
Scale
MatMul
t
a, embedding
b, embedding
Q
K
V
D (N*M)
D (MxN)
ag embedding
by embedding
ag embedding
Figure 2: (a) An overview of the MatNet architecture. (b) Mixed-score attention. "Multi-Hese Mixed-Score Attention" block (a) consists of many independent copies the mixed-score at- tentions arranged in parallel and fully connected (FC) layers at the input and output interfaces (not drawn).
3.2 Mixed-score attention
We now focus on how MatNet makes use of the edge weight e(a,, by) = Diy in its attention mech- anism. "Multi-Head Mixed-Scou Attention" block in Figure a) is the same as "Multi-Hoe At- tention" block of the Transformer except that the scaled dot- dot-product attention in each attention head replaced by the mixed-score attention shown in Figure (b). Originally, the scaled dot- dot-product attention outputs the weighted sum of the values, where the weights are calculated from the atten- tion scores (the scaled dot products) of query-key pairs. For MatNet, in addition these internally generated scores, it must use the externally given relationship scores, Dij, which is also defined for all query-key pairs. The mixed-score attention mechanism mixes the (internal) attention score and the (external) relationship score before passing it to the next "SoftMax" stage. We note that mixing of the two scores appear the works Sykora et al. 255 and Dwivedi al. (26) in similar ways.
Rather than using a handcrafted prioritizing rule to combine the two types of the scores. we let the neural net figure out the best mixing formula. "Trainable element-win function" block in Figure (bb) is implemented by multilayer perceptron (MLP) with two input nodes and a single output node. Each head in the multi-head attention architecture is given its own MLP parameters, so that some of the heads can learn to focus on specific type of the scores while others learn to balance, depending on the type of graph features that each of them handles. Note that an element- function, so that the output of the mixed-score attention is indifferent to the ordering of a; and bj. ensuring the permutation-invarict invariance the operation.
The attention mechanism of the Transformer is known for its efficiency as it can be computed by highly optimized matrix multiplication codes. The newly inserted MLP can also be implemented using matrix multiplications without the codes that explicitly loop over each row and column of the matrix D each attentional head. Actual implementation of MatNet keeps the efficient matrix forms of an attention mechanism. Also, note that the duality of the graph attentional layers of MatNet explained in Section 3.1 is conveniently supported by DT. transpose of the matrix D.
3.3
The initial node representations
The final pieces of MatNet that we have not yet explained are the initial node representations that are fed to the model to set it in motion. One might be tempted to use the edge weights directly for these preliminary representations of nodes, but the vector representations are ordered lists while edges of graph offer no particular order, making this choice inappropriate.

---

MatNet uses zero-vectors to embed nodes in A, and one-hot vectors for nodes in B (or vice versa) initially. The use of the same zero-embeddings for all nodes of is allowed, as long as all nodes in B are embedded diffe differently, because they acquire unique representations after the first graph attentional layer. The vero-vector embedding enables MatNet to support variable-sized inputs. Regardless of how the number of the nodes in A changes from a problem instance to another, MatNet can process them all in a uniform manner. In Appendix H, for example, we demonstrate solving FFSP instances containing 1,000 different jobs using MatNet that is trained on smaller instances.
The one-hot vector embedding scheme for nodes in B, on the other hand, provides somewhat limited flexibility towards varying N, the number of columns in the input matrix. Before a MatNet model trained, its user should prepare a pool of NNax different one-hot vectors. When a matrix D. with N₂ (S Mmxx columns is given, No different one-hot vectors are randomly drawn from the pool in sequence and used as the initial node representations for B-nodes.
When a good value for Nmax is difficult to establish before the deployment, or when the application requires better generalizability without the strict limit on N, one can employ an alternative initial node representation scheme. One-hot vectors can be substituted by vectors filled with the random numbers that are drawn independently for each problem instance. This completely lift the restriction of Nmax at a price which slightly worsens the model's performance. (See Appendix A.3.)
Instance augmentation via different sets of embeddings. The initial one-hot (or random) vec- tor embedding scheme naturally accommodates the "instance augmentation" strategy proposed by Kwon et al. [8] For each random sequence of one-hot vectors chosen to embed B-nodes, a MatNet model encodes the matrix D in a different way. (That is, the number of node representation sets for a given problem instance can be augmented from one to many.) One can take advantage of this property and easily create many dissimilar solutions simply by running the model repeatedly, each time with new one-hot vector sequence. Among those multiple solutions, the best one is chosen. This way, a higher quality solution can be acquired at the cost of increased runtime. The diversity of solutions created by the instance augmentation technique are far more effective than those produced by the conventional multi-sampling technique. (See Appendix C.)
4 Asymmetric traveling salesman problem
Problem definition. In the traveling salesman problem (TSP). the goal to find the permutation of the given N cities so that the total distance traveled for round trip is minimized. For each pair of "from" city a, and "to" city by. a distance d(a, b,) is given, which constitutes an N-by-N distance matrix. To verify that Mat- Net can handle general cases, we focus on the asymmetric trav- eling salesman problem (ATSP). This problem does not have the restriction d(a;, by) = d(a,, b;) so that its distance matrix is asym- metric. We use "tmat" ccaass ATSP instances that have the triangle inequality and are commonly studied by the OR community [27]. (See Appendix B for detailed explanation of the tmat class.) We solve the ATSP of three different sizes, having N = 20, 50, and 100 number of cities.
P61
Pbz
Softmax
PbN
Scale
MatMul
Masked Multi-Head Attention
k
MatNet configuration. MatNet is used to encode the distance matrix. Regardless of the size of the ATSP, we have used the same MatNet structure. The MatNet model constructed by stacking L = 5 encoding layers. The embedding dimension, dmodel. for input/output of each layer is set 256. Both sub-modules (FA and F8) use h = 16 attention heads, where each head processes query, key, and value as 16-dimensional vectors (i.e, dg dg d, = 16). The score-mixing MLP in each head has one hidden layer with 16 nodes. For implementation of the "Scale" block in Figure 2b. we apply scaling of 1/V4 and then soft-clipping to [-10, 10 using a tanh function, following the convention of Bello et al. [[]]
QUERY
b, embedding
Ma1
by embedding
Ma2
:
by embedding
MmN
The decoder. Scalars may and paj are the mask and the selection probability for by (j = 2, N).
Figure 3:
blocks in Figure 2(a) is imple-
5

---

Table 4.1: Experiment results on 10,000 instances of ATSP
ATSP20
ATSP50
ATSP100
Method
Len.
Gap
Time
Len.
Gap
Time
Len.
Gap
Time
CPLEX
1.54
(12m)
1.56
(1h)
1.57
(5h)
Nearest Neighbor
2.01
30.39%
(-)
2.10
34.61%
(-)
2.14
36.10%
(-)
Nearest Insertion
1.80
16.56%
(-)
1.95
25.
(-)
2.05
30.79%
Furthest Insertion
1.71
11.23%
(-)
1.84
18.22%
(-)
1.94
23.37%
(-)
LKH3
1.54
0.00%
(1s)
1.56
0.00%
(11s)
1.57
0.00%
(Im)
MatNet
1.55
0.53%
(2s)
1.58
1.34%
(8s)
1.62
3.24%
(34s)
MatNet (x 128)
1.54
0.01% %
(4m)
1,56
0.11%
(17m)
1.59
0.93%
(1h)
mented with one hidden layer of dimension du = 516. We use instance normalization for "Add & Norm." For the initial node representations,
zero vectors for "from" cities and one-hot vec- tors to embed "to" cities. The size of the pool from which we draw the one-hot embedding vectors is adjusted to the minimum, the number of the cities of the problem (i.e., Nmmxx N).
Decoder. Once MatNet processes the distance matrix D and produces vector representations of "from" and "to" cities, solution of ATSP (a permutation sequence of all cities) can be constructed autoregressivelyy, one city at a time. The decoder model of Kool er al. [2] (shown in Figure 3 is used repeatedly each step. Two "from" city representations, one for the current city and the other for the first city of the tour, are concatenated to make the QUERY token Vector representations of all "to" cities go into the decoder, and for each city the decoder calculates the probability to select it as the next destination. mask (0 for the unvisited and -oo for the visited cities) used inside the multi-head attention block to guide the decision process, well right before the final softmax operation to enforce one-visit-per-city rule of the problem. See Appendix for a diagram that explains the ATSP decoding process.
Training. We use the POMO training algorithm g to perform reinforcement learning on the MatNet model and the decoder. That is, for an ATSP with size N, N different solutions (tours) generated, each of them starting from a different city. The averaged tour length of these solutions used baseline for REINFORCE algorithm [28]. We use Adam optimizer [29] with learning rate of 4 x 10 without decay and a batch size of 200. With an epoch being defined as training 10,000 randomly generated problem instances, we train 2,000, 8,000, and 12,000 epochs for N 20, 50, and 100, respectively. For N = 20 and 50, they take roughly 6 and 55 hours, respectively, on single GPU (Nvidia V V100). For N 100, we accumulate gradients from 4 GPUs (each handling a batch of size 50) and the training takes about 110 hours. Multi-GPP processes are used for speed, as well to overcome our GPU memory constraint (32GB each)
Inference. We use the POMO inference algorithm []. That is, we allow the decoder to produce N solutions in parallel, each starting from different city, and choose the best solution. We use sampled trajectories for POMO inference rather than greedy ones (argmax on action probabilities) [21 because they perform slightly better in our models.
4.1 Comparison with other baselines
In Table 4.1 we compare the performance of our trained models with those of other representative baseline algorithms 10,000 test instances of the tmat-class ATSP. The table shows the average length of the tours generated by each method (displayed in units of 108). The gap percentage is with respect to the CPLEX results. Times are accumulated for the computational processes only, excluding the program and the data (matrices) loading times. This makes the comparisons between
'Information of the first city is required in the QUERY token, because the decoder needs to know where the final destination of the tour is. The average of all node embeddings (a.k.a. "the graph embedding") is dropped from the QUERY token. See Appendix E discussion on this omission.)
"If needed, a smaller batch size can be used to reduce GPU memory usage. A batch size of 50 achieves the similar results when trained with learning rate of x 10-4. although this takes bit longer to converge.

---

different algorithms more transparent. Note that the heuristic baseline algorithms require only a sin- gle thread run. Because it is easy make them run parallel on modern multi-core processors, we record their runtimes divided by 8. (They should be taken references only and not too seri- ously.) For consistency, inference times of all MatNet-based models are measured on a single GPU, even though some models are trained by multiple GPUs.
Detailed explanations on all the baseline algorithms for the ATSP and the FFSP experiments, in- cluding how we have implemented them, are given in Appendix B and G, respectively.
Mixed-integer programming (MIP). Many CO problems in the industry solved by MIP be- cause it can model a wide range of CO problems, and many powerful MIP solvers are readily avail- able. If one can write down mathematical model that accurately describes the CO problem hand, the software can find a good solution using highly engineered branch-and-boum This is done in an automatic manner, freeing the user from the burden of programming. Another merit of the MIP approach is that it provides an optimality guarantee. MIP solvers keep track of the gap between the best solution found so far and the best lower (or upper) bound for the optimal.
type algorithms.
To solve test instances using MIP, we use one of the well-knows polynomial MIP formulations of the ATSP [30] and let CPLEX (3I solve this model with the distance matrices that provide. CPLEX is one of the popular commercial optimization software used by the OR community. With 1 10-second timeouts, CPLEX exactly solves all N = 20 instances. For N 50 and 100 test instances, it solves about 99% and 96% of them to the optimal values, respectively. Solutions that are not proven optimal have the the average optimality gap of 1.2% for N 50 and 0.5% for N 100.
Heuristics. Nearest Neighbor (NN), Nearest Insertion (NI), and Furthest Insertion (FI) are simple greedy-selection algorithms commonly cited as baselines for TSP algorithms. Our implementations of NN, NI, and FI for ATSP in C+ solve 10,000 test instances very quickly, taking at most a few seconds (when N 100). We thus omit their runtimes in Table
state-of-thh-ar algorithm carefully engineered for various classical routing problems. It relies on local search algorithm using k-opt operations to iteratively improve its solution. Even though it offers no optimality guarantee, our experiment shows that it finds the optimal solutions for most of our test instances in very short time.
The other heuristic baseline, LKH3 32
MatNet. In Table 4.1 the performance of the MatNet-based ATSP solver is evaluated by two inference methods: 1) single POMO rollout, and 2) choosing the best out of 1 128 solutions generated by the instance augmentation technique (i.e., random one-hot vector assignments for initial node embeddings) for each problem instance. The single-rollout inference method produces a solution in N selection steps just like the other greedy-
algorithms (NN, NI, and FI), but the quality of the MatNet solution is far superior. With instance augmentation (x 128), MatNet's optimality gap goes down to 0.01% % for 20-city ATSP, or to less than 1% for 100-city ATSP.
Flexible flow shop problem
Problem definition. Flexible flow shop problem (FFSP), or sometimes called hybrid flow shop problem (HFSP), a classical optimization problem that captures the complexity of the production scheduling processes in real manufacturing applications. It is defined with set of N jobs that has to be processed in S >> stages all in the same order. Each stage consists of M > 1 machines and job can be handled by any of the machines in the same stage. A machine cannot process more than one job at the same time. The goal is to schedule the jobs so that all jobs are finished in the shortest time possible (i.e., minimum makespan).
For our experiment, we fix on a configuration of stages and machines of moderate complexity. We assume that there are S = 3 stages, and each stage has M = 4 machines. At the kth stage, the processing time of the job on the machine is given by D (k) Therefore, an instance of the ig
problem is defined by three processing time matrices (D D (2) and D (3)), all of which have the
size M-by-N. D (k) is filled with a random integer between 2 and for all i, j. and k. We solve three
'In general, the number of machines in each stage can vary from stage to stage. When all stages have just machine, the problem simplifies flow shop problem.
7

---

Job #1-20
Time
15
20
3
W
14
16
2
1
1.9
S
5 9 6 8 9 6
20
5
10
6
5
536
11
15
5
9
13
18
5 5694 9 8 3 8 7 5 4 3
1.2
4
15
18
667 6 2
6
9
13
20
5
4 2 6
8 2 S
16
7
2
10
6 2 7 5
B
56
17
14
11
19
252 6 9 3 5 9 2 3 8
9
1.3
16
20
18
44
G
8 2
6
4
14
5
19
9 3 6
6 3
7
15
10
5 7 2 6
17
11
Figure 4: (LEFT) Processing time matrices for 3-stage 4-4-4-machine 20-job flexible flow shop problem. (RIGHT) Gantt chart showing a valid schedule for the given problem. Numbers on colored strips are assigned job indices. This schedule has been produced by our MatNet-based neural net model, and it has a makespan of 25.
types of FFSP with different number of jobs, namely, N 20, 50, and 100. An example instance of FFSP with job count N 20 is shown in Figure along with Gantt chart showing an example of a valid schedule.
Encoding & decoding. To encode three processing time matrices, ( 1,2,3), we use copies of a MatNet model, one for each matrix, and acquire vector representations F.1k) 1,2,,, for machines and ((()) 1==1,2,.-..20 for jobs in stage This stage-wise encoding scheme is the key to develop a proper scheduling strategy, which should follow different job-selection rules depending on whether you are in early stage a late one. All three MatNets are configured identically, using the same hyperparameters as the ATSP encoder explained in the previous section Machines initially embedded with one-hot vectors (M max
4), and jobs embedded with zero vectors. We also use three decoding neural nets, 9x = 1, 1)..3). 3). all of them having the same architecture as the ATSP decoder (Figure 3).
Generating an FFSP solution means completing a Gantt chart like the one in Figure 4 We start at the upper left corner of the chart (time / 0) and move from stage 1 to stage 3. At stage k. we loop over its 4 machines
2, 3,4 4, each time using (,(k) as the QUERY token for 9k. The input embeddings for S& are (1) (j = 1, ................................ 2,....... 20), plus one extra (21st) job embedding made of learnable parameters
for "skip" option. 9a outputs selection probabilities for jobs j = 1,2, ... 20, and 21. When the "skip" option is selected, no job is assigned to machine even if there are available jobs. This sometimes necessary to create better schedules. Obviously, unavailable jobs (already processed or not ready for stage k) are masked in the decoder. When no job can be selected (no job at stage k or the machine is busy),
simply do not assign any job to the machine and move on. When finish assigning jobs for machines, we increment time t and repeat until all jobs are finished. See Appendix for the flow of the FFSP decoding process.
Training The decoding process series job assignments to machines in each stage, but note that the order of the machines assign jobs to be arbitrary. We use 4! = 24 number of per- mutations of (#1, #2, #3, #4) for the order machines in which we exccute job assignments at each stage. From the same set of vector representations of machines (hat) and jobs (h.))) ), this per- mutation trick can create 24 heterogeneous trajectories (different schedules), which we use for the POMO reinforcement learning to train the networks. We use batch size 50 and Adam optimizer with a learning rate of 10-4 One epoch being processing 1,000 instances, we train for (100, 150, 200) epochs for FFSP with job size = (20, 50, 100), which takes (4, 8, 14) hours. For FFSP with N 100, accumulate gradients from 4 GPUs.
"except for the number of encoding layers L = 3, descreased from 5. This change is optional, but we have found that L = 5 is unnecessarily too large for the task.

---

Table 5.2: Experiment results on 1,000 instances of FFSP
FFSP20
FFSP50
FFSPI00
Method
MS
Gap
Time
MS
Gap
Time
MS
Gap
Time
CPLEX (60s)
46.4
21.0
(17h)
X
x
CPLEX (600s)
36.6
11.2
(167h)
Random
47.8
22.4
(Im)
93.2
43.6
(2m)
167.2
77.5
(3m)
Shortest Job First
31.3
5.9
(40s)
57.0
7.4
(1m)
99.3
9.6
(2m)
Genetic Algorithm
30.6
5.2
(7h)
56.4
6.8
(16h)
98.7
9.0
(29h)
Particle Swarm Opt.
29.1
3.7
(13h)
55.1
5.5
(26h)
97.3
7.6
(48h)
MatNet
27.3
1.9
(8s)
51.5
1.9
(14s)
91.5
1.8
(27s)
MatNet (x 128)
25.4
(3m)
49.6
(8m)
89.7
(23m)
Inference. We use sampled solutions and the POMO inference algorithm with 24 machine-order permutations similarly to the training. Interestingly, the sampled solutions are significantly better than the greedily-chosen ones, which could be consequence of the stochastic nature of the problem in our approach. Fach decoder 9x makes decisions without any knowledge of other (F k) stages.
5.1 Comparison with other baselines
In Table 5.2
we record average makespan (MS) of the schedules produced by various optimization methods for the same 1,000 test instances. The gaps given in absolute terms with respect to MatNet with x x128 augmentation result. We display the runtime of each method, following the same rules that use for Table 4.1 (e.g., computation time only, scaling by 1/s for single-thread processes, and single-GPU inference for the MatNet-based method).
Mixed-integer programming (MIP). Modeling flow shop problems using MIP is possible, but is much more complex than for TSPs. We use an FFSP model found in literature 33 with modifica- tions that (empirically) improves the search speed of CPLEX. Even with the modifications, however, CPLEX cannot produce optimal solutions for any of the test instances within reasonable time. For FFSPs with job size N = 20, we show two results, recorded with timeouts
and 600 seconds per instance. For N- = 50 and 100, valid solutions are found within 600 seconds.
Heurssieusssstiss Random and Shortest-Job-Fire (SJF) methods are greedy heuristics. They cre- valid schedules in one-shot manner using the Gant--chart-ommllttoon strategy, similarly to MatNet based model. SJF assigns the shortest jobs (at most 4) in ascending order that are available for each stage each time step The runtimes for Random and SJF are slower than that MatNet in Table 5.2 because MatNet solves batch of problems in parallel using GPUs.
Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) two metaheuristics widely used by the OR community to tackle the FFSP. Metaheuristics are systematic procedures to create heuristics, most useful for optimization problems that are too complex to MIP approaches to engineer problem-specine handcrafted algorithms. Our implementation GA and PSO are based on the works found in the OR literature 34 35
MatNet. Solutions produced by the learned heuristic of our MatNet based model significantly outperform those the conventional OR approaches, both in terms of the qualities and the runtimes. Some commercial applications of the FFSP require solving just one instance as best one can within relatively generous time budget. Hence, we have also tested the performance algorithms under ample time to improve their solutions on single instances. The results are provided in Appendix Even this case, however, the conventional OR algorithms do not produce better solutions than those of our MatNet method.
baseline

---

Conclusion and Discussion
In this paper, we have introduced MatNet, neural net capable of encoding matrix-style relationship data found in many CO problems. Using MatNet as front-end model, we have solved two classical optimization problems of different nature, the ATSP and the FFSP, for the first time using deep learning approach.
A neural heuristic solver that clearly outperforms conventional OR methods has been rare, espe- cially for classical optimization problems. Perhaps, this is because the range of CO problems ML researchers attempt solve has been narrow, only around simple problems for which good heuristics and powerful MIP models already exist (such as the TSP and other related routing prob- lems). The FFSP is not one of them, and we have shown that our MatNett-based FFSP solver signif- icantly outperforms other algorithms. Our results are promising, hinting the prospect of real-world deployments of neural CO solvers in the near future. More research is needed, however, to fully reflect combinations of many different types of constraints posed by real-world problems.
For experiments, have chosen to purely data-driven and does not require any engineering efforts by a domain expert. We would like emphasize, however, that the use of MatNet restricted end-to-end methods only. Hybrid models (MI, OR algorithms) based on the MatNet encoder should be possible, and they will have better performance and broader applicability.
end-to-end RL approach for its simplicity. It is
We have implemented our MaiNet model in PyTorch. The training and testing code for the experi- ments described in the paper is publicly available."
10

---

Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for their valuable comments that helped improve the paper. We thank Kevin Tiernyy for reviewing the MIP methods used in our experiments and giving us helpful tips and comments. We declare no third party funding or support.
References
[1] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' horizon. European Journal of Operational Research, 2020.
[2] Markus Kruber, Marco E. Lübhecke, and Axel Parmentier. I Learning when use decomposition. Interna- tional Conference Al and OR Techniques in Constraint Progranming for Combinatorial Optimization Problems, pages 202-210, 2017.
[3] Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning classification of mixed mixed-integer quadratic programming prohlems. International Conference the Integration of Constraint Programmiing, Artifi- cial Intelligence, and Operations Research, pages 595-604, 2018.
[4] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems 32, 2019.
[5] André Hottung and Kevin Tiemey. Neural large neighborhood search for the capacitated vehicle routing problem. European Conference Artificial Intelligence, pages 443 450, 2020.
[6] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning- hased iterative method for solving vehicle routing problems. International Conference on Learning Representations, 2020.
[7] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems 30, 2017.
[8] Ycong-Dac -Da Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjunc Gwon, and Scungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processngg Systems 33, 2020.
Oriol Vinyals, Meire Fortunato, and Navdeop Jaitly. Pointer networks. Advances Neural Information Processing Systems 28, 2015.
[10] Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence sequence learning with neural networks. Advances in Neural Information Processing Systems 27, 2014.
[11] Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. ICLR (Workshop). 2017.
[12] MohammadReza Nazari, Afshin Oraojlooy, Lawrence Snyder, and Martin Takac. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems 31, 2018.
[13] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Proceedings. 2005 IEEE International Joint Conference on Neural Nenworks, 2005., 2, 2005.
[14] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner. and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks. 20tt:rnnss.((11661111 20(1):61-00 2008
[15] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in Neural Information Processing Systems 31, 2018.
[16] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2016.
[17] Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems 33, 2020.
[18] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs. Advances in Neural Information Processing Systems 33, 2020.
[19] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems 30, 2017.
11

---

[20] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova. Adriana Romero, Pietro Lio. and Yoshua Bengio. Graph attention networks. International Conference Learning Representations, 2018.
[21] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! International Conference on Learning Representations, 2019.
[22] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systemy 32, 2019.
[23] Daniel Gibbons, Cheng- Cheng-Chew Lim, and Peng Shi. Deep learning for bipartite assignment problems. 2019 IEEE International Conference Systems, Man and Cybernetics (SMC), pages 2318 22252,2252222 2019.
[24] Paul Duetting, Zhe Feng, Harikrishma Narasimhan, David C. Parkes, and Sai Srivatsa Ravindranath. Op-
timal auctions through deep learning, International Conference on Machine Learning, pages 1706-1715, 2019.
[25] Quinlan Sykora, Mengye Ren, and Raquel Urtasun. auentt routing value iteration network. Interna- tional Conference Machine Learning, pages 9300 93000-993,,,-0 2020.
[26] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning Graphs: Methods and Applications, 2021.
[27] Jill Cirasella, David S Johnson, Lyle A McGeoch, and Weixiong Zhang. The asymmetric traveling sales- man problem: Algorithms, instance generators, and tests. Workshop on Algorithm Engineering and Ex- perimentation, pages 32-59, 2001.
[28] Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229-266, 1992.
[29] Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
[30] Clair Miller, Albert Tucker, and Richard A Zemlin. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4):326-32,, 1960.
[31] IBM ILOG CPLEX Optimization Studio. V20.1: User's Manual for CPLEX. IBM Corp, 2020.
[32] Keld Helsgaun. An Extension of the Lin Kermighan-Helgganee TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report. Roskilde Universitet, December 2017.
[33] Ebrahim Asadi-Gangra Lagrangian relaxation approach to minimize makespan for hybrid flow shop scheduling problem with unrelated parallel machines. Scientia Iranica, 25(6):3765-3775, 2018
[34] Cengiz Kahraman, Orhan Engin, Ihsan Kaya, and Mustafa Kerim Yilmaz. An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. International Journal of Computa- tional Intelligence Systems, 1(2):134-14 147, 2008
[35] Manas Ranjan Singh and SS Mahapatra. A swarm optimization approach for flexible flow shop scheduling with multipracessor tasks. The International Journal of Advanced Manufacturing Technology, 62(1- 4):267-277, 2012.
[36] David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: computational study. Princeton university press, 2006.
[37] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. INFORMS Annual Meeting 2019, Session Boosting Combinatorial Optimization using Machine Learning.
[38] Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. ACML, pages 480. 2020.
[39] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Leamingg improvement heuristies for solving routing problems.. IEEE Transactions on Neural Networks, 2021.
[40] Tian-Soon Lee and Ying- Tai Loong. A review of scheduling problem and resolution methods in flexible flow shop. International Journal of Industrial Engineering Computations, 10(1):67-88, 2019.
[41] André Hottung, Yeong Dae Kwon, and Kevin Tiemey. Efficient active search for combinatorial optimiza- tion problems. International Conference on Learning Representations, 2022.
fee
12


Reviews:
[{"review_id": "mbstG_IcWli", "reviewer": "Reviewer_i9Xj", "summary": "This work proposes a novel matrix encoding network (MatNet) to solve combinatorial optimization (CO) problems with matrix-style relationship data. This kind of CO problems, such as asymmetric TSP, can be found in many real-world applications, but cannot be solved by the current neural combinatorial optimization approaches. The key contribution is the proposed dual graph attentional layer, along with the multi-head mixed score attention, to efficiently incorporate the matrix data into the well-known Attention Model (AM) architecture for solving CO problems.  ", "questions": "", "limitations": "", "rating": 7, "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": "I generally find the idea and the proposed model novel and interesting. But the lack of some important discussions on the proposed method makes me hard to give a clear acceptance for the current manuscript. I am willing to adjust my score based on the author's response.  \n\nStrengths:\n\n+ This paper is generally well-written and easy to follow.\n\n+ This work is the first neural combinatorial optimization approach to solve CO problems with matrix-style relation data, which is important for many real-world applications.\n\n+ The proposed dual graph attention layer is a novel and reasonable generalization of AM model to incorporate matrix-style relation data. The design of simple initial node embedding + matrix data enhanced attention structure is novel and inspiring. The instance augmentation strategy is also an efficient way to generate diverse solutions (and to find the best one).\n\n+ It is glad to see the proposed method can successfully solve general asymmetric TSP and flexible flow shop problems with promising results and fast runtimes.\n\nMajor Concerns:\n\n- C1. Contribution and Better Position: The proposed dual graph attention layer and mixed score attention are novel to deal with CO problems with matrix data. However, it is not sure whether similar structures (e.g., with extra data) have been proposed in GAT/GNN/Transformer for other applications. The current related work section is mostly on neural combinatorial optimization (NCO), but a better position with other similar GAT/GNN architectures is needed to judge the novelty of the proposed architecture. Even if similar structures have been proposed, it will not hurt this work's contribution on solving CO problems with matrix data. Indeed, providing related work on similar GAT/GNN structures would be valuable for potential follow-up and improvement. \n\n- C2. Generalization to New Problems: The generalization ability is a key feature for a learning-based solver to be used in real-world applications. Some current work finds the NCO approach is not good at generalization to problems with different distributions, which is a crucial limitation [1,2]. It seems that the proposed model makes itself harder to generalize to problems with different sizes (e.g., train on 100-city ATSP, generalization to 500-city ATSP) due to the at most $N_{max}$ one-hot initial node representation, which has been briefly discussed in the paper. Is it possible to use random 0/1 representation (total $2^N$ possibility) or even truly random representation for initial node representation to avoid this limitation? Is the one-hot vector crucial for the proposed methods? \n\n- C3. Comparison to Other Learning-based methods: This work mainly compares the proposed method with different MIP and heuristics methods, but not other learning-based methods. It is understandable since it is the first method to deal with CO problems with matrix data. However, to better analyze the proposed model, it is still valuable to compare it with other NCO methods on problems that can be solved by both methods. For example, it is possible to use this method to solve euclidean TSP with matrix data, and compare the results obtained by POMO-based AM with classical euclidean input. Will this method perform poorer due to the lack of strong explicit prior knowledge of the euclidean coding?   \n\n- C4. Runtime: For the TSP results, MatNet takes 2s/8s/34s to solve 10,000 ATSPs with 20/50/100 cities, and POMO only needs <1s/2s/11s to solve 10,000 TSPs as reported in [3]. This resuts is reasonbale since MatNet has a larger encoder to incoporate the matrix data. However, why does the LKH3 solver only need 1s/11s/1m for 10,000 ATSPs but 42s/6m/25m for 10,000 TSPs?\n\nOther Issues:\n\n- I1. What does the front-end model mean in the context of NCO?\n\n- I2. In the TSP decoder, why not also use the graph embedding (e.g., average node embedding) to make the QUERY token as in AM? \n\n- I3. For ATSP, why the tmat class is more interesting than the general ATSP problem? \n\n- I4. The provided Github repository is empty. I think it is unsuitable to say the code is provided in the checklist. \n\n[1] Joshi, Chaitanya K., Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning TSP requires rethinking generalization. arXiv preprint arXiv:2006.07054 (2020).\n\n[2] Michal Lisicki, Arash Afkanpour, and Graham W. Taylor. Evaluating Curriculum Learning Strategies in Neural Combinatorial Optimization. arXiv preprint arXiv:2011.06188 (2020).\n\n[3] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems 33, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "_k1vQXjq3Tq", "reviewer": "Reviewer_cRFQ", "summary": "Several combinatorial optimization problems can be fully specified by one or more matrices specifying the relationships between two groups of parameters. For example, such a matrix can encode inter-city distances in the traveling salesman problem. In the hybrid flow shop problem, a set of matrices D_i encode the time it takes to perform a job on a given machine at each timestep i. the This paper proposes to learn to embed such matrices using a neural network derived from the transformer architecture and use such embedding to find good approximate solutions to the corresponding combinatorial problems. ", "questions": "", "limitations": "", "rating": 5, "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": "The paper makes 3 contributions:\n * It introduces what it calls a matrix encoding network (MatNet). It details how to modify the transformer architecture to turn it into a supercharged graph attention network. This is the most significant contribution of this paper.\n * It demonstrates step by step how to build the matrices for two important combinatorial problems, the asymmetric traveling salesman problem (ATSP) and the flexible flow shop problem (FFSP). The paper states precisely what hyper parameters were used for the magnet model, and how to derive a solution from the MatNet embedding. Providing such a detailed description of the process ensures that the results of this paper will be easily replicable.\n * It evaluates the effectiveness of the approach on the ATSP and the FFSP problems by comparing the results against a commercial grade MILP solver (CPLEX) as well as 4 heuristics based solvers.\n\nThe paper is clearly written and well organized. This makes it easy to follow. It also provides an extensive list of related work to help put the work in perspective.\n\nThe paper states that the ATSP the FFSP problems were previously not amenable to DNN based optimization. While it is possible, using previous work such as Kool et al mentioned in the paper, to encode a M by N matrix by simply embedding N features for each of the M nodes, this encoding wouldn't be flexible since the number of features would depend on one of the dimensions of the problem. As a result, a new policy would need to be trained for each value of N that is being considered. In contrast, this paper realizes that a M by M matrix can be interpreted as a bipartite graph and that a single bipartite graph neural network can, in theory, be trained to handle all matrix sizes. However, the paper appears to train distinct neural networks for each problem size, so it fails to demonstrate the flexibility of the MatNet embedding.\n\nThe paper explains how to adapt a transformer based neural architecture to apply it to a bipartite graph, and provides a rationale for the modifications, in particular the need for 2 update functions. However it doesn't validate these design choices, for example with an ablation study. Furthermore, it doesn't compare the effectiveness of its MatNet architecture against other bipartite graph embeddings. The work of gasse et al (Exact Combinatorial Optimization with Graph Convolutional Neural Networks) would be a good candidate here, but other bipartite graph embeddings solutions have been published and could be used as well. \n\nFurthermore, RL driven MILP solvers are readily available (see for example http://ecole.ai) for academic work and could have been used in addition to CPLEX and the heuristic based approaches to build more relevant baselines for evaluation. \n\nI believe that the MatNet approach has potential, but it is currently insufficiently evaluated.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors appear to have been candid about the limitation of their approach.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Nelya06G6Q6", "reviewer": "Reviewer_tewG", "summary": "The authors propose a family of matrix encoding networks to encode the states of combinatorial optimization problems which can be encoded as a matrix. The proposed matrix encoding network works like a bi-partite graph embedding network. Compared to previous efforts encoding sequences and graphs, the effort of this paper is appealing. Two CO problems are studied: ATSP and FFSP, and the performance on ATSP is inferior to competing methods, and the performance on FFSP is more convincing. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 strengths of this paper are:\n1. Designing encoding networks for matrices in neural CO is interesting and appealing, deferring from previous efforts in modeling sequence and graph data. \n1. The designed attention-based network is similar to the Transformer architecture, and the unsymmetric message-passing design based on the bi-partite graph is reasonable.\n1. Experiment results on FFSP are convincing. \n1. The authors discuss the potential of applying the proposed method to hybrid ML-OR approaches.\n\nThe limitations of this paper are:\n1. My major concern is that the experiment results in this paper may not ground this paper as a general framework for a wide range of CO problems that can be modeled by matrices. Because the authors only experiment on two CO problems (ATSP and FFSP), and only the FFSP results are convincing. If this paper is focused on FFSP, I think it is a good submission; however, since the authors are aiming at a wider range of problems, the experiment results are not that convincing. In comparison, most existing papers which focused on developing a general approach (e.g. S2V-DQN in NeurIPS17, NeuRewritter in NeurIPS19) study 3 different CO problems and report convincing results on all problems.\n1. Since MatNet uses zero-vectors to embed nodes in A, and one-hot vectors for nodes in B, can we design a MatNet for symmetric cases (e.g. symmetric non-Euclidean TSP)?\n\nSome minor remarks:\n1. As a read from \"Instance augmentation via different sets of embeddings\", do you break the permutation invariance nature of MatNet? \n1. In Table 2, Random and Shortest Job First are slower than MatNet. However, from my understanding, Shortest Job First is a greedy algorithm and should be at least as fast as MatNet (which performs greedy roll-out), because Shortest Job First does not require the forward pass of neural networks. Random should also be a fast algorithm for the same reason. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation part is clearly written and well discussed. I agree with the authors:\n\n“A neural heuristic solver that clearly outperforms conventional OR methods has been rare, especially for classical optimization problems. Perhaps, this is because the range of CO problems ML researchers try to tackle has been too narrow, only around simple problems (such as the ATSP) for which good heuristics and powerful MIP models already exist.”\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5RSm8ycOi7M", "reviewer": "Reviewer_2Zed", "summary": "The paper introduces a neural net model that takes relationship matrices as input for solving combinatorial optimization problems. The proposed network can be considered as a special GNN fed by a complete bipartite graph with weighted edges. The experiment results show that their end-to-end RL framework can achieve a similar performance as LKH3 for asymmetric traveling salesman problems and significantly outperform conventional OR methods for flexible flow shop problems.", "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": "Originality: The proposed model can be seen as a special GNN with a complete bipartite graph with weighted edges as input. The structure is inspired by [1] with several improvements. \n\n1) There are two independent update functions for nodes in two disjoint sets.\n2) The attention score considers the edge weight as well.\n\nQuality: The paper is complete with sufficient details about the model structure. \n\nClarity: The paper is clearly written and easy to follow.\n\nSignificance: The proposed framework takes the matrix-style relationship as input, which is novel and can handle a large class of combinatorial optimization problems. The experiment results show that the proposed algorithm significantly outperforms conventional OR methods for flexible flow shop problems which are also very impressive. \n\n\n[1] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! International Conference on Learning Representations, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some comments:\n\n1) For the experiment part, I would expect authors to provide more diagrams/charts to enable a more intuitive understanding of the proposed model.\n\n2) It can be useful to employ sensitivity analysis to demonstrate the stability and scalability of the proposed framework. \n\n3) I am looking forward to seeing the performance of this framework with other different combinatorial optimization in your future work.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a general approach to solving approximately with GNNs a large class of matrix-based combinatorial optimization problems. After the discussion, the paper is
* an interesting contribution for combinatorial optimization problem solving from the machine learning perspective.
* will be helpful for other problems not covered in the paper.
* the paper is nice too read.

However, there are shortcomings of the paper:
* The proposed method does not outperform existing methods (on ATSP). We agree however that outperforming highly optimized codes like LKH is not necessarily expected.

Due to the novelty of the architecture and the tackled setting and the relevant results the paper is a good fit for NeurIPS.

We urge the authors to reflect the discussion and the additional experiments in the final paper and include the promised changes in their final paper.
Decision: Accept (Poster)