Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling

Response to Weaknesses

We sincerely appreciate your insightful comments and your recognition of the novelty of our algorithm and the thoroughness of our numerical experiments. Below, we address your concerns about comparing runtime measurements across different implementations. **On the Comparison of Wall-Clock Time** We appreciate your thoughtful observation regarding the challenges of comparing wall-clock time across solvers implemented in different programming languages and optimized for distinct hardware platforms. As you correctly pointed out, solvers such as Gurobi and other domain-specific tools are typically designed for CPU execution and cannot utilize GPU parallelism. In contrast, PQQA leverages GPU-based parallel computation, one of its core strengths. Given these fundamental differences, achieving a perfectly fair comparison is inherently challenging. However, for solvers supporting GPU acceleration, including UL-based solvers and iSCO, we ensured uniform hardware configurations and consistent programming environments during our benchmarks to minimize variability due to differences in computational resources. Although implementation differences (e.g., programming languages, library optimizations) can introduce some variability, such effects are typically limited to constant factors. In contrast, the observed advantages of PQQA are more significant in order of magnitude and cannot be explained by implementation differences alone. For instance, **the results in updated Table 2 and the $10^{4} \times$ speedup demonstrated by PQQA over SA clearly highlight its scalability and efficiency**, stemming from its effective use of GPU acceleration. It is also worth highlighting that the PQQA implementation used in our experiments intentionally avoids problem-specific optimizations or fine-tuned acceleration techniques. This design choice underscores the fundamental strengths of PQQA as a general-purpose solver and highlights the potential for further runtime improvements through future optimizations. Finally, as shown in the revised Table 2, which now includes iSCO results, the scalability of PQQA for large-scale problems is even more evident. These results reinforce the significant contributions of PQQA in providing a scalable, efficient, and flexible solution for large-scale combinatorial optimization problems. We hope these clarifications address your concerns and demonstrate the robustness and scalability of PQQA. Considering these improvements and additional results, we kindly request that you reconsider your evaluation and score.

Response to Weaknesses (1/2)

We sincerely thank you for your detailed and thoughtful review. We greatly appreciate your recognition of PQQA's parallel GPU implementation. We believe leveraging GPU resources for CO problems is crucial for this work and valuable for the broader ICLR community. Below, we provide detailed responses to your comments and concerns. **Convergence Guarantees** We appreciate your inquiry regarding convergence guarantees. As noted, PQQA does not provide formal guarantees of convergence to a global optimum—**a limitation shared by heuristic/meta-heuristic and sampling-based methods, such as UL-based solvers [1, 2, 3], iSCO [4], and simulated annealing**. However, PQQA focuses on practical performance, leveraging GPU and gradient-based updates to explore the solution space efficiently. **Guarantee of Finding a Feasible Solution** Thank you for emphasizing this critical aspect. We acknowledge that PQQA may face challenges in solving problems with an exponential number of constraints due to the penalty-based approach, as described in Eq. (2) (Line 95). This limitation is shared by related methods, including UL-based solvers [1, 2, 3] and iSCO [4]. Specifically, penalty methods may fail to guarantee feasibility under poorly tuned parameters. Indeed, the limitations of this approach are explicitly noted in the conclusion of iSCO [4]. **To clarify this point, the revised version includes a Discussion on Limitations in Appendix F.** Despite these challenges, PQQA demonstrates significant advantages across various benchmarks, covering almost all benchmarks of UL-based solvers [1, 2, 3] and iSCO [4]. For instance, Table 1 illustrates that Gurobi struggles with large-scale ER-[9000-11000] problems, whereas PQQA achieves superior speed-quality trade-offs compared to both iSCO and other solvers. Additionally, PQQA's flexibility enables it to address non-linear cost functions and problem formulations without requiring reformulations, often necessary for solvers like Gurobi. Reformulations, such as introducing slack variables, can significantly increase problem complexity. Importantly, we do not position PQQA as a replacement for exact solvers like Gurobi. Instead, it is a complementary approach that excels in scenarios where heuristic or meta-heuristic methods are more effective. Both paradigms offer distinct advantages, and we believe that advancing both is essential for the sustained progress of the CO field. We hope this clarifies the role of meta-heuristic methods in CO research. In response to Reviewer CsaC's suggestion, we conducted additional experiments on TSP instances without using the 2-opt algorithm. The results are summarized in the table below: | Instance | TSP50 | TSP100 | TSP200 | |------------|---------------|---------------|-----------------| | ApR | 1.011 ± 0.143 | 1.016 ± 0.121 | 1.0415 ± 0.003 | | Violation | 0 ± 0 | 0 ± 0 | 0 ± 0 | The ApR measures performance relative to Concorde, an OR solver. Values close to 1.00 demonstrate PQQA's strong alignment with optimal solutions. These results show that PQQA consistently finds feasible solutions in all tested instances, fully satisfying the given constraints. Furthermore, the ApR values indicate a high alignment with optimal solutions. If additional details about these experiments or further benchmark results are required, we would be happy to discuss them. We recognize the importance of further exploring PQQA's capabilities for addressing problems with complex constraints. While this represents an important avenue for future work, we hope that the demonstrated superiority of PQQA over UL-based solvers [1, 2, 3] and iSCO [4] in solving large-scale problems with a moderate number of constraints, as detailed in the main text, is recognized as a significant contribution to the field. - [1] Haoyu Wang and Pan Li, Unsupervised Learning for Combinatorial Optimization Needs Meta Learning, ICLR2024 - [2] Haoyu Wang et al., Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation, NeurIPS2022 - [3] Schuetz Martin JA, J. Kyle Brubaker, and Helmut G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nature Machine Intelligence 4.4 (2022): 367-377 - [4] Sun Haoran et al., Revisiting Sampling for Combinatorial Optimization, ICML2023

Response to Weaknesses (2/2)

**Performance on SATLIB** We appreciate your comment regarding the runtime observed in the SATLIB results. These differences arise due to the nature and scale of the SATLIB benchmarks. SATLIB instances are relatively small in scale compared to the other instances analyzed. PQQA utilizes gradient-based optimization algorithms, such as AdamW, which are highly effective for solving large-scale problems by accelerating convergence and enabling simultaneous updates to multiple variables. However, these advantages become less pronounced when applied to smaller instances. Our primary goal remains the development of a scalable, general-purpose solver to address large-scale problems. As shown in Table 1 and the revised Table 2 (which now includes results for iSCO), PQQA exhibits significant advantages on large-scale instances, such as ER-[9000-11000], where Gurobi cannot solve the problem due to computational limitations. **Benchmarking on MIPLIB 2017** We appreciate your suggestion to use MIPLIB 2017 as a potential benchmark. While datasets like MIPLIB 2017 are valuable for evaluating solvers on mixed-integer programming problems, our primary focus was to compare PQQA with UL-based solvers [1–3] and iSOC [4] using their benchmarks. These benchmarks enabled us to effectively demonstrate the scalability and speed-quality trade-offs of PQQA. Evaluating PQQA on MIPLIB 2017 is an excellent suggestion we plan to address in our future work. **Why Not Solve the Relaxed Linear Programming Problem Directly?** Solving the relaxed linear programming problem directly is feasible only when both the cost function and the constraints are linear. Although LP relaxations can yield optimal solutions for some discrete issues with specific structures, such as bipartite graphs [5], they frequently produce half-integral solutions, 1/2 [6], that are challenging to round into valid discrete solutions. Furthermore, PQQA incorporates an $α$-entropy term, converting the problem into one characterized by a quadratic cost function. This non-linearity makes standard LP solvers inapplicable. - [5] Integral boundary points of convex polyhedra. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pages 49–76, 2010. - [6] George L Nemhauser and Leslie E Trotter Jr. Properties of vertex packing and independence system polyhedra. Mathematical programming, 6(1):48–61, 1974 Again, We thank you for your thoughtful feedback and the opportunity to improve our manuscript. The additional experiments, clarifications, and future directions outlined above aim to address your concerns comprehensively. We hope these contributions, particularly the parallel implementation of PQQA on GPUs and its demonstrated scalability to large-scale CO problems, are recognized as significant advancements in the field. We respectfully request that you reconsider your evaluation in light of these responses.

Response to Weaknesses and Additional Experiments on TSP Instances

We sincerely thank the reviewer for their insightful comments and for recognizing the novelty and numerical contributions of our work. Below, we respond to each of the points raised in detail. **Simple Constraints in Benchmarks** We appreciate your valuable feedback. We acknowledge that PQQA may encounter challenges when solving problems involving an exponential number of constraints. However, we consider that this issue originates not from the continuous relaxation itself but rather from the penalty method, as described in Eq. (2) (Line 95). As explained later, no constraint violations resulting from continuous relaxation were observed in any numerical experiments presented in the main text and in the additional experiments on TSP instances. The penalty method is employed in UL-based solvers [1, 2, 3] and iSCO [4], which also encounter constraint violation issues due to their reliance on penalty-based exploration. Indeed, the limitations of this approach are explicitly noted in the conclusion of iSCO [4]. Therefore, these challenges are common to both UL-based and sampling-based solvers, including PQQA. **To clarify this point, the revised version includes a Discussion on Limitations in Appendix F.** As you pointed out, benchmark problems for UL-based solvers [1, 2, 3] and iSCO [4] primarily address large-scale problems with moderate constraints rather than those characterized by an exponentially large number of constraints. Our numerical experiments extensively cover these benchmarks, demonstrating that PQQA surpasses existing methods regarding the speed-quality trade-off. Furthermore, these benchmarks underscore PQQA's capability to solve intractable instances for commercial solvers like Gurobi. Note that **iSCO's performance on the TSP is largely attributable to its integration with the 2-opt algorithm, as described in Section 5.3: Traveling Salesman Problem of [4].** By incorporating the 2-opt algorithm, iSCO explores constraint-satisfying regions. However, as mentioned in the Introduction in the main text, this approach deviates from our primary goal of creating a general-purpose solver for scenarios where effective greedy algorithms are unavailable. iSCO’s reliance on an existing greedy heuristic fundamentally distinguishes its approach from our intended contribution. Moreover, the specifics of iSCO's integration with the 2-opt algorithm are not indicated in [4], making a fair comparison with PQQA challenging. A meaningful comparison between PQQA and iSCO [4] on TSP instances would necessitate excluding the 2-opt component from iSCO, making this an essential direction for future research. - [1] Haoyu Wang and Pan Li, Unsupervised Learning for Combinatorial Optimization Needs Meta Learning, ICLR2024 - [2] Haoyu Wang et al., Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation, NeurIPS2022 - [3] Schuetz Martin JA, J. Kyle Brubaker, and Helmut G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nature Machine Intelligence 4.4 (2022): 367-377 - [4] Sun Haoran et al., Revisiting Sampling for Combinatorial Optimization, ICML2023 **Additional Experiment on TSP Instances** Based on your valuable suggestion, we conducted additional experiments to evaluate the performance of PQQA on TSP instances. Specifically, we evaluated PQQA on TSP50, TSP100, and TSP200 instances without applying the 2-opt algorithm, as detailed below. | Instance | TSP50 | TSP100 | TSP200 | |------------|---------------|---------------|-----------------| | ApR | 1.011 ± 0.143 | 1.016 ± 0.121 | 1.0415 ± 0.003 | | Violation | 0 ± 0 | 0 ± 0 | 0 ± 0 | The ApR metric is defined relative to the results of Concorde, a well-established OR solver. An ApR value approaching $1.00$ signifies performance closely aligned with Concorde's results. If further details about the experiments are required or additional benchmark tests are requested, we are open to discussing them. The results showed that PQQA successfully found feasible solutions in all tested instances, fully satisfying the given constraints. Additionally, the results report an ApR close to 1.00. We acknowledge the importance of thoroughly exploring PQQA's potential in addressing these problems with complex constraints and view this as an important future direction. Nevertheless, we hope the demonstrated superiority of PQQA over UL-based solvers, including iSCO, in solving large-scale problems with a moderate number of constraints, as discussed in the main text, is recognized as a significant contribution to the field.

Response to Questions

In this comment, we will answer your question. **Regarding Binary Solutions in PQQA** Thank you for pointing out the need for clarification regarding binary solutions. In the revised manuscript (Lines 297–299), we explicitly note that for all benchmark CO problems, the soft solutions at the end of the training process naturally converge to binary values (0 or 1) within the 32-bit floating-point precision limit when using PyTorch on a GPU. Similarly, no issues with non-binary solutions were observed in the additional TSP experiments. This result demonstrates the robustness of PQQA in consistently achieving discrete solutions. Additionally, by annealing the parameter $\gamma$ while monitoring the $\alpha$-entropy term, it is possible to obtain discrete solutions by halting the annealing process when $s(\sigma(w)) \approx 0$. **Regarding Solution Feasibility** We greatly appreciate your thoughtful comment on the feasibility of solutions. Our numerical experiments revealed no constraint violations when the penalty parameters were set according to values reported in previous studies [1, 2, 3, 4]. These results have been incorporated into the revised manuscript, specifically in lines 299–300. Furthermore, additional TSP experiments demonstrate that feasible solutions can be achieved by selecting large penalty values, thereby eliminating the need for precise parameter tuning. **Regarding the Impact of LP Relaxation Strength** Although the precise meaning of "strength of LP relaxation" remains unclear, we interpret it as a measure of the quality of relaxation influence solutions. By employing the continuous relaxation strategy, our method enables simultaneous updates of multiple variables via gradients, in contrast to simulated Annealing, which updates variables one at a time, and iSCO, which updates a subset of variables determined by its Path Auxiliary Sampler (PAS) parameter [4]. This feature dramatically enhances scalability for high-dimensional problems, as shown in Tables 1 and 2. Additionally, one can obtain discrete solutions by annealing the parameter $\gamma$ while monitoring the $\alpha$-entropy term. **Regarding the Absence of iSCO in Table 2** Thank you for pointing out this omission. We have now included the iSCO results in Table 2 of the revised manuscript. Similar to the findings in Table 1, the results show that as the problem size increases, PQQA consistently outperforms iSCO regarding speed-quality trade-off. **Regarding iSCO's Performance on Maximum Independent Set vs. Max Clique** We appreciate your observation regarding iSCO’s varying performance across these problems. While we currently lack a definitive explanation for iSCO's slower performance on Max Clique, this behavior could be attributed to the structural properties of the graphs or the interaction between iSCO’s hyperparameters and the problem's characteristics. **Minor Remarks** Thank you for identifying the inconsistencies in runtime evaluation and the incorrect references. The revised manuscript has addressed these issues to enhance clarity and consistency. We believe that the clarifications above address your concerns and further strengthen our contribution to the work. Specifically, adding iSCO results in revised Table 2 provides strong evidence of PQQA's scalability to large-scale problems. We respectfully request that you reconsider the score provided for our submission in light of these improvements.

Response to Questions

We sincerely thank you for your positive and constructive feedback. We are particularly grateful for your recognition of the clarity of our problem formulation, methodology, and numerical experiments. Below, we address the specific questions you raised to provide further clarity. **Clarification of ApR values exceeding 1 (Table 1)** As described in Line 301 (*Evaluation Metric*), ApR is computed relative to the best-effort results for problems where the optimal solution cannot be guaranteed. Specifically, Table 1 uses baseline values from KaMIS, the state-of-the-art MIS solver and winner of the PACE 2019 challenge. Therefore, an ApR value greater than 1 signifies that the solver outperforms KaMIS. Notably, iSCO has demonstrated superior performance to KaMIS on ER-[700-800] and ER-[9000-11000], attracting significant attention. However, PQQA significantly outperforms iSCO in both instances. Furthermore, the updated results in Table 2, which include those of iSCO, further validate this performance advantage. **Clarification of Runtime in SATLIB Results (Table 1)** We appreciate your comment regarding the runtime differences in the SATLIB results. This discrepancy arises from the nature and scale of the SATLIB benchmarks. SATLIB instances are relatively small in scale compared to the other instances. PQQA employs gradient-based optimization algorithms, such as AdamW, which are highly effective for large-scale problems by accelerating convergence and simultaneously updating multiple variables. However, these advantages diminish when applied to smaller instances. Fine-tuning learning rates and other hyperparameters could enable PQQA to achieve runtime and performance comparable to iSCO on SATLIB instances. However, such extensive tuning lies beyond the scope of this study and remains an important future work. Note that our primary objective is to develop a scalable, general-purpose solver for large-scale CO problems, where commercial solvers like Gurobi become impractical. SATLIB was included primarily as a benchmarking dataset due to its use in prior studies, such as iSCO. However, we consider that its relevance in demonstrating the advantages of our approach is limited, particularly since commercial solvers like Gurobi can easily handle such small-scale instances. **Correction of table references** We appreciate your attention to this detail. The erroneous reference to "Table 5.1" in Line 314 has been corrected to "Table 1" in the updated manuscript. **Clarification of "parameters" in Line 60** Thank you for highlighting the ambiguity surrounding the term *parameters*. In the revised manuscript, we have clarified that *parameters* specifically refers to the learnable parameters within the UL-based solvers. We have addressed the reviewer's concerns about ApR values exceeding 1 and elaborated on the scalability advantages of PQQA, especially for large-scale problems. The updated Table 2 highlights the superior performance of our method in comparison to iSCO. We kindly request that you reconsider the scores for our submission, as we believe these clarifications and improvements strengthen the contribution and robustness of our work.