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 valuebased 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. Our results indicate that learning within combinatorial optimization algorithms is possible and that there is much room for improvement in learning more sophisticated pivoting strategies, especially for larger LP instances.
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.
The 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:
- 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.
- 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.
- The first paragraph in Section 4 is literally a copy-paste of the last paragraph in Section 3.
- 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.
- 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.
- "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.
- 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.
- Where did the equations for rewards come from? They are just given, without much explanation or intuitive discussion.
- Above Section 5.1, "where s_{t-1} -> s_t", where is this notation even used?
- Typo: "value of at"
- Is it "tableau" or "tableaux"? Choose one.
- 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. 
- 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.
- "Epsilon is decayed appropriately." How?
- 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.
- Maybe add an algorithm illustrating the methods? In addition to visualization mentioned above.
- Figures are not really super visible. Also, figures should have captions, so text go below the figure.
- Figure 2 is referenced in Section 6.2, where it should be Figure 3.
- "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.
- "Adams optimizer"? Do you mean Adam?
- 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?
===== AFTER THE REBUTTAL ======
Thank you for your rebuttal, and especially for the extra experiments! It definitely adds a lot of value to this effort.
The 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. 
I 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).