Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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).
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: Summary: 
The 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. 

Comments:
I have some concerns on the technical contribution.
First 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. 

The 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. 

As a summary, the idea could be interesting, but the paper is not mature enough.

Comments after Rebuttal:
I 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.  
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: [ 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. ]

The 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.

Pros:
- 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.
- The paper made a reasonable attempt to provide sufficient background to understand the problem.

Cons:
- 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.
- 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.

Additional comments:
- 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.
- 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).
- It would be helpful to give further details on how the best possible strategy is computed, perhaps as part of an appendix.
- 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.
- “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.
review_title: Official Blind Review #2

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