Controlling Continuous Relaxation for Combinatorial Optimization

Reply to Reviewer J6G3

Thank you for recognizing the contribution of our paper, and we appreciate your decision to raise the score. Based on your insightful comments, we conducted additional experiments on several TSP problems from the TSPLIB dataset (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/). Below, we present the results demonstrating the $p$-dependency of the solutions. | Instance | ApR ($p=2$) | ApR ($p=4$) | ApR ($p=6$) | ApR ($p=8$) | ApR (PI) | Optimum | |------------|----------------------|----------------------|----------------------|----------------------|---------------------|---------| | burma14 | 0.91 ± 0.08 | 0.98 ± 0.10 | 0.97 ± 0.14 | 0.99 ± 0.06 | 0.736 ± 1.21 | 3,323 | | ulysses22 | 0.89 ± 0.03 | 0.92 ± 0.02 | 0.88 ± 0.07 | 0.89 ± 0.05 | -- | 7,013 | | st70 | 0.96 ± 0.01 | 0.85 ± 0.03 | 0.88 ± 0.04 | 0.80 ± 0.02 | -- | 675 | | gr96 | 0.81 ± 0.05 | 0.82 ± 0.03 | 0.90 ± 0.05 | 0.86 ± 0.05 | -- | 5,5209 | In these experiments, we calculated the ApR as the ratio of the optimal value to the CRA result, with the ApR representing the average and standard deviation over 3 seeds. The "--" in PI-GNN indicates that most variables are continuous values and that the maximum epoch did not obtain a solution satisfying the constraint. We used the same GNN and optimizer as in our experiments of the main text. The table shows that the CRA approach found solutions with an ApR exceeding 0.9 across various instances. Notably, for the "burma14" problem, our method found the global optimal solution, 3,323, several times. However, the optimal $p$ value may vary depending on the specific GNN architecture and problem structure, which suggests that a more comprehensive ablation study would be beneficial in future work. We will include these results and additional problem instances in the appendix or main text of the revised version. We hope that these enhancements, which demonstrate the broader applicability and robustness of our approach, will further highlight the contribution of our work. We would greatly appreciate it if these improvements could be taken into consideration during your final evaluation.

Thank you for the efforts. Response to Authors

### Response to Authors: - The experiments are evaluated on RRG and ER. The run-time of the proposed method scales only with the size of the graph, which I find impressive. Your response "runtime remains nearly constant as graph order and density increase" is not accurate as it is clear that the run-time is ~4X more when $n$ increased. In subsequent versions of the paper, I highly recommend including KaMIS and ILP solvers in these tables, as they are both known to scale with density, not just graph size. However, first, I find that the Apr in these results are low, and KaMIS should have been used to examine the solution quality. Second, in general, I still think that the proposed method is under-evaluated. The authors should consider using several random graph generators from NetWorkX, especially since it is a dataless method. - Discussing the intuition of over-parameterization to smoothen the landscape is acknowledged. I highly recommend that the authors include their response to this comment in the main body of the paper. - I acknowledge the additional experiments for MIS. The method clearly outperforms DIFUSCO while requiring no training data. However, the proposed approach still underperforms when compared to iSCO, a training-data-free sampling method where no GNNs are needed. However, I think that iSCO, while reporting significant results, is sensitive to the choice of the sampler and hyper-parameters. So overall, the CRA results in this table are fair. - **Question**: Why are the CRA MIS size results in the "Numerical Experiments" global response competitive, but the results in the attached PDF are not (way below 1)? - Larger graphs sizes (nodes) or harder instances can be any graph where ILPs and heuristics struggle in terms of either run-time or solution quality. For MIS, the authors can try mid-density (with respect to the complete graph) GNM graphs or ER (with $p > 0.4$) graphs. - Overall, I appreciate the dataless training approach and the theoretical support of the proposed method, and I encourage the authors to further investigate this direction. However, I feel that the paper could benefit from (i) a major revision in terms of writing (e.g., polishing the arguments about the non-convexity and rounding issues of general continuous relaxations of COPs) and (ii) a more comprehensive evaluation and explanation of the results. Therefore, I will only increase my score to 4.

Reply to Reviewer qMFs

Thank you for your thoughtful feedback and continued engagement with our work. We apologize for any confusion caused by our previous explanation in the global (unified) response. The iSCO results presented in the *"Numerical Experiments"* of our global response are from the paper by Sun et al. (ICML 2023) [1]. We apologize for any inconvenience and kindly request that you review these results in the global response, where we demonstrated CRA's performance that is comparable to or slightly below the SOTA iSCO method. As Reviewer BuGW noted, **"I acknowledge the additional experiments for MIS. The method clearly outperforms DIFUSCO while requiring no training data. However, the proposed approach still underperforms when compared to iSCO, a training-data-free sampling method where no GNNs are needed. However, I think that iSCO, while reporting significant results, is sensitive to the choice of the sampler and hyper-parameters. So overall, the CRA results in this table are fair."** This recognition of our comparison with iSCO supports the fairness of our results. It is also important to highlight that iSCO [1] uses a first-order Taylor expansion of the objective function to approximate the essential $\Delta(x)$ term in the discrete Langevin dynamics, enabling efficient parallel processing on GPUs. However, this method may experience performance degradation when the first-order approximation is inadequate. The iSCO paper primarily tests problems where the approximation is valid or nearly valid, which should be considered, particularly in black-box optimization with complex surrogate models. In contrast, our method does not rely on such approximations and can be applied as long as the gradient of the objective function, $\hat{l}(p; C, \lambda)$, is accessible. Indeed, Wang et al. (2022) [2] demonstrated the superiority of UL-based solvers in black-box optimization using complex surrogates with GNNs, leveraging the flexibility of UL-based solvers. Additionally, as Reviewer BuGW pointed out, **"I believe that over-parameterization and benefiting from the structure of a GNN are what makes the contribution valuable. To me, the benefit here is similar, in spirit, to the topic of lifting in optimization."** This suggests that solution performance could further improve depending on the GNN's over-parameterization and architecture. We believe that the statement in the *"Main Contribution and Novelty"* section of the Global Response, "Our primary contribution is the introduction of CRA to overcome the limitations of UL-based solvers (Type II), as highlighted by Wang et al. (ICLR 2023)," is crucial to realizing these future possibilities. To further strengthen our paper, we plan to include more detailed comparisons with iSCO in the revised version and additional discussions and results. We respectfully request that you reconsider your score based on these efforts. - [1] Sun et al. Revisiting Sampling for Combinatorial Optimization. ICML 2023. - [2] Wang et al. Unsupervised learning for combinatorial optimization with principled objective relaxation. NeurIPS 2022.

Reply to qMFs

Thank you very much for your continued engagement and for addressing our responses. We greatly appreciate your acknowledgment of CRA's generalizability and the significance of our work. > Firstly, I'm confused why authors feel there is any essential difference between "a first-order Taylor expansion of the objective function" used in iSCO and the "gradient of the objective function" used in CRA. We apologize for our unclear response. There might be a need for clarification regarding the iSCO [1]. We understand that **iSCO, which employs discrete Langevin Monte Carlo, is not a gradient descent algorithm based on continuous relaxation.** Instead, it generalizes Langevin dynamics (gradient flow) from continuous probability distributions to discrete ones. iSCO changes the temperature while numerically simulating the Equation from Theorem 3.1, characterized by Equation (23) on Sun 2022 [2]. Executing discrete Langevin dynamics without approximation requires calculating the difference between the objective functions $f(y)$ and $f(x)$ for the next transition candidates, as mentioned in Section 3.2.1 of Sun 2023 [1]. This approach is noted to be computationally intensive, as Sun et al. themselves acknowledge in Section 3.2.1. **The need to compute the difference between objective values rather than gradients indicates that iSCO is not based on continuous relaxation**. Although they approximate this difference with a Taylor expansion to expedite the simulation, it remains unclear how effective this approximation is for more complex problems and how to related to our method. > Then it leads to my second question. Clearly, iSCO owns more parameters than CRA when the graph size is even larger, then why does CRA outperform iSCO on large instances if the over-parameterization is its advantage against iSCO? My personal answer here is that iSCO is optimized on a larger parameter space and it converges slowly on large instances. As explained above, **iSCO uses the gradient of the objective function to approximate and efficiently simulate original discrete Langevin dynamics without using continuous relaxation**. On the other hand, since CRA uses continuous relaxation, it is easy to implement gradient descent, and optimizers with good convergence properties, such as AdamW, can be used. Indeed, we used AdamW in our numerical experiments. Also, as reviewer BuGW pointed out, over-parameterizing the decision variables using GNNs may smooth the loss landscape, making it more suitable for optimization and speeding up the convergence speed. However, it is difficult to investigate this hypothesis at present theoretically, and we consider that a more detailed investigation is future work. Additionally, it is crucial to investigate iSCO's implementation details, including its specific code-level parallelization methods. Unfortunately, as the iSCO code has yet to be shared, it has been challenging to delve into these details during the discussion period. In the revised version, we will add these differences between iSCO and CRA to the related work. > I note that all the theoretical analyses are on the output parameters $p_{i}$, isn't this type of analyses more related to gradient-based simulated annealing methods whose parameters are exactly $p_{i}$ here? > I do question the significance of this work on the Type II solvers. Our analysis is a theoretical analysis of the output parameters $p_{i}$. As you point out, there is an indirect relationship with gradient-based simulated annealing for $p_{i}$, but gradient-based simulated annealing is a method that performs Langevin Monte Carlo while lowering the temperature, and our method is a gradient descent method that controls the term $\Phi(p)$ that controls the continuity and discreteness. **Also, the method of simply performing continuous relaxation and gradient-based simulated annealing for $p_{i}$ cannot guarantee the original CO problems because they have the rounding issue, as pointed out in our main text.** We observed superior results compared to DIFUSCO for larger instances. As a heuristic approach, obtaining good solutions for problems too large for an exact solution method like Gurobi is vital. Also, as Reviewer BuGW pointed out, a more comprehensive comparison is needed between CRA and iSCO, including the setting of hyperparameters. We think that investigating which method is superior in a more quantitative way is future work (While we intended to conduct a detailed comparison with iSCO on larger problems such as d-regular random graphs during the rebuttal period, the unavailability of the iSCO code prevented us from completing this within the time limit). Considering these points, we would sincerely appreciate it if you could provide a final evaluation. - [1] Sun et al. Revisiting Sampling for Combinatorial Optimization. ICML 2023. - [2] Sun et al. Discrete langevin samplers via wasserstein gradient flow. AISTATS 2023.