DeepSimplex: Reinforcement Learning of Pivot Rules Improves the Efficiency of Simplex Algorithm in Solving Linear Programming Problems
Authors: Varun Suriyanarayana
Onur Tavaslioglu
Ankit B. Patel
Andrew J. Schaefer
Venue:  (2020)
Keywords: Simplex Algorithm
Pivoting Rules
Reinforcement Learning
Combinatorial Optimization
Supervised Learning
Travelling Salesman Problem

Abstract: Linear Programs (LPs) are a fundamental class of optimization problems with a wide variety of applications. Fast algorithms for solving LPs are the workhorse of many combinatorial optimization algorithms, especially those involving integer programming. One popular method to solve LPs is the simplex method which, at each iteration, traverses the surface of the polyhedron of feasible solutions. At each vertex of the polyhedron, one of several heuristics chooses the next neighboring vertex, and these vary in accuracy and computational cost. We use deep value-based reinforcement learning to learn a pivoting strategy that at each iteration chooses between two of the most popular pivot rules -- Dantzig and steepest edge. 
Because the latter is typically more accurate and computationally costly than the former, we assign a higher wall time-based cost to steepest edge iterations than Dantzig iterations. We optimize this weighted cost on a neural net architecture designed for the simplex algorithm. We obtain between 20% to 50% reduction in the gap between weighted iterations of the individual pivoting rules, and the best possible omniscient policies for LP relaxations of randomly generated instances of five-city Traveling Salesman Problem. 

Under review as a conference paper at ICLR 2020
DEEPSIMPLEX: REINFORCEMENT LEARNING OF PIVOT RULES IMPROVES THE EFFICIENCY OF SIM- PLEX ALGORITHM IN SOLVING LINEAR PROGRAM- MING PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Linear Programs (LPs) are fundamental class of optimization problems with a wide variety of applications. Fast algorithms for solving LPs are the workhorse of many combinatorial optimization algorithms, especially those involving integer programming. One popular method to solve LPs is the simplex method which, each iteration, traverses the surface of the polyhedron of feasible solutions. At each vertex of the polyhedron, one of several heuristics chooses the next neighboring vertex, and these vary in accuracy and computational cost. We use deep value- based reinforcement learning to learn a pivoting strategy that at each iteration chooses between two of the most popular pivot rules Dantzig and steepest edge. Because the latter is typically more accurate and computationally costly than the former, assign higher wall time-based cost steepest edge iterations than Dantzig iterations. We optimize this weighted cost on neural net architecture designed for the simplex algorithm. We obtain between 20% 50% reduction in the gap between weighted iterations of the individual pivoting rules, and the best possible omniscient policies for LP relaxations of randomly generated instances of five-city Traveling Salesman Problem. Our results indicate that learning within combinatorial optimization algorithms is possible and that there much room for improvement in learning more sophisticated pivoting strategies, especially for larger LP instances.
INTRODUCTION
Machine learning has revolutionized many fields by leveraging large amounts of data to learn functions, replacing approaches which used to rely heavily on hand-designed features. One area where machine learning has not made much of an impact is heuristics used inside combinatorial optimization algorithms such as the simplex or integer programming algorithms.
The No-Free Lunch (NFL) theorem (Wolpert al. 1997) of search and optimization essentially says there are no general-purpose optimization algorithms that work well on all problems. In practice, this implies that many optimization algorithms rely on several different kinds of hand-designed heuristics. But these lack theoretical guarantees, and they embody a one-size-fits-all approach that cannot specialize to the instance distribution. clear historical example that of linear programs (L.s). LPs require specification of pivoting rule, and decades of research has generated many different options. However, no theory exists for how to choose pivoting rules based on the instance distributions encountered in practice, let alone how to design new pivot rules based properties of the instance family.
We propose to address this issue by using data-driven machine learning approaches to learn such heuristics, based on the data encountered by the combinatorial optimization algorithms in practice. be interpreted instantiating the converse of the NFL theorem: any advances made in quality or speed must be due to the algorithm's specialization to the distribution/family of instances it encounters.
Our approach

---

Under review as a conference paper at ICLR 2020
In this vein, here focus learning pivot rules for the simplex algorithm for solving LP instances. In particular, we learn new pivoting rule policies that combine existing hand-designed heuristics by training large data sets of LP relaxations of randomly generated instances of the Traveling Salesman Problem (TSP). Our main contributions are:
We introduce a data-driven approach to learning pivoting rules that focuses explicitly on maximizing the speed of optimization as measured by a novel wall-time weighted iteration cost.
We use reinforcement learning to learn hybrid policy that combines two the most prominent pivoting rules for the Simplex algorithm- Dantzig and steepest edge. The resultant policy decides when to switch between the two rules based on the LP instance objective value and reduced costs at that time.
We also employ a novel omniscient oracle-based analysis to gauge just how well our policy does relative to oracle, testing how difficult is to learn the ground-truth omniscient policy, and whether there exist learnable patterns in the omniscient policy or whether it is "random" function that can only be memorized.
We achieve 20-50% reduction in the gap between the existing pivoting rules and the best possible (omniscient) policy. To our knowledge, this is one of the first studies to report improvements via learning for combinatorial algorithms.
2 RELATED WORK
Algorithms for solving optimization problems, e.g., combinatorial optimization problems, often involve heuristic-based algoritmic strategies where, arguably, it is impossible to find an optimal policy that will improve the performance of the algorithm for a wide range of instances. Machine learning approaches give the possibility of devising data-driven methods for the existing heuristics. Khalil et al. (2016) learn to make branching decisions on the branch-and- ann--oundddd tree in mixed-integer programming. Bonami al. 2018) learn classifier for mixed-intege quadratic programming problems to decide whether linearizing the quadratic objective will improve the performance. [Bertsimas & Stellato (219)) solve online mixed-integer optimization problems very high speed using machine learning. They convert parametric mixed-integer quadratic optimization problems to multiclass classification problem and obtain two to three orders of magnitude speedups compared the of-t--ofthh-ar solver Gurobi. [Bngiio et al. (2018) provide detailed survey of machine learning approaches for combinatorial optimization problems.
TSP is canonical example of combinatorial optimization problems, where there are recent studies for developing machine learning-bart
heuristic algorithms (Khalil et al.) [017]] Bonami et al.. 2018, Hansknecht et al., 2018). [Vinyals et al. (2015) develop a supervised learning algorithm for combinatorial problems using "pointer networks" and present computational results for TSPs. [Bello reinforcement learning approach where they optimize the parameters of the recurrent neural network using policy gradient method. They claim that their reinforcement learning approach outperforms the supervised learning algorithm presented by Vinyals al. (2015).
et al. (2016)
Concorde TSP solver (Applegate et al. 2006a) is one of the best exact TSP solvers, which uses cutting plane methods (Applegate et al. 2003) the TSP integer programming formulation, i.e., lazy implementation of a conventional TSP formulation (details given in Section (3). iteratively solves linear programming relaxations of the TSP formulation and uses branch-and-bound tree to reduce the search space for the optimal solution. One of the main motivations of this study is to learn the structure of the LP relaxation of the TSP and speed up solving the iterative LP relaxations by learning pivoting rule policy.
LINEAR PROGRAMMING AND TRAVELLING SALESMAN PROBLEM
general formulation of an LP is as follows:
Minimize c
subject to
Ar = b.
2 0,
2

---

Under review as a conference paper at ICLR 2020
Schematic of
27
35
58
42
a
W.N.
89
Minimize c²x
94
22
subject to Ai
0,
Traveling Salesman Problem
Integer Program (Sequential Form)
Lineur Program (Standard Form]
(Non-Euclidean)
Apply phase row operations
Choose Pivot
Q-Values for each Pivot Rule
Fully Connected ReLU Net
Tableaux
Ieie argins buftmad
cost
Figure 1: Steps of the Learning algorithm
where the objective e E R", right-hand side E RT, constraint matrix A E m and the number of variables is greater than the number of constraints, i.e., decision variable x that minimizes the c' x value over the feasibility region = {i E R AA = b}. There different approaches solve LPs, e.g., the simplex algorithm, interior point methods, and the ellipsoid algorithm, where the interior-point methods and the ellipsoid algorithm are polynomial algorithms. In this study, focus the simplex algorithm, which is the most commonly used method of solving LPs by commercial solvers, c.g., CPLEX and Gurobi.
The goal of an LP is to find optimal
Simplex Algorithm. LPs have attractive properties, including (i) the feasible region is convex, (ii) if there is an optimal solution, there exists an optimal solution that is an extreme point of P, and (iii) an optimal extreme point has most m non-zero entries, which are called basic variables. The simplex algorithm has two phases. Phase one finds basic feasible solution, and Phase two finds an optimal basic feasible solution.
The main idea of the simplex algorithm is to find an extreme point and implicitly check its adjacent extreme points. If no adjacent extreme points improve the objective, then the current extreme point optimal because of the linearity the objective and convexity of P. If there are adjacent extreme points that improve the objective, the simplex algorithm moves to one of them and continues the search until an extreme point with no improving adjacent extreme points can be found. An iteration of the simplex method is given below (Bertsimas & Tsitsiklis 1997).
1. Form the basis matrix B e R= consisting of basic columns of A that are associated with an extreme point (basic feasible solution) I.
2. Compute the reduced costs ε₁ = Cj BB 'A for all nonbasic indices j E {l...., n). i.e., E (1,...,,)) n such that x; 0, where eB is the objective vector associated with the basic entries of x and Aj is the jth column of A. If they all nonnegative, the current basic feasible solution is optimal, and the algorithm terminates; else, choose some j for which Cj < 0.
3. Compute u B Ay. If no component of is positive, we have 6* oc, the optimal cost is 000 and the algorithm terminates. If some component of is positive, let 0* min #BG) and l E arg min M4
=g(()
4. Form a new basis by replacing A A with Aj. If If is the new basic feasible solution, the values of the new basic variables are Uj 8" and yB(3) BB()) u, + l.
Pivoting Rule. The bold part in Step 2 is the only part of the simplex algorithm that is not precisely specified. The rule of choosing an index is called as the pivoting rule. There are many proposed ways to choose the extreme point among the adjacent points in Step 2 above, e.g., Bland's 's rule, Dantzig's 's rule, steepest edge rule, and greatest improvement rule. The most commonly used methods for choosing the next extreme point, i.e., the pivoting rule, are Dantzig's rule and the steepest edge rule. Dantzig's 's rule calculates the rate of improvement (reduced costs) for all nonbasic variables and chooses the best one, i.e., choose arg min Cj. where Cg < O, and the steepest edge normalizes the
3

---

Under review as a conference paper at ICLR 2020
reduced costs with the norm of their corresponding updated constraint matrix columns and chooses the best one, i.e., choose E arg min T where Cy < 0.
Among the mentioned pivoting rules, only Bland's rule guarantees finiteness; however, it is practically efficient. For the remaining methods, generally the total number of required iterations of the simplex algorithm decreases as the pivoting rule becomes more complex and requires more time to choose the leaving variable. However, there is no guarantee that a more expensive pivoting rule (in terms of the time it takes calculate the leaving variable) takes fewer iterations find an optimal solution. Furthermore, these methods do not guarantee finiteness. Hence, pivoting rules may be improved by learning algorithms.
The simplex algorithm can be viewed as problem of finding a path on a graph, where extreme points are nodes and only adjacent extreme points are connected. The starting node the initial extreme point and the end node is an optimal extreme point. The pivoting rules dictate how the next node on the path is selected. Thus, the pivoting rule is a natural candidate for learning algorithms.
Travelling Salesman Problem. LPs are essential for solving integer programs (IP) which are LPs for which the decision variables are restricted to take only integer values. Unlike LPs, IPs are A'r-hard. The most common way of solving IPs is using manchhand-boung algorithms, which we repeatedly solve linear relaxations of the IP with added inequalities (dropping the integrality requirement and solving the corresponding LP) obtain feasible integer solutions to form global lower bound and to get local upper bounds with the relaxed problem.
In this study, we focus the LP relaxation of the TSP. The TSP considers list of cities connected graph and finds the shortest route that visits each city exactly once and returns to the origin city. The TSP is famously hard solve, which has attracted the attention of many researchers from different fields. The TSP is an IP with many different formulations presented in the literature, e.g., the subtour elimination formulation Dantzig et al. (1954) and the sequential formulation Miller et al.) (1960). Both formulations use a set of cities N = {l...., n where the length of an are 2, E N is Cij. and define decision variables Tij- if and only if j.j E N a link in the tour and Taj = otherwise. Furthermore, both formulations share the following objective and constraints:
Minimize
Σ
Cij
(1a)
NJENN
subject to jEN:j#i
Σ
Dij
1
Vi N,
(lb)
Σ Tij
1,
Vj N
(1c)
iEN:
Zij E (0, 1},
V.. N
(1d)
The conventional formulation Dantzig et al. 1954) has the following set of subtour climination constraints
Ty S M - 1, VM C N11,, [M| 2
(1e)
N.jEN
Hence, the conventional formulation has n(n 1) binary variables and 2n + 2n - 2 constraints.
The sequential formulation introduces new continuous variables u, which represents the sequence in which city i is visited for i * 1. The set of extra constraints of the sequential formulation is
u4 uj + nxy I 1, Vi,j N ML), i i
(1f)
The sequential formulation has n 1) binary and n continuous variables, and n² n + constraints. The sequential formulation has polynomial number of constraints compared to the exponential number constraints of the conventional formulation. However, the conventional formulation is more practical computationally. despite its larger size (Applegate et al. 2006b).
Our study focuses on reducing the solution time of the LP relaxation of the sequential formulation for the TSP. We aim to learn optimal way of choosing the pivoting rule for the LP relaxation of the sequential formulation which will potentially lead to reduction of the TSP solution time using the sequential formulation.
4

---

Under review as a conference paper at ICLR 2020
4 LEARNING APPROACH
Our study focuses reducing the solution time of the LP relaxation of the sequential formulation for the TSP. We aim to learn an optimal way of choosing the pivoting rule for the LP relaxation of the sequential formulation, which will potentially lead reduction of the TSP solution time using the sequential formulation.
The main steps of our learning algorithm are illustrated in Figure [ The first step is generating TSP instance by determining the number of nodes and assigning distance between them. We formulate the problem using the sequential formulation and take its linear relaxation. We then convert the LP relaxation to the standard form by adding slack variables so that we can use the simplex algorithm to solve the instance. We use the phase one implementation of linear programming solver to find a basic feasible solution. The focus of this study is learning pivoting rule for phase two of the simplex algorithm, where the algorithm starts from a basic feasible solution and finds a path to an optimal solution by traveling to neighboring basic feasible solution in each iteration.
Every basic feasible solution of the LP has its own basis matrix B, reduced cost é, and right-hand side b. In each iteration in phase two of the simplex algorithm, we pass the reduced cost vector č and the objective value to a fully connected ReLU neural network to estimate the Q-Value which decreases as expected weighted distance rises. Based on the Q-Value estimations, we choose a pivoting rule and iterate the simplex algorithm. The algorithm continues to choose a pivoting rule in each step until the simplex algorithm reaches optimal basic feasible solution.
EXPERIMENT DESIGN
We generate TSP instances with five citics. We use five-city TSP instances because they are the largest TSP instances where we can build and store the exact graph of the extreme points of the LP relaxation. All instances have fully connected graphs where the cost of traveling between two cities is random integer value between and 100. We construct 1000 instances where we use 800 of them for training and the remaining 200 for testing.
Training Data:
We consider only Dantzig's 's and the steepest edge rules because they are the most commonly used pivoting rules in practice. At iteration t of the simplex algorithm, we define action a if the Dantzig's rule is selected and o 1 if the steepest edge rule is selected. The state space is the set of possible simplex tableaux. We denote the current state at iteration & as st.
Action and State Space:
Choice of metric: We minimize the total number of weighted simplex iterations. The steepest edge rule is computationally more expensive. Thus we penalize the learner more for choosing the steepest edge rule over Dantzig's rule. We calculate the relative cost of the steepest edge against Dantzig's s rule by solving all of the generated TSP instances using purely Dantzig's 's rule, and purely the steepest edge rule, We calculate the average time of a single iteration for both the Dantzig's 's rule and the steepest edge rule. In our experiments, we find that the steepest edge rule is 15% more costly than the Dantzig's rule. Hence we weight each steepest edge itcration with 1.15. We note that this relative cost may be hardware and software dependent enabling user customize.
We denote T as the maximum number of unweighted iterations, which is taken as 28 for our experiments to limit the size of Q-values without cutting off a significant portion of paths to optimal solutions, w as the factor by which steepest edge rule is costlier relative to Dantzig's rule, i.e., 0.15, (((s)) as the objective value before the action is performed, f(st, (x) as the objective after the action is performed, le as the optimal value. Then the reward, denoted as R(8;, or), at iteration / is:
Reward function:
t> T or El = E"
t< T, a, 0, and (s.) E(s a.) C.
R(st (x)
1
L LS T. at 0, and (( 0t) > lt.
T 1
t < T, a 1, and f' (s:) > [(s az) = le,
1
t tsT dt = 1, and ((8 44) > lt.
T
5

---

Under review as a conference paper at ICLR 2020
Q-Value function: The true Q-value function, denoted Q', is the total of expected discounted future rewards,
Q' (ser, ae) )= = R(se' ar) ) +
max (me)
Σ
R(s,, az)
t=
where 8t-1 - S, is valid state transition and is the discount factor. If the optimal policy x' actions a" are known in advance, e.g., obtained by using the full simplex graph, then the optimal Q-value function, Q", can be derived using the following recursion when ? 1:
Q' (18411,441 = = (st, a,) + T + wa..
Network architecture: The network has 8 fully connected hidden layers, where each layer has a width of 128 and ReLU activation functions. The input of the network is the reduced costs and the objective value of at the given simplex algorithm iteration. The width of the output is 2, the predicted Q-Value when choosing Dantzig's 's rule and the steepest edge rule, respectively. The tanh activation function is applied on the 2 outputs.
5.1 LEARNING WITH Q" -VALUE
Unlike usual reinforcement learning (RL) applications, for the linear relaxations of five-city TSP instances,
generate Q" -alvuless by creating the extreme point graph of each LP instance where edges represent possible transitions using the Dantzig's rule or the stcepest edge rule. Since these graphs tell us how many weighted and unweighted iterations from any given current state/tableau/vertes and the action that leads to the optimal solution fastest, we can use these actions recursively construct the Q' Qa-veless. Before attempting to learn the Q-values using RL, we use supervised learning of Q" to glean insights regarding the "learnability" of Q* and the improvement potential RL algorithms for minimizing the total weighted iterations.
needed reach the optimal solution
Training Algorithm:
For each LP instance, at each iteration of the simplex algorithm. random choice of action is taken. The tableaux for that LP are stored and sorted into batches of the chosen batch size. Then the neural network is trained on this data set using supervised learning with -'vvalues
Loss Function:
For a single epoch of the training algorithm, at each iteration of simplex, the neural network generates estimated Q- Values for the simplex tableau. The action corresponding to the higher Q- V-Vulee is chosen and the error with respect to the Q" -values is noted. The mean square error over all tableaux reported as the test loss for that epoch.
5.2 LEARNING WITH DEEP RL
Learning with -aalul tests the potential for learning pivoting rules, and learning with Deep RL, without using Q -aauuss, aims to show whether it is possible to improve the performance of the simplex algorithm using RL.
We implement a standard Q-learning algorithm with the reward function described above. During an epoch, for each LP, each iteration of simplex, the tableaux for the LP instances are stored and sorted into batches. Then the network provides estimated Q- Q-Values, where an action is chosen with an epsilon-gen opsilon-greedy approach. Q- D-Vuuu of the next state and therefore the gradients are found using the target network which is updated every 1/2 epoch. Epsilon is decayed appropriately.
Training Algorithm:
Loss function: At any it and tableau 8,, we perform action ot and transition to tableau 8141 (st, az). We define the loss as the mean square error between Q(se, ar) and max.,-1 Q(5c+1, dc+1) T wa,, where Q refers to the network's 's estimation of Q".
6 EXPERIMENTAL RESULTS
We first give performance results on supervised learning with valuus and reinforcement learning algorithms. We then give overall analysis of the experiments.

---

Under review as a conference paper at ICLR 2020
6.1 LEARNING WITH Q' -VALUES
Figure 2: Performance comparison of the supervised learning with QV-aalues (blue line) against random pivoting rule (purple line), pure Dantzig's ' rule (orange line), pure steepest edge rule (green line), and the best possible strategy (red line) for weighted and unweighted iterations on training (first row) and test sets (second row) for 850 epochs.
Training Weighheeiteattonn By Fpoch
Training Unweighted teeratonns By Epoch
Trahinn loss
150
12
124
0.111
131
133
Wy poliiig tigghee VAllihhheee Shh
125
with Afgeet Anl yHtee
0.80
0.08
181
132
0.04
Test Wwwghtod Mtrattons Epoch
Unswiighted Etecraiionn Ipach
0.004
0,544
12.5
0.00
0.04
11.5
Figure presents the performance comparison of the supervised learning with Q" -valuess against pure Dantzig and steepest edge rules, random strategy where Dantzig's 's rule the steepest edge rule is chosen with a 50% chance, and the best possible strategy calculated using the graph representation of the simplex algorithm. The first column of Figure 2 shows the performance of the algorithms for weighted iterations, which is the metric used for training the network. The second column shows the number of unweighted iterations, i... the total number of iterations taken. The final column gives the training and test loss in each epoch.
For weighted iterations, the pure Dantzig's 's rule takes 13.17 iterations, the pure steepest edge takes 11.85 iterations, and the random policy takes 12.9 iterations. The best performing network on the test set takes 11.33 iterations with a corresponding 11.09 iterations on the training set. The network used steepest edge 45.2% of the time on the training set and 47.6% of the time on the test set. The best policy takes 9.65 weighted iterations on average and uses steepest edge 19. of the time. Hence, the trained network outperforms all of the pure and random strategies, reducing the difference between the best policy and the pure Dantzig's 's rule, the pure steepest edge rule and the random policy by 52.3%. 23.6%, and 48.3%, respectively.
The hyperparameters used are learning rate of 0.0001, a batch size of 128 tableaus, Orthognal Initial- isation and Adams Optimizer with default Tensorflow parameters and L2 regularization of 10 10-7
6.2 DEEP REINFORCEMENT LEARNING (RL)
The experiments have the following parameters: 0.001 learning rate, 128 batch size, orthogonal initialization, Adams optimizer and L2 regularisation with À = 10-7 We use an epsilon greedy approach to training over time, epsilon begins at 1.00 and is annealed to 0.01 over 50 epochs linearly. The target network updated twice per epoch.
presentss the performance comparison of the deep reinforcement learning algorithm against pure Dantzig and steepest edge rules, the random strategy, and the best policy where their weighted iteration performances on the test set are 13.17, 1 11.85, 12.9, and 9.65, respectively. The best test performance of the deep RL is 11.25 weighted iterations (using steepest edge 70.1 % of the time) with corresponding 11.17 on the training set (using steepest edge 70.2% of the time), reducing the difference between the best policy and the pure Dantzig and steepest edge rules, and the random policy by 54.5%, 27.3%, and 50.8%. respectively. The last row of Figure 2 shows the RL loss plots training and test sets. The last column of
the true loss with respect to the Q -values calculated in Section 6.1 indicating that deep RL. network successfully estimates Q' -values.
7

---

Under review as a conference paper at ICLR 2020
Figure 3: Performance comparison of the deep reinforcement learning algorithm (blue line) against random pivoting rule (purple line), pure Dantzig's s rule (orange line), pure steepest edge rule(green line), and the best possible strategy (red line) for weighted and unweighted iterations on training (first row) and test (second row) sets for 500 epochs, given with both the reinforcement learning loss and true loss against Q' -values.
Training Weighted iterations By Epoch
Training Unweighted Iterations Epoch
True Training Loss
13.0
13.0
13.5
12.
618
Test Weighted By Epoch
Test Unweighted Iterations By Epoch
True Test Loss
130
12.
12.
6:20
135
110
605
65
Reinforcement Learning Training
Deinnorcementteeriing Lost
3.30
365
6.3 ANALYSIS OF RESULTS
One of the most striking consequences of experiments is that the deep Q network performs on par with the network trained with Q' -vauuu in terms of weighted iterations on the test sets, which suggests that the use of more sophisticated RL frameworks is unlikely to bring significant improvement. The capacity the network trained using RL to perform well as supervised learning with Q' -values also suggests scope for success on larger instances, and highlights the need for more bespoke neural network architectures for further improvement.
7 CONCLUSION AND FUTURE WORK
We provide the first study on pivoting rules of the simplex algorithm and show the potential for reducing the wall time of solving LPs. Applegate et al. (2003) report that their exact TSP algorithm spends more than 98% of its computational time for solving LPs large TSP instances. Hence, we believe designing data-driven pivoting rules for family of LP instances have potential benefits.
In this study, we have focused on small TSP instances (five cities) due to the cost of training neural networks and the difficulty of developing new architectures for this task. Also, omniscient oracle analysis becomes intractable for a larger number of cities. In future work, we want to explore how well our approach scales to larger LP instances and how well it can be incorporated into combinatorial optimization algorithms that solve LPs as a subroutine. The neural network inference has a significant wall time cost, and we do not consider hardware acceleration approaches here. However, the successes seen on mobile devices for image and video recognition networks suggest that there is something to be gained, then the hardware will follow. Finally, results rely the relative wall time estimates, which are, in turn, heavily dependent on the hardware used and the typical instance size the family. We plan to update algorithm to learn wall-time costs online.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. Implementing the Dantzig- Fulkerson-Johnson algorithm for large traveling salesman problems. Mathematical Programming. 97(1):11-153, Jul 2003.
David I. Applegate, Robert E. Bixby, Vašek Chvátal, and William J Cook. Concorde TSP solver, 2006a.
David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. The traveling salesman problem: A computational study. Princeton University Press, 2006b.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial
optimization with reinforcement learning, arXiv preprint wwxiv:/611.0994// 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' h'orrizon. arXiv preprint 1011vv181110611111 2018.
Dimitris Bertsimas and Bartolomeo Stellato. Online mixed-integer optimization in milliseconds.
arXiv preprint arXiv: 00000020 2019.
Dimitris Bertsimas and John N Tsitsiklis. Introduction Linear Optimization, volume 6. Athena Scientific Belmont, MA, 1997.
Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning a classification of mixed-integer quadratic programming problems. Willem-Jan van Hoeve (ed.), Integration of Constraint Prugramming, Artificial Intelligence, and Operations Research, pp. 595-604, Cham, 2018. Springer International Publishing.
George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of large-scale traveling-salesiee salesman problem. Journal of the operations research society America, 2(4):393-410, 1954.
Christoph Hansknecht, Imke Joormann, and Sebastian Stiller. Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem. arXiv preprint arXiv:1805.0144 2018.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30,
pp. 6348-6358. Curran Associates, Inc., 2017.
Elias Boutros Khalil, Pierre Le Bodie, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Clair E Miller, Albert Tucker, and Richard Zemlin. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4):326-33))) 329, 1960.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. D. Lawrence,
D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2692-2700. Curran Associates, Inc., 2015.
David H Wolpert, William G Macready, No free lunch theorems for optimization. 1EEE transactions on evolutionary computation, 1(1):67-82, 1997.


Reviews:
[{"review_id": "rygvZne-9S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe authors propose a deep-reinforcement learning method for training how to choose pivot rules for the simplex algorithm for a set of LP instances. In particular, the authors applied the RL-approach to randomly generated TSP problems with five cities, which reduces the costs. \n\nComments:\nI have some concerns on the technical contribution.\nFirst of all, I wonder in what kind of realistic situations where we want to “learn” something from optimization problem instances. When we can learn something, the problems would share some properties and there have to be many such instances. I don’ know practical examples of such a scenario. The artificial TSP instances used in the experiments are not convincing for practical applications. \n\nThe second concern is the scalability. In the experiments, TSP instances with only five cities are used, for which a simple brute-force search is still acceptable and too small. So, the proposed method is far from practical yet. \n\nAs a summary, the idea could be interesting, but the paper is not mature enough.\n\nComments after Rebuttal:\nI read the authors' rebuttal comments. I think the authors' work is valuable and should be investigated further, but the scalablity issues make me feel that the paper is still premature.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "H1eYwcTTtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[ EDIT: Thanks for the response. I still believe the paper is not ready for publication, so I'll keep my rating unchanged. But as I said before, this is a really interesting research direction and I hope the authors will continue this work to collect more results and re-submit it. ]\n\nThe paper proposes learning a policy for selecting a pivoting rule to apply at each iteration of the Simplex algorithm for linear programming. Several pivoting rules have been proposed in the optimization literature, and different rules work better than others on different instances. By learning a policy that switches among the existing rules at each step of the Simplex algorithm, it may be possible to construct a pivoting rule that outperforms existing ones. The paper considers learning to switch between the Dantzig rule and the steepest edge rule as an RL problem. Results on 5-city TSP instances show that the learned policy can outperform both rules on a test set with respect to number of iterations.\n\nPros:\n- The problem is very interesting and definitely should be explored further. Learning could potentially help combine rules in an instance distribution-specific manner to construct better pivoting rules.\n- The paper made a reasonable attempt to provide sufficient background to understand the problem.\n\nCons:\n- The results on the 5-city synthetic TSP instances are not sufficient. While I understand the motivation for considering small problems to measure the best possible strategy’s performance and to learn on Q* values, I’m not convinced that the insights from such small synthetic problems would necessarily transfer to larger LPs for which the solve time is large enough to be able to afford the overhead of neural network inference to try to reduce it. The learning challenges will likely be very different, and the tradeoff between the inference cost of the neural network and the savings from reducing iterations will also likely be different. Scaling up and neural network inference cost are briefly mentioned in the conclusion, but I believe those are the main challenges.\n- Presentation of the results need to be improved significantly. Figures 2 and 3 need to be annotated properly and explained more clearly so that they are easy to understand.\n\nAdditional comments:\n- Although I’m recommending rejection, the problem is interesting and I hope the authors will continue working on it to develop the ideas further and collect results on larger scale problems.\n- For permutation invariance and ability to handle variable-sized inputs, a graph neural network would be a better architecture (see, e.g., Gasse et al., NeurIPS’19).\n- It would be helpful to give further details on how the best possible strategy is computed, perhaps as part of an appendix.\n- Another baseline to compare against is the performance of an oracle that makes the best possible choice of the pivoting rule per problem instance. This will indicate how well a fixed choice per instance can work if that choice is made as well as possible, compared to switching among choices at each iteration.\n- “To our knowledge, this is one of the first studies to report improvements via learning for combinatorial algorithms.” This sentence needs to be clarified because a literal interpretation of it is not true, as shown by, e.g., Bengio et al. https://arxiv.org/abs/1811.06128.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygYFMhZcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a learned method for speeding up optimization of LP, with an application to the TSP problem. In particular, they discuss choosing a pivoting strategy in the simplex algorithm that is set up as a 2-class classification problem, taking the simplex tableau and outputting one of two classes (Dantzig or steepest edge). They consider both the supervised learning approach where they first compute the optimal policy Q*, as well as the RL approach.\n\nThe paper presents a quite interesting approach to solving the TSP, using NNs on top of the tableaus. I enjoyed the presented ideas, however the authors could have done a great job of clearly presenting their work. Notation is not the best, and the experiments are quite limited, indicating limited practical value of the current approach. Detailed comments follow:\n- Especially given that the authors have 2 more pages for writing, it would be beneficial to add more visualization and intuitive explanations of the presented ideas.\n- The notation should be improved, especially given that there isn't that much notation anyway. E.g., eq (1e) and the following one are not quite clear, what is M? Is it a scalar, or a set? Reading closely it becomes clear it is a set, but the authors use upper-case letter both for scalars and sets, leading to confusion. This is very easy to fix, and would help readers quite a lot.\n- The first paragraph in Section 4 is literally a copy-paste of the last paragraph in Section 3.\n- Accompanying Section 4 discussion, would be good to add a figure showing an example tableau. Actually, tableau is not even mentioned here and is the main input to the network, it is only mentioned later.\n- Using just 5 cities does seem small, indicating limited practical value of the method. Please comment on the actual full size of the exact graph of the relaxation, and why is it infeasible to store. Currently the explanation is hand-wavy.\n- \"The state space is the set of possible simplex tableau\", so you enumerate all the possible tableaus of extreme points prior to training? It seems yes, but would be good to explain that explicitly.\n- In \"Reward function\" section, \"as the objective value ...\", please add a reference to eq (1a) here. It helps readers follow the text by referencing already introduced parts.\n- Where did the equations for rewards come from? They are just given, without much explanation or intuitive discussion.\n- Above Section 5.1, \"where s_{t-1} -> s_t\", where is this notation even used?\n- Typo: \"value of at\"\n- Is it \"tableau\" or \"tableaux\"? Choose one.\n- Section 5.1, are both outputs updated at each iteration? It says that a random action is taken, but is that after Q-values for both actions are checked? It seems yes, but it is not clear. \n- In general, a number of small details are missing, and the authors should make sure to not skip them. This introduces confusion to the text which should clearly be avoided.\n- \"Epsilon is decayed appropriately.\" How?\n- Please define an epoch. In particular, what constitutes a 0.5 epoch, and how does the update actually work here? So you store examples into batches, keep them on the side, and once half an epoch passes only then use them to update the model? It seems yes, but again would be good to be more gentle in explanations.\n- Maybe add an algorithm illustrating the methods? In addition to visualization mentioned above.\n- Figures are not really super visible. Also, figures should have captions, so text go below the figure.\n- Figure 2 is referenced in Section 6.2, where it should be Figure 3.\n- \"weighted\" vs. \"unweighted\" iteration should be defined earlier. It is nowhere introduced, and while it may be clear what it means, it is not clearly defined and it should be.\n- \"Adams optimizer\"? Do you mean Adam?\n- Experiments are somewhat weak, and seem to indicate that the method does not have much practical value. Is the method useful beyond 5-city size?\n\n\n===== AFTER THE REBUTTAL ======\n\nThank you for your rebuttal, and especially for the extra experiments! It definitely adds a lot of value to this effort.\nThe writing could still be improved, as a number of details are missing as explained in the review and to some extent acknowledged by the authors. I liked the idea quite a lot and would not mind seeing it in the conference, but given the number of issues raised by myself and others it seems that the best route forward is rewriting the paper given the inputs by the reviewers and submitting to a future venue. \n\nI will remain at a \"borderline\" evaluation, and if the other reviewers change their recommendations to (weak) accept I would not mind accepting the paper (assuming all the changes and promised fixes are implemented).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper present a learning method for speeding up of LP, and apply it to the TSP problem.

Reviewers and AC agree that the idea is quite interesting and promising. However, I think the paper is far from being ready to publish in various aspects:

(a) much more editorial efforts are necessary
(b) the TPS application of small scale is not super appealing 

Hence, I recommend rejection.
Decision: Reject