Designing efficient algorithms for combinatorial optimization appears ubiquitously in various scientific fields. Recently, deep reinforcement learning (DRL) frameworks have gained considerable attention as a new approach: they can automatically train a good solver while relying less on sophisticated domain knowledge of the target problem. However, the number of stages (until reaching the final solution) required by existing DRL solvers is proportional to the size of the input graph, which hurts their scalability to large-scale instances. In this paper, we seek to resolve this issue by proposing a novel design of DRL's policy, coined auto-deferring policy (AutoDP), automatically stretching or shrinking its decision process. Specifically, it decides whether to finalize the value of each vertex at the current stage or defer to determine it at later stages. We apply the proposed AutoDP framework to the maximum independent set (MIS) problem and its variants under various scenarios. Our experimental results demonstrate significant improvement of AutoDP over the current state-of-the-art DRL scheme in terms of computational efficiency and approximation quality. The reported performance of our generic DRL scheme is also comparable with that of the existing solvers for MIS, e.g., AutoDP outperforms them for the Barabási-Albert graph with two million vertices.
The paper proposes a Deep RL approach called Auto-Deferring Policy (ADP) to learning a policy for constructing solutions for the Maximum Independent Set (MIS) problem. Rather than constructing a solution one variable per episode step, the policy can make decisions about multiple variables per step, as well as defer decisions to later steps. At each step the MIS constraints of a valid solution are checked and decisions that violate the constraints are reverted, and any additional decisions that are automatically implied by the decisions so far and the MIS constraints are taken. The policy and value function are parameterized as a graph convolutional network to make use of the graph structure of the problem. A diversity regularizer that encourages the policy to generate diverse final solutions is used for training. Results show that the approach is able to match the objective value of the state-of-the-art solvers on several datasets, and is able to outperform S2V-DQN on several datasets when neither approach is trained on them.
Pros:
- Extensive experiments have been done on several datasets, both synthetic and real. The ablation and generalization experiments are particularly valuable for getting insight into the performance of the algorithm.
- Comparison to CPLEX and ReduMIS strengthens the results.
- The paper is reasonably well-written and easy to follow. Figures 2 and 3 are especially useful for quickly understanding key ideas.
Cons:
- The update and clean-up phases inject significant domain knowledge about MIS into the policy. At a high level the idea is similar to unit propagation in Boolean Satisfiability (SAT) solvers or domain propagation in Mixed Integer Programming (MIP) solvers, i.e., the hard constraints of the problem can be used to make decisions in the search for a solution. Both SAT and MIP solvers have been shown to rely on it to significantly improve their search. Improvements over S2V-DQN could be due to this extra built-in domain knowledge, rather than any improvements related to learning. For a fairer comparison, either this knowledge should be removed from ADP as an additional ablation study, or it should somehow be given to S2V-DQN as well. Without such a comparison, it is not clear that the improvements are really due to the new ideas like auto-deferring, diversity regularizer, etc.
- A comparison to Li, Chen, and Koltun, NeurIPS’18 is needed since they have shown strong results for MIS and they have made the code available online. Although their approach is supervised learning, it would still be useful to assess an RL approach’s performance relative to SL.
Additional comments:
- It is not clear what encourages the policy to defer decisions, rather than making all the {0,1} decisions for all variables in one step or a small number of steps. Does this behaviour of the policy arise naturally via training, or does some regularization need to be applied to ensure that the policy doesn’t prematurely fix all variables? For example, as a way to avoid/reduce variance in the reward signal, the policy may learn to fix all variables in just one step -- does this issue arise?
- The abstract says "The reported performance of our generic DRL scheme is also comparable with that of the state-of-the-art solvers specialized for MIS, e.g., ADP outperforms them for some graphs with millions of vertices." Can you please point out the specific results in the paper that this sentence is referring to?
- Comparison to CPLEX:  The paper mentions that “we observe that our algorithm outperforms the CPLEX solver on ER-(100, 200) and ER-(400, 500) datasets, while consuming a smaller amount of time”, and “It is remarkable to observe that ADP outperforms the CPLEX solver on both datasets under reasonably limited time.” Note that CPLEX not only optimizes the objective, but also proves a bound on the objective, while ADP only does the former. So this is not a fair comparison. A fairer comparison would be to set CPLEX hyperparameters to give higher priority to optimizing the objective and then measure the time CPLEX took to first reach a particular objective value rather than the time to “solve” an instance. It can be the case that a given objective value is achieved quickly but then proving a bound requires much longer. Also there is no mention of the optimality gap used as a stopping criterion for CPLEX.
- One potential advantage of making one decision per step is that the credit assignment problem may be simpler compared to making many decisions simultaneously. It would be insightful to explore this tradeoff in more detail.
- The acronym ADP is somewhat well-known in the optimization community as Approximate Dynamic Programming (http://adp.princeton.edu/), so it would be helpful to use a different one.