AIA: learn to design greedy algorithm for NP-complete problems using neural networks
Authors: Zhenxin Ding
Jingyan Sui
Ruizhi Liu
Shizhe Ding
Liming Xu
Zihao Huang
Chao Wang
Haicang Zhang
Shiwei Sun
Chungong Yu
Dongbo Bu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Algorithm design is an art that heavily requires intuition and expertise of the human designers as well as insights into the problems under consideration. In particular, the design of greedy-selection rules, the core of greedy algorithms, is usually a great challenge to designer: it is relatively easy to understand a greedy algorithm while it is always difficult to find out an effective greedy-selection rule. In the study, we present an approach, called AIA, to learn algorithm design with the aid of neural networks. We consider the minimum weighted set cover (SC) problem, one of the NP-hard problems, as an representative example. Initially, we formulate a given weighted SC problem as an 0-1 integer linear program (ILP): each variable $x_i$ has two options, i.e., $x_i=0$, which denotes abandon of the set $s_i$, and $x_i = 1$, which denotes selection of  $s_i$. Each option of a variable leads to a sub-problem with respect to the original ILP problem. Next, we design a generic search framework to find the optimal solution to the ILP problem. At each search step, the value of a variable is determined with the aid of neural networks. The key of our neural network is the loss function: the original ILP problem and the  sub-problems generated by assigning a variable $x_i$ should satisfy the Bellman-Ford equation, and the dissatisfication of the Bellman-Ford equation is evaluated and used as loss function of our neural network. The trained neural network is used as greedy-selection rule. Experimental results on representative instances suggest that using the NN-based greedy selection rule, we can successfully find the optimal solutions. More importantly, the NN-based greedy-selection rule outperform the outstanding Chavatal greedy algorithm, which was designed by human expert. The basic idea of our approach can be readily extended without significant modification to design greedy algorithm for  other NP-hard problems.  

Under review as a conference paper at ICLR 2023
AIA: LEARN TO DESIGN GREEDY ALGORITHM FOR -P-COMPLETE PROBLEMS USING NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Algorithm design is an art that heavily requires intuition and expertise of the hu- man designers as well as insights into the problems under consideration. In partic- ular, the design of greedy-selection rules, the core of greedy algorithms, is usually a great challenge to designer:
relatively easy to understand greedy algo- rithm while it is always difficult to find out effective greedy-selection rule. In the study, we present an approach, called AIA, to learn algorithm design with the aid of neural networks. We consider the minimum weighted set cover problem (WSCP), one of the NP-hard problems, as an representative example. Initially, we formulate given WSCP an 0-1 integer linear program (ILP): each variable 2; has two options, i.e., = 0, which denotes abandon of the set 8i, and x; = 1, which denotes selection of 8i. Each option of a variable leads to sub-problem with respect to the original ILP problem. Next, we design generic search frame- work find the optimal solution to the ILP problem. At each search step, the value of variable is determined with the aid of neural networks. The key of our neural network the loss funetion: the original ILP problem and the sub-problems gen- erated by assigning variable x; should satisfy the Bellman-Ford equation, which enables us to set the dissatisfication of Bellman-Ford equation as loss function our neural network. The neural network is used as greedy-selection rule. Experi- mental results on representative instances suggest that using the NN- IN-based greedy selection rule, we successfully find the optimal solutions. More importantly, the NN-based greedy-selection rule outperform the outstanding Chavatal greedy algorithm, which designed by human expert. The basic idea of our approach can be readily extended without significant modification to design greedy algo- rithm for other NP-hard problems.
INTRODUCTION
NP-complete problems, the hardest ones in the NP class, can be validated in polynomial time, but no polynomial-time algorithm has yet been found to solve these problems. A great variety of prac- tical problems can be formulated NP-complete problems, such strategic planning, production planning, facility location problems, as well as a variety of scheduling and routing problems. Thus, despite the hardness of these problems, designing efficient solving algorithms for NP-complete prob- lems is highly desired.
The weighted set cover problem (WSCP) is classical NP-complete problem, which aims to find subset of columns that cover all the rows of 0-1 matrix at minimal cost (Karp) 1972). The algorithms solve WSCP, say branch-and-boun with limited size. Therefore, considerable efforts have been devoted to design heuristics and meta- heuristies that can find optimal or near optimal solutions to large-scale WSCP problems within reasonable time. The latest works meta-heeristir approaches for the WSCP include genetic algorithms, ant colony optimization, simulated annealing, tabu Search.
and branch-and-cut, can only handle instances
With the breakthrough of deep learning (DL) in solving practical problems, many researchers try to use DL to solve combinatorial optimization problems. Training a neural network end-to-end with supervised learning to solve theoretically complex combinatorial optimization problems is diffi- cult problem. On the one hand, traditional algorithms and mathematical methods have a relatively complex theoretical foundation while the neural network black box lacks theoretical foundation.

---

Under review as a conference paper at ICLR 2023
On the other hand, many practical problems have their specific data characteristies while DL models usually require large amount labeled data under the distribution and constructing labeled data needs to know the optimal solution of the original problem, so it is very difficult to build a large-scale dataset like ImageNet Russakkvkyy et al. 2015).
not directly solving this problem end-to-end like other fields. In the study, present an approach, called AIA, to learn algorithm design with the aid of neural networks. The specific goal of this paper is to use machine learning find greedy rules for solving WSCP and then design an efficient and practical algorithm for WSCP.
Thus,
Our main contributions of this work
follows:
1. We propose idea to solve the problem, where the neural network learns greedy strategies to assist researchers in designing algorithms instead of using deep learning to solve the problem end-to-end.
2. We propose the NNVal algorithm, which uses simple neural network to score recursive sub-problems that are used to guide a multi-step decision-making process, and a special novel loss function is designed to train the neural network.
3. We propose the NNGreedy algorithm for WSCP. The experimental results on multiple datasets show that compared with greedy algorithms designed based on human experience, such as the Chvatal algorithm, the NNGreedy algorithm can obtain better solution.
2 RELATED WORKS AND BACKGROUND
There exist two traditional approaches to solve combinatorial optimization problems: exact algo- rithms and approximate/heurrstic algorithms. Exact algorithms are guaranteed to find optimal so- lutions, but they become intractable when the problem scales up. Approximate algorithms trade optimality for computational efficiency. They are problem-specific, often designed by iteratively applying simple man-crafted rule, known as heuristic. Their complexity is polynomial and their quality depends on an approximate ratio that characterizes the worstlaverage-case error w.r.t the optimal solution.
For NP-complete or even NP-hard constraint programming problems, the exact algorithm usually adopts the divide-and-conquee approach, dividing the solution process into multiple parts, and grad- ually eliminate poor choices until the optimal solution found. These methods are essentially exhaustive search and their time complexity exponential.
The cores of the divide-and woidd--addcooquur strategy is how to decompose it into sub-problems and which sub- problem to choose to solve first. Taking the Traveling Salesman Problem (TSP) example, the solution software Concorde (Appleegte et al.) (002) adopts the maach-and-boume combined with cut plane method. For more general mixed integer linear programming problems, the mainstream solvers, for example, Gurobi 2007). CPLEX 2009). EPRESS(Laund) et al., 2009)) SCIP(Gamrath al. (2016), etc., also branch and bound combined with cutting plane and column generation technology.
When searching for the optimal solution, heuristic rules play an important role. Taking mixed inte- ger programming as an example, in the branch-and-bount process, selecting an appropriate branch re-selected also requires heuris-
variable requires heuristic rules, and each time a sub-probles tic rules. Choosing appropriate branching variables and subproblems can significantly reduce the search space. addition, to obtain a good feasible solution as soon as possible speed up pruning, the algorithm performs a simple and fast primitive heuristic strategy on each subproblem. A good original heuristic can find better feasible solutions faster.
Heuristic rules depend the specific problem and solution process. In other words, different heuris- tic rules and different parameters have different effects on different data and at different stages of solution. Therefore, data-driven machine learning technique is potential heuristic rule design method.
In the last decade. DL has significantly improved Computer Vision, Natural Language Processing and Speech Recognition by replacing hand-crafted features with features learned from datagLeCun et al. 2015). On the one hand, combinatorial optimization algorithms often used com-
2

---

Under review as a conference paper at ICLR 2023
plement to deep learning solutions. DETR (arion et al. 2020) uses a bipartite graph matching algorithm to replace the NMS post-processing in traditional object detection, which solves a pain point in this field. DeepSORT current frame is the same as the one in previous frame, which is one of the most popular and general object tracking algorithms.
et al. (017) uses the Hungarian algorithm to tell if an object in
On the other hand, more and more researchers have introduced neural network into Combinatorial Optimization, called Neural Combinatorial AndimizationGaammenn et al., (022), which attempts to learn good heuristics for solving a set of problems using Neural Network models. The use of machine learning techniques in No-complete problem solving can be divided into two categories: one is learning from expert knowledge, that is, supervised learning, and the other is learning from experience, that is, reinforcement learning, which is briefly described as follows:
Supervised learning is relatively common and easy to implement. In the branch and bound frame- work of Mixed Integer Programming Solver, there are more than 10 heuristic rules for the selection of branch variables. The Strong Branch strategy is recognized as the branch variable selection strat- egy that minimizes the size of the branch search tree (Achterberg et al., 2005). selects the variable branch that minimizes the lower bound of the new sub-problem after the branch every time. The cost is that for each branch, the lower bound of the new subproblem must be calculated. This step introduces lot of calculations, and absolutely most calculations cannot be reused in subsequent solutions. This makes the strong branching strategy lag behind in solving time compared to other rules. In order to overcome the shortcoming of the strong branch strategy, Marcos let al. 2014) used a special kind of decision tree to learn the branch variable selection strategy of Strong Branch. Khalil(Khalil et al., 2016) proposes an instance-specific learning framework. For each problem, the choice of strong branching strategy is recorded on several sub-problems at the be- ginning, and the features of each variable and each step are extracted at the same time. They train an SVMrank and use the learned model on the following sub-problems. Gasse uses a Graph Convolu- tional Neural Network(Gaass et al. 2019) to extract deeper information on variables and constraints before each branch to learn the choice of strong branching strategies. He(He et al. (2014) designed a machine learning algorithm,in which among all open subproblems, the subproblem whose sub- tree contains the optimal solution will be selected. Chaitanya's 's work[Joshi al. 2019) uses deep graph network by supervision to predict the probabilities of an edge to be in the TSP tour, which more sample efficient compared to reinforcement learning, whose feasible tour is generated by beam search.
Reinforcement learning techniques mostly used in solving algorithms for specific NP-hard problems. Taking the TSP problem as an example, Vinyals( Vinyals et al.) 2015) proposed a pointer network, and introduced a pointer in the decoder RNN, which solves the problem of variable size output dictionaries using the mechanism of neural attention. This model solves the problem that the output scale strictly depends on the input scale during training. Bello(Bello et al. 2016) uses a similar model structure, sets the current total distance as reward, and uses reinforcement learn- ing to train the network, which solves parts of problems that supervised learning is difficult to deal with, such as non-unique standard answers. Kool and Welling et al., 2018) replaced the Re- current Neural Network (RNN) with a Graph Neural Network (GNN) to process the input. All three above use reinforcement learning to train end-to-end models. Astounding results from Trans- former Vaswani et al. 2017) models on NLP and CV tasks(Khan et al., 2021) have intrigued the researcher to study their application to TSP. Xavier and Thomas(Bresson & Laurent 2021) propose to adapt the Transformer architecture to the combinatorial TSP. Training is done by reinforcement learning, hence without TSP training solutions, and decoding uses beam search. As for the learning of specific heuristic rules, Khalil uses the graph neural network (Khalil et al. (011)) to encode graph information to make choices.
Vinyals(Vinyals
In general, reinforcement learning methods are more widely used in solving combinatorial optimiza- tion problems, which don't require too much prior knowledge, while supervised learning methods are more efficient in sampling and training. All in all, the use of machine learning to assist the solu- tion of combinatorial optimization problems very promising research trend. The main question is whether DL can learn better heuristics from data, i.e. replacing numan-designe heuristics.
3

---

Under review as a conference paper at ICLR 2023
3 STATE-TRANSITION EQUATION
The WSCP is the problem of covering the rows an m-row, n-column, 0-1 matrix with subset of the columns minimum cost. Problem Iis matrix form of WSCP
min
== c²
Ax 2 b 2j
s.t.
(j= 1,2....
We define a state 8s. = [A,b, c; (k: 0, 0.1...,n k=O represents the original programming problem and &: >0 means that the variables 31, Fi,,...... problem as a multistep recision-making process, determining whether a variable Iy is 0 or I at each to be A', which has rows and
-... 2y have already been fixed. We define the
step. If 2 1= the first step, with rows and columns 1 columns and b turns to be b an(a is the j-th column of A). We redefine the problem as follows,
min c.a.
Ax 2 b
s.t.
21, I2, 23 are fixed
Ik+1, Th+2: Fn = or
We define f(s)) as the optimal solution of the subprogram 2 under the state sy. Therefore state- transition equation can be obtained.
f(sk+1)
= min #4+1
f(s)), k = O,.., n
(3)
4
METHOD
We use a neural network to score each sub-problem and guide multi-step decision- according
equation 3 instead of predicting the solution the sub-problem. We call this algorithm NNVal
4.1 PROBLEM REFORMULATION
Supposing the optimal solution of the sub-problem 2 is J(A,b, c), jwe have the following state- transition equation state Sk.
f(A',b', c') min (f (A", Ck+1 + f f(A" 0c+1, c"))
A'
A' (x(xnk)
(a0+1, ak42, an)
A"
A mx
(Ou+22, ak. an)
b' b'm
b (xj01 + + x(ax)
c'
cr-k
(G441; Cn)
c" -
= C633 Cn)
where, zf is the variable determined at state 8k-1 and as represents the k-th column of We define f bA, too when Ax 2 b has feasible solution.
Thus, given the function f. it is easy to get:
0 1
f(A" b' c²) Ck+1 f(A" AA".8 ak+1, d") f(A", b', c") Ck+1 + f(A" cx)
T
(5)
Appendix B provide the training process including flowchat and pscudocode

---

Under review as a conference paper at ICLR 2023
4.2 NNVAL ALGORITHM
A simple idea is to fit f with neural network, but it may not be feasible. On the one hand, it is due the difficulty of obtaining labeled data, and on the other hand, due to the characteristics of the neural network itself, the input changes little, but the output may change greatly, so it is difficult to accurately predict the target. We decide make full use of the state-transition equation. Our model go does not directly learn the optimized values of the sub-problems, but learns the recursive relationship between the original problem and the sub-problems.
For preserving all information of the problem and simplifying the training procedure, use simple two-layer fully-connected neural network to learn the recursive relationship. The model go input is the same the input of f. whose input layer has X n + m nodes, corresponding to A. b and с of the original Problem [ As for sub-problem input, og and Cg corresponding to fixed variables Fy
to O. The output layer of the network has node. hidden layer is in the middle, which has m + n nodes. The whole model shown in Figure
Ga
42
dg
b
reshope
linerr
lineor
objyal
di
hiddon layer
Figure 1: Neural Network for NNVal
4.3 LOSS FUNCTION
We define the state transition loss function for one-step decision decision-making making just as follows,
C(P:0) = Liquure Trauz
(6)
In dynamic programming, the recurrence relation is as follow,
Objval(P) min (Obiaal)l)(SS)) Objyal(SPPi)
where P is the original problem and SP is sub-problem P. We hope our model can also learn the recursive relationship, define Lequare follows.
Lequare = (ge (P) min
(8)
We want the output of the original problem to be as close as possible to the output the correct sub- problem. However, this is not enough, because sometimes there are situations where sub-problems are not feasible. Thus, we add the auxiliary item Lauz as follow,
Trauz ReLU (go (feasible SP) go (infeasible SP))
5

---

Under review as a conference paper at ICLR 2023
where ReLU(xx) max(2; 0). We know Lauz is equal 0 when the model output of feasible sub- problem is less than the infeasible, and infeasible sub-problem is selected, this item will generate positive penalty. All in all, suqure is mainly used to make model learn the recursive relationship, and Lauz is used to control the case where the sub-problem is not feasible
4.4 IMPROVEMENT
The algorithm discussed before relies external library functions to judge the feasibility of the sub- problem, so it is suitable for any ILP. This section attempts to mine the nature of the weighted set coverage problem itself, which is more controllable and flexible. In order to facilitate the distinction, we call the algorithm discussed before as NNVal VI, and the algorithm to be discussed next is called NNVal V2.
In NNVal V2, we still use a two-layer fully fully-connected neural network just as V1. The difference of model from VI is that a ReLU layer is added. The structure of the neural network is shown in Figure 2 where Re)U(bb..
4
b
coolupe
objbal
dn
dus
Jukkon layer
Rel
Figure 2: Neural network for improved version of NNVal
Let's rethink the sub-problem corresponding to state 8s [A, b, c; k).
min Ck+1#++1 + ... + In + (qpz +... + cxaz))
0141
Hn b (a12) + ax²%))
(10)
2k+1, Tb-1, H. = or
where the constant term on the right side of the constraint inequality takes a integer value not ex- ceeding In fact, for such 0-1 ILP, the value of b (a1z} +..+ being 0 or less than has
no effect on the solution, so we can use ReLU to reduce the complexity of training. The i-th row of the inequality constraint be written as,
dib+11k411 + as,n bj,t+1
(11)
where bi Zn {x x S 1) is the i-th element of (a1æf + ... agat), oi (0, is the i-th row element of and I; E 1).
In fact, 3k+1, ...; Fn, be arbitrarily 0 if bi,441 S 0. However if b 1, then the row constraint is possible to have further restrictions on Ik+1. In being 0 or 1. In particular, if 0:11-1 a,,+1. ain. O. then the line constraint
bi,+11 0r 1 and ag,k+1 becomes 2 and we get .1 = 1.
Mooe interpretion is shown in appendix

---

Under review as a conference paper at ICLR 2023
Thus, before the state transition, check whether 21+1 need to be fixed to 1. If so directly specify Ik+1 = -1, otherwise make state transition according to the result the model go.
4.5 NNGREEDY ALGORITHM
Based on NNVal algorithm, we design greedy rule and greedy algorithm NNGreedy. The NNGreedy algorithm makes decisions step by step from 21 Zn. and finally obtains complete solution. Without loss of generality, we record P& as the original problem of the k-th step. SPoo corresponds the sub-problem when Fy 0 and SPa1 corresponds the sub-problem when 23. greedy rule adopted by the NNGreedy algorithm is as follows,
The
Algorithm NNGrreddy algorithm greedy rule
if go(SP))) < go(SPk)) then
2:
Ik
3: else
4: 32
5: end if
In specific WSCP, for S; E F, Vi E (1.2...,,n). x; = 0 means not choosing S; and æ; = means
St is selected. The pseudo-code of the NNGreedy algorithm can be expressed follows,
Algorithm NNGreedy greedy algorithm
1: for = 1 + do
2: Calculated z; according to the NNGreedy greedy rule
3: end for
4: Output 11, 22; In and Ex=1 w.F
EXPERIMENTS
5.1 NNVAL EXPERIMENTS
This article uses PyTorch1.6. The CPU is Intel Core i7-8700K, and the GPU is an NVIDIA GeForce GTX 1080Ti. We randomly generate some weighted set coverage problems as dataset according to the method of Balas & Ho 1980). We use the two scale follow,
Small-scale ILP instance, full set |U| 20, 20 subsets S2, S20. constraint matrix density is 0.1, that is, the probability of the number appearing in the constraint matrix.
2. Large-scale ILP instance, full set |8| 50, 50 subsets S2, Sso. constraint matrix density is the same as small-scale instance.
The NNVal algorithm is mainly used to assist decision making at every step, and the sub-problems different stages have different scales. In order prove the effectiveness of the algorithm, conduct experiments on problems of different scales. We choose sub-problem pairs (SPP, SP,) to evaluate.
T shows the estimation of the order between the sub-problems of NNVal pairs on small-scale and big-scale instances, and their estimation accuracy 95.4% and 86.5%.
5.2 NNGREEDY EXPERIMENTS
We compared the NNgreedy algorithm with the Chvatal's greedy algorithm, which designed purely based human experience, in terms of time and solution quality
On 100 small-scale instances, we compare the NNGreedy algorithm and the Chvatal greedy algo- rithm from two perspectives:

---

Under review as a conference paper at ICLR 2023
Table 1: The estimation relationship on sub-problem pairs in 2 scales
SCALE
Obj(5P))<Ohi(SPP))
Ob((SPR))0bj(SPP)
Acc
(o(SP)<g0((P))))
217
139
Big
86.50%
go(SPo)2go(SP)
128
1494
go(SP))g0(SB))
281
Small
95.39%
go(SPo>>g0(PP)
28
982
Table 2: Comparison of solution quality on small scale instances
Chvatal Greedy
NNGreedy
Instance
Optimal Obj
Objective Value
Gap
Objective Value
Gap
120_1 1
416
416
416
0
120.2
621
676
8.86%
621
0
120_3
494
598
21.05%
503
1.82% %
120_4
451
490
10.87%
451
0
120_5
542
542
542
0
120_6
520
553
6.35%
520
120
570
678
18.95%
570
0
120
602
702
16.61%
602
120_9
529
549
3.78%
529
0
120_10
427
427
432
1.17%
1. Comparison of the number of instances to obtain the optimal solution: NNGreedy obtains the optimal solution on 87 instances, and the Chvatal greedy algorithm obtains the optimal solution 11 instances.
2. Comparison of solution Quality: On 87 instances, the solution obtained by NNGreedy is better than the solution obtained by Chvatal greedy, and on 3 instances, the solution obtained by NNGreedy is inferior the Chvatal greedy algorithm.
Table shows the specific solution quality comparison of the two greedy algorithms on 10 small- scale instances. shown in the table the solution quality of NNGreedy algorithm better than that of the Chvatal greedy algorithm.
On 10 large-scale instances, we also compares the NNGreedy algorithm and the Chvatal greedy algorithm from the perspectives of the number of instances to find the optimal solution and the quality the solution:
1. Comparison of the number of instances for obtaining the optimal solution: NNGreedy obtains the optimal solution on one instance, and the Chvatal greedy algorithm does not obtain the optimal solution on any instance.
2. Comparison of solution Quality: On 8 instances, the solution obtained by NNGreedy is better than the solution obtained by the Chvatal greedy algorithm, and on 2 instances, the solution obtained by NNGreedy is inferior the Chvatal greedy algorithm.
Table shows the specific solution quality comparison of the greedy algorithms on 10 large- scale instances. The experimental results show that the solution quality of the NNgreedy algorithm better than that of the Chvatal greedy algorithm.
Although the NNGreedy algorithm slow to solve due to embedding training, it acceptable, and the iteration time of each round is about 0.01s 0.
8

---

Under review as a conference paper at ICLR 2023
Table 3: Comparison of solution quality big scale instances
Chvatal Greedy
NNGreedy
Instance
Optimal Obj
Objective Value
Gap
Objective Value
Gap
150
1559
1742
11.73%
1725
10.65 %
150_2
2206
2452
11.15%
2331
5.67 %
150_3
1221
1899
55.53%
1760
44.14%
150_4
2548
3203
25.71% %
3067
20.37 %
150.5
2315
2417
4.41% %
2408
4.02%
150.6
1965
2294
16.74%
2298
16.95%
150_7
1933
2128
9.83%
2030
5.02%
150.8
1975
2101
6.28%
2013
1.92%
150_9
2105
2439
15.87%
2525
19.95%
150_10
1630
1888
15,83%
1630
0
CONCLUSION AND DISCUSSIONS
Aiming at the WSCP, this paper proposes an optimal sub-problem estimation algorithm NNVal and solving algorithm NNGreeny. Experiments show that the NNVal algorithm and NNGreedy algorithm based on deep learning can obtain better solutions than the Chvatal greedy algorithm based on human experience. The basic idea of our approach can be readily extended without significant modification to design greedy algorithm for other NP-hard problems.
Although NNGreedy is sufficient for neural network training to converge on the corresponding SCP, there is still a certain time gap from commercial solvers. In addition, the hyperparameter setting of iterative algorithm still an issue. For WSCP of the same scale, under the same parameters, the time for the training to converge to the output optimal solution is still not stable.
This paper is an attempt to use deep learning technology to assist algorithm design: the greedy algorithm proposed in this paper does not rely human experience to design greedy rules, but learns greedy rules, which is an intelligent search algorithm and can help to overcome the inadequacy of human experience. We believe that data-driven algorithm design will be new hot topic.
REFERENCES
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):42-54, 2005.
Alejandro Marcos Alvarez, Quentin Louveaux, and I Louis Wehenkel. A supervised machine learning approach variable branching branch-and-bound.
ECMI., 2014.
David Applegate, William Cook, Sanjeeh Dash, and André Rohe. Solution of min-max vehicle routing problem. INFORMS Journal on Computing, 14(2):132-143, 2002.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradi- ent optimization: computational study. In Combinatorial Optimization, pp. 37-60. 1980.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. arXiv preprint 1611.09911 2016.
Bob Bixby. The Gurobi optimizer. Transp. Research Part B, 41(2):155-111 1788 2007.
Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXiv:2103.03012 2021.
Nicolas Carion. Francisco Massa, Gabriel Synnaeve, Nicolas Usumier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European conference on computer vision, pp. 213-229. Springer, 2020.

---

Under review as a conference paper at ICLR 2023
IBM ILOG Cplex. V12. 1: User's Manual for CPLEX. International Business Machines Corpora- tion, 46(53):157, 2009.
Gerald Gamrath, Tobias Fischer, Tristan Gally, Ambros Gleixner, Gregor Hendel, Thorsten Koch, Stephen Maher, Matthias Miltenberger, Benjamin Müller, Mare Pfetsch, et al. The SCIP opti- mization suite 3.2. 2016.
Andoni Garmendia, Josu Ceberio, and Alexander Mendiburu. Neural combinatorial optimization: new player in the field. arXiv preprint (rXXi:2205.01366 2022.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pp. 17580-15592, 2019.
He He, Hal Daume III. and Jason M Eisner. Learning to search in branch and bound algorithms. In Advances in Neural Information Processing Systems, pp. 3293-3301, 2014.
Chaitanya Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: (906:0:900.012222 2019.
Richard M Karp. Reducibility among combinatorial problems. In Complexity of Computer Compu- tations, pp. 85-103. Springer, 1972.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
Elias Boutros Khalil, Piere Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Salman Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. ACM Computing Surveys (CSUR), 2021.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn solve routing problems! arXiv preprint 1rXiv:1803.08477 2018.
Richard Laundy, Michael Perregaard, Gabriel Tavares, Horia Tipi, and Alkis Vazacopoulos. Solv- ing hard mixed-integer programming problems with Xpress-MP: A MIPLIB 2003 case study. INFORMS Journal Computing, 21(2):304-313, 2009. 2009..
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436 444, 2015.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):2112255 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances Neural Informa- tion Processing Systems, 30, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Infor- mation Processing Systems, 28, 2015.
Nicolai Wojke, Alex Bewley, and Dietrich Paulus. Simple online and realtime tracking with a deep association metric. In 2017 IEEE international conference on image processing (ICIP), pp. 3645- 3649. IEEE, 2017.
10

---

Under review as a conference paper at ICLR 2023
A LOSS FUNCTION FOR ILP
The neural network model is denoted as de where is the parameters of the neural network, We first need ge satisly the state-transition equation follows,
go ('', min (go(A", ,,,",,,co "i,,,,c"),, C,t1 + go , -axt1,c") c"))
(12)
We define the following variables:
L.HS = go()))
= -o(A',U,,
RHS1 = (8k: Pk+1 =
= Ck+1 + go (A" , 0x++1c"))
(13)
RHSO = go (Sk: #k+1 = 0)
= [A" b', c")
We want Oo satisfy the state-transition equation 14
[iin RHSO)
2k++ is free
LHS
RHS1
2k+1 is infeasible
(14)
RHSO
Tk+1 is infeasible
There is an important fact that we have defined f(4, c) = + when 2; = 0 or has no feasible solution. This constraint should be taken into the loss function well. Therefore, the loss function (for one-step state-transition) can be designed as follows:
(LHS min(RHSI......... RHSO))²
Tk+1 is free
(os)(0)=
(LHS RHS1)² ReLUU RHSO)
Ik+1 0 is infeasible
(15)
[LHS- RHSS)2 ReLU RHSI)
Tk+1 is infeasible
The purpose the ReLU item make the output of go large enough when the sub sub-problemt not feasible. In fact, in one-step state transition, Ge can obtain the correct optimal solution long the output value of go in the infeasible state is greater than the one the feasible. When the training over, the optimal solution be obtained according to the equation 16 in each step.
Øk+1 = {
go (A",", b²,c") S C++1 + go(A", b' ak+1, d") (A", A", b', (,,")) C++1 + Ao AA, b' axt1,
(16)
B
TRAINING PROCESS
Scart
OPTTA ficed
Generating i% and push into the data pool
OPT Fy. Re: fixed
zu foasuble.
00e only
Random sampling data pool, celculete loss dozording to different label
Update the paremeter by R, P/9.)
argnints + Ja a- 4,e" (A,
Xy randomly
2)
Output solution objval panameter By without feasibility jadgement
W = 6,7, +
Push feasbilit label)
Endl
Figure Training process used in NNVal VI
11

---

Under review as a conference paper at ICLR 2023
In order to understand the training process of the algorithm, we provide the algorithm flowchart and pseudocode this section. For algorithm NNVal V1, the flowchart is Figure the pseudocode is Algorithm 3 and for algorithm NNVal V2, the flowchart is Figure and the pscudocode is Algorithm
Algorithm Training Algorithm for NNVal VI
1: Initialize ge, data pool D, exploration rate learning rate 7 and max iteration number T, t <-)
2: while
do
3: Trý, sol <- GENERATETRAVECCORRY (g,
4: Push Trj with weight c" sol into data pool
5:
Generate batch training data B by weighted sampling in D
6:
Calculate L(0) EB L(0)
7: 0 O- 0 L)O)
8: Evaluate ge
9: end while
10: function
A.c) c) m, n f A.shape, Dtmp + (1,..., 1).
12:
Initialize sol, Trj
13:
for =
do
14:
+- the i-th column of A, +- the i-th number of c
15:
Ag <- A, the i-th column of A 0- 0
16:
J1 CHECKFEASIBLE( A, Demp az)). Jo <- -CHECKFEASIBLE btmp)
17:
R1 < g(A, htmp - a;) + G. Ro f g(A, Btmp)
18:
According J1 Jo, R1, Ro, calculate 2; with exploration c, update Demps push T;
into sol, push (Au, A, htmp: Css, 4)) into Trj
end for return Trj.sd. sol
20:
end function
22:
function CHECKFEASIBLE(A/
if A. is feasible then
24:
return True
else
26:
return False
27: end
28:
end function
Generating data based on 0, and push into the data pool
OPT OPT.A.....H. Ai.; flxed
frow
should
Random sampling from data pool. calcurite loss according to different label
Updele the peremeter by 0yes P)(0.)
araminls fEA b- (00) (.l'...)))
is 03 uanlanily
2,
Cutput the solution besed on persmeter 9. with fixing module
W Cj Cuty ... Cafl
End
Figure Training process used in NNVal V2
12

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Training Algorithm for NNVal V2
Initialize ge, data pool D, exploration rale e, learning rate 7 and max iteration number T, f
2: while & < 'I' do
3:
Trj, sol <- GENERRATTTRAACCTORRY(Y... A. c)
4:
Push Try with weight e" sol into data pool D
5:
Generate a batch training data B by weighted sampling
6:
Calculate L()) EB L(0)
7: 0 4 0 V0)
8: Evaluate go
9:
end while
10: function GENBATETTRJJECTORYY, A.
11: m, 72 + A.shape, bimp f- {I,..., 1)", initialize sol, Trj
for i = do
13:
Oi t the i-th column of A, C, + the i-th number of c, Ao + A. fix + CHECKFIXING(A. bimp..) 1)
15:
if label = True then
Push I; into sol, the i-th column of +
17:
Push (Ao, A, Demps 02, Ci) into Trjj, Demp <- Dtmp
else
19:
The i-th column of A +- O. push (Ao, A, Damp Cii Ci) into Trj R1 4- (A, Dtmp - a.) + Ci Rg f 9(A Dtmp)
20:
21:
According to R1, Ro, calculate r; with exploration rate update bemps push 2; into
sol
22:
end if end for
23:
24: return Trj, sol
25: end function
function CHECKFIXING(A, idx)
27:
n + A.shape, label + False, initialize f fix_ides for 1-+ m and bli] do Calculate cnt, which is the number of 1 in Ali). pos means position of if cnl = then
29:
30:
31:
Push pos into fiir_dds
32:
end end for
33:
34:
if ide in fir idns then
35:
label True
36:
end if
37:
return label, fix kidss
38:
end function
13


Reviews:
[{"review_id": "j55offTtJy", "reviewer": "Reviewer_CYCn", "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": "", "summary_of_the_paper": "This paper proposes a neural network based machine learning method for deciding binary variables at each search step. Some design decisions such as layers of the neural network, the loss functions and etc are made. Some numerical results to demonstrate the performance of the proposed method are given.", "summary_of_the_review": "Overall, the contribution of this paper is marginal. The numerical experiments are not carried out extensively so the improvement of the proposed method is hard to justify.", "strength_and_weaknesses": "Strengths:\n\nThe results presented show seemingly significant improvements.\n\nWeaknesses:\n\n1. There is only one experiment conducted on a random dataset. Also the compared method is only a classical method. There exists some other heuristic methods which are mentioned but not compared. Thus the improvement of the method is not quite convincing.\n\n2. The meta-heuristic approaches are mentioned in the introduction without any citations.\n\n3. The design of the neural network seems trivial. The loss function is designed but why does it work well is not estabished.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "crEny0xJcqj", "reviewer": "Reviewer_63py", "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": "", "summary_of_the_paper": "The paper proposes a neural-network-based approach to learn greedy heuristics for the WSCP. The authors describe their method and evaluate it empirically, comparing it to a hand-crafted heuristic.", "summary_of_the_review": "The paper investigates an interesting problem, but lacks detail and clarity. This starts with the abstract, which mentions that the loss function should satisfy the Bellman-Ford equation, but no detail of this is given in the paper itself (neither the equation, nor how the loss function satisfies it. The description of the method uses symbols that are not explained. The problem itself is never specified, at least it is not obvious how the state and a solution to the WSCP relate. The architecture for the neural network to solve the problem is simply given, not justified or explained -- why this particular architecture? Did you compare to any other architecture candidates? The authors give two versions of their neural network, the second improving upon the first, but this is not empirically evaluated. It is unclear why two methods are given if only one is evaluated.\n\nThe authors claim that the experimental evaluation considers both execution time and solution quality, but execution times are not reported, only at a very high level that does not allow the reader to compare to the other method. The only other method the authors compare to is from 1979, and the proposed new method does not improve in every case. Only two small sets of relatively uniform instances are considered. It is unclear how the accuracy of the estimation order was evaluated; accuracy seems unsuitable in this case and a rank measure should be used. The authors do not say how they trained their neural network. Based on the description given in the paper, it is impossible to reproduce the results.\n\nNo reference is given for the Chvatal algorithm, which is referred to extensively in the paper. There is no space before references. The authors in a reference are sometimes referred to by their last names, sometimes by their first names. There are typos, grammatical mistakes, and formatting mistakes throughout the paper.", "strength_and_weaknesses": "+ interesting approach to a classic NP-complete problem\n\n- paper not well written and lacks detail to understand what exactly is being proposed\n- experimental evaluation small-scale and compares to only one method\n- many technical details unclear", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "QjGbVJ09sM", "reviewer": "Reviewer_3jeR", "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": "", "summary_of_the_paper": "This paper proposes an approach, called AIA, to learn algorithm design with the aid of neural networks. We consider the minimum weighted set cover problem (WSCP), one of the NP-hard problems, as an representative example.\n\n\n\n\n", "summary_of_the_review": "This is an interesting paper on a critical topic. However, the paper is technically weak and does not allow a reviewer to evaluate it fully.", "strength_and_weaknesses": "Strengths:\n\nThis is an important research area, and the paper has many aspects of novelty.\n\nWeakesses:\n\nThe approach is interesting, but the technical details of the paper are so poor that it is very hard to understand how the algorithm works. Many critical concepts are not defined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "1RRHokgVYK", "reviewer": "Reviewer_Vs8A", "summary": "", "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": "", "summary_of_the_paper": "The paper tackles the problem of the minimum weighted set problem by using a Neural Network. They leverage the recurrence relationship of the state-transition equation, and instead of making the NN learn directly the value of the sub-problems, they make the NN learn the relationship between each state. The model provides a relatively good result, that beats the Chvatal Greedy method in most instances. ", "summary_of_the_review": "About Challenge: \n-The authors claim that they overcame the main challenge by overcoming the idea of fitting the recurrent relation with a neural network. Which is unfeasible due to the neural network being very sensitive to the change in input.", "strength_and_weaknesses": "- The Authors contribute to this area by presenting a more or less novel method of leveraging the recurrence relations between each state. Making an NN estimate the relation between each state.\n- The authors claim that the NN can aid the researchers' design of an algorithm, implying that this is not an end-to-end model. But in the 4.5 NNGreedy algorithm section, essentially, it seems that the algorithm is just deciding whether a node should or should not be included, based on the state information of the node. Which is more or less an end-to-end model.\n- A lot of work on tackling NP-Complete problems using Neural structures has been presented already, what is the key difference between using the plain MLP and say a GNN? Like in this work https://arxiv.org/abs/1809.02721 for example.\n- If one is trying to leverage the recurrence relations between each state, would it be more intuitive to just use an RNN or a GCNN? What is the advantage of using the plain MLP and not his alternatives?\n- Baseline method is limited to a human designed heuristic algorithm. It is not enough to convince that the algorithm could outperform existing methods. A baseline of optimal solutions should be added as well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Reject