This paper introduces a framework for solving combinatorial optimization problems by learning from input-output examples of optimization problems. We introduce a new memory augmented neural model in which the memory is not resettable (i.e the information stored in the memory after processing an input example is kept for the next seen examples). We used deep reinforcement learning to train a memory controller agent to store useful memories. Our model was able to outperform hand-crafted solver on Binary Linear Programming (Binary LP). The proposed model is tested on different Binary LP instances with large number of variables (up to 1000 variables) and constrains (up to 700 constrains).
# Summary
This paper proposes a neural network framework for solving binary linear programs (Binary LP). The idea is to present a sequence of input-output examples to the network and train the network to remember input-output examples to solve a new example (binary LP). In order to store such information, the paper proposes an external memory with non-differentiable reading/writing operations. This network is trained through supervised learning for the output and reinforcement learning for discrete operations. The results show that the proposed network outperforms the baseline (handcrafted) solver and the seq-to-seq network baseline.
[Pros]
- The idea of approximating a binary linear program solver using neural network is new.
[Cons]
- The paper is not clearly written (e.g., problem statement, notations, architecture description). So, it is hard to understand the core idea of this paper.
- The proposed method and problem setting are not well-justified. 
- The results are not very convincing.
# Novelty and Significance
- The problem considered in this paper is new, but it is unclear why the problem should be formulated in such a way. To my understanding, the network is given a set of input (problem) and output (solution) pairs and should predict the solution given a new problem. I do not see why this should be formulated as a "sequential" decision problem. Instead, we can just give access to all input/output examples (in a non-sequential way) and allow the network to predict the solution given the new input like Q&A tasks. This does not require any "memory" because all necessary information is available to the network.
- The proposed method seems to require a set of input/output examples even during evaluation (if my understanding is correct), which has limited practical applications. 
# Quality
- The proposed reward function for training the memory controller sounds a bit arbitrary. The entire problem is a supervised learning problem, and the memory controller is just a non-differentiable decision within the neural network. In this case, the reward function is usually defined as the sum of log-likelihood of the future predictions (see [Kelvin Xu et al.] for training hard-attention) because this matches the supervised learning objective. It would be good to justify (empirically) the proposed reward function. 
- The results are not fully-convincing. If my understanding is correct, the LTMN is trained to predict the baseline solver's output. But, the LTMN significantly outperforms the baseline solver even in the training set. Can you explain why this is possible?
# Clarity
- The problem statement and model description are not described well. 
1) Is the network given a sequence of program/solution input? If yes, is it given during evaluation as well?
2) Many notations are not formally defined. What is the output (o_t) of the network? Is it the optimal solution (x_t)? 
3) There is no mathematical definition of memory addressing mechanism used in this paper.
- The overall objective function is missing. 
[Reference]
- Kelvin Xu et al., Show, Attend and Tell: Neural Image Caption Generation with Visual Attention