Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
The cutting plane method is an augmentative constrained optimization procedure that is often used with continuous-domain optimization techniques such as linear and convex programs. We investigate the viability of a similar idea within message passing -for integral solutions in the context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP), we propose a factor-graph based on HeldKarp formulation, with an exponential number of constraint factors, each of which has an exponential but sparse tabular form. 2) For graph-partitioning (a.k.a. community mining) using modularity optimization, we introduce a binary variable model with a large number of constraints that enforce formation of cliques. In both cases we are able to derive simple message updates that lead to competitive solutions on benchmark instances. In particular for TSP we are able to find nearoptimal solutions in the time that empirically grows with N 3 , demonstrating that augmentation is practical and efficient.
The authors studied how to solve NP-hard TSP and graph partition problem as an inference on a graphical model. They first showed how to design a graphical model for each problem. The corresponding graphs are cyclic and the inference problems are NP hard. Because of the success of the belief propagation (BP) method, which provides a good approximate inference with cheap computational cost in error correction codes and related problems, the authors applied min-sum BP for TSP and graph partition problem.Most part of the paper is clearly written. The approach is interesting, but this is an empirical study. My recommendation is positive but not strong.The paper has two main claims. One is how to design the graphical models and apply BP algorithm. Naïve BP may not work well, and the authors combined some tricks. The other point is to show the numerical results of min-sum. The authors claim the results are comparable to state-of-art methods but the computations cost is small.First point: The graphical model representation of TSP is straightforward. That for the graph partition is realized via a stochastic approach, which is not so difficult. The important part is how to apply BP successfully. The graphs have a lot of cycles and naïve min-sum BP may not work well. For each problem, they combined some approaches: the messages are normalized, and the subtour/clique constraints are treated carefully. They also combined and decimation for TSP and damping for both. These are heuristic and we would like to know if they really avoided local maxima and how often the algorithm converges to the optimal points.Second point: For graphs with many cycles, min-sum BP generally does not provide the optimal solution. We confirm this fact from numerical results of the paper. Although the authors claim the cheap computational cost and the good quality of the solutions, it is difficult to convince non-specialists to use this approach.Overall comment: The authors have shown numerical results for known data. What people want to know is what will happen for new unknown data. Some theoretical studies of the characteristics should be shown. For what kind of data, this method is better than other methods, and how the computational cost grows according to the size of the problem (the discussion in section 4 is not sufficient). Finally, I have one question. The graph partitioning method uses a randomized method. How the results are influenced with it?