Efficient Combinatorial Optimization via Heat Diffusion

Summary

This work solves combinatorial optimization problems using the gradient method by transforming the discrete problem into a continuous problem. Under the invariant of the optimal solution, the authors transformed the hard continuous problem into an easier problem by changing the objective function using a heating equation and improved the calculation process of the gradient which makes the problem more tractable.

Strengths

1. The authors established the basic theory for the method proposed in the paper. 2. Extensive experients have been conducted and clearly figures have been presented.

Weaknesses

1. The motivation of this paper seems to improve the scope of the search-based combinatorial optimization solver, but the proposed method is to change the objective function to improve the efficiency of the gradient method. The method seems a little bit irrelevant to the original motivation of the paper. 2. The paper does not fully discuss the combinatorial optimization problem with constraints ( only do some experiments on the minimum vertex cover problem ), and the description of the violation of constraints is not sufficient.

Questions

1. The discussion of equations (8) to (9) is a little confusing. Could you please explain how to calculate the projection map in equation(9)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

1. The method does not fully discuss the combinatorial problem with constraints which is the main part of the combinatorial problem.

Summary

This paper proposes the Heat Diffusion Optimization (HeO) method, which leverages thermodynamic principles to enhance combinatorial optimization (CO) problems. Specifically, it integrates heat diffusion equations into gradient-based optimization to improve efficiency and help escape local minima.

Strengths

1. The paper is generally well-written, with a good balance of examples, explanations, and discussions. 2. The idea of using heat diffusion to propagate information across the solution space is novel and interesting for solving CO problems. 3. The proposed method is validated on different types of CO problems with varying scales.

Weaknesses

1. While the work introduces a new approach for gradient-based combinatorial optimization, it inherits the limitations of gradient-based methods. It may struggle with complex CO problems, such as routing problems, as discussed by the authors. 2. The paper could benefit from a deeper theoretical and empirical analysis of the HeO algorithm. For example, a detailed analysis of the convergence properties and computational complexity of the algorithm is needed. Also, summarizing and providing recommendations on parameter sensitivity and selection would be valuable. 3. The paper demonstrates improved performance over several classic solvers like MDGE, SA, and LQA. However, it does not provide enough evidence or discuss the potential of HeO to achieve state-of-the-art performance on the studied CO problems. 4. The submission seems to be not incomplete as there lack of appendices or supplementary materials that verify the soundness of the theorems presented in Section 3. Overall, I feel like this paper is proposing a very interesting new method for CO with potential. It would benefit greatly from a major revision that includes more details, proofs, and broader experiments.

Questions

None.

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

No concerns.

Summary

This paper aims to improve the efficiency of existing combinatorial optimization methods via heat diffusion. The author have made a thorough analysis over the existing problems and propose the heat diffusion method HOE for general combinatorial optimization problems. The empirical evaluation verifies its advantage over various combinatorial optimization problems.

Strengths

1. The authors make a comprehensive analysis of the problems of existing methods, the proposed method is quite novel, with enough insights to the future research on the combinatorial optimization. 2. The proposed method is both theoretically supported and empirically justified. 3. The empirical evaluation spans a various of combinatorial optimization problems, and thorough analyses are presented. 4. The whole paper is well-written

Weaknesses

1. In section 2, the analyses are only focused on the methods doing the gradient descent over the relaxed variables. It is unclear to me how the conclusions are generalized to the method like large neighborhood search, variable neighborhood search and path auxiliary sampling (as mentioned in the introduction part).

Questions

See the weaknesses part

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Summary

The paper presents a novel framework for solving combinatorial optimization problems using a concept termed "Heat diffusion optimization (HeO)." The approach diverges from traditional methods by utilizing heat diffusion to enhance information propagation within the solution space, allowing for more efficient problem-solving.

Strengths

1. The introduction of heat diffusion as a mechanism to aid in combinatorial optimization is novel and thoughtfully developed. 2. Comprehensive experiments across different optimization problems illustrate the method's effectiveness and superiority over traditional approaches. 3. The methodology is tested on a wide range of problems, showing its versatility and potential for broader application in real-world scenarios.

Weaknesses

1. The paper lacks a detailed discussion on the scalability of the method, especially in very large-dimensional spaces, which are common in real-world applications. 2. More baselines are needed.

Questions

1. On Page 4, Line 129, the method for determining the value of K in the multilinear polynomial is not clear. Could you elaborate on how K is selected in different scenarios? 2. Figure 2 shows that the energy does not monotonically decrease during optimization. Why the energy in Fig. 2 is not monotonically decreased? 3. What are the algorithmic complexity and computational time of the proposed heat diffusion optimization method? 4. Is it possible to apply your heat diffusion framework to other types of combinatorial optimization problems, such as those found in operational research?

Rating

6

Confidence

5

Soundness

3

Presentation

2

Contribution

3

Limitations

1. On Page 3, line 105, the definitions of \Delta_\theta and the function u are not given. 2. The ability of global search is not theoretically analyzed.