- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper aims to solve Quadratic Assignment Problem (QAP) which is fundamental and extremely difficult field in combinatorial optimization. The author proposed Sinkhorn-Reparameterized Primal-Dual Optimization (SRPD), a scalable framework for solving QAP. There are major two contributions:
-
The author reformulates QAP as a continuous optimization problem with integrality constraints and replace explicit projection with differential Sinkhorn operation so that enables unconstrained latent-space optimization with adaptive primal–dual updates.
-
Building on this formulation, the paper develops a GPU-parallel trajectory harvesting strategy that greedily decodes intermediate soft assignments across multiple optimization runs and retains the best feasible permutation, exploiting candidate solutions encountered throughout the optimization process.
Extensive experiments on QAPLIB, large-scale taiXXeYY instances, and graph isomorphism benchmarks establish the framework’s empirical effectiveness
Critical strengths
-
The paper provides a clear formulation of the QAP and develops a coherent optimization framework. The proposed Sinkhorn reparameterization offers an intuitive, differentiable alternative to explicit projection, enabling optimization in an unconstrained latent space. Its integration with primal–dual updates and trajectory harvesting further strengthens the framework’s computational practicality.
-
The paper presents a detailed theoretical analysis of the proposed framework, covering the properties of Sinkhorn reparameterization, bounds on greedy decoding errors, and sufficient conditions for exact penalization. Notably, the analysis explicitly accounts for a finite number of Sinkhorn iterations rather than assuming exact normalization, bringing the theoretical treatment into closer alignment with the practical implementation.
-
The experiments span standard QAPLIB benchmarks, large-scale taiXXeYY instances, and graph isomorphism problems. The proposed method substantially outperforms the projected primal–dual baseline in both solution quality and runtime. Results on larger instances further demonstrate its practical scalability, while optional 2-opt refinement yields additional gains in solution quality.
Critical weaknesses
-
Although the paper derives useful bounds for decoding errors and objective values, it remains unclear how these results support the adaptive optimization scheme used in practice. The exact-penalty analysis in Theorem 4.2 assumes fixed penalty coefficients of sufficient magnitude, yet the algorithm updates its dual variables adaptively without guaranteeing that the resulting values satisfy those assumptions. This mismatch is particularly evident in the experiments on larger taiXXeYY instances, where the dual variables are kept positive—a configuration outside the stated sufficient conditions. A further gap is the absence of a convergence analysis for the adaptive primal–dual procedure as a whole. The authors should therefore explain more precisely what the theoretical results imply for the implemented algorithm and where their applicability ends.
-
The substantial gains over the projected primal–dual baseline demonstrate the effectiveness of the overall framework, but leave the sources of those gains unresolved. The current evaluation provides limited evidence for distinguishing the impact of Sinkhorn reparameterization from the benefits of parallel multistart optimization and trajectory harvesting. A more informative assessment would vary these components in controlled ablation studies while holding the computational budget constant, allowing their respective contributions to be assessed. In addition, the stochastic optimization process calls for an evaluation across independent runs. Reporting the resulting variability alongside aggregate performance would provide stronger support for the reliability of the experimental findings.
Questions for authors
My main concern is the alignment between the theory and implementation.
3 comments
Reply to rebuttal
I have no further concerns, the author have addressed my questions.
Thank you for your positive feedback. We are glad that our response has addressed your concerns.
Thank you for highlighting the distinction between the theoretical guarantees and the implemented adaptive algorithm. We clarify the scope and applicability of each result below.
In summary, our theory provides recovery and objective guarantees for the actual finite-budget outputs, rather than convergence guarantees for the adaptive optimization trajectory. These results do not guarantee that the search encounters a near-optimal candidate; the effectiveness of the adaptive search itself is supported empirically.
Thank you for this suggestion.
We have further clarified this comparison in Sections 5.1 and 5.3 of the revised manuscript.
Thank you for highlighting the importance of evaluating variability across independent runs.
We have included the complete five-seed results in Appendix F of the revised manuscript.