{"id":"9f72e7cf-ae5e-4da4-ab3d-a8d57394b8c4","arxiv_id":"1908.04522","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A proximal DC algorithm on a rank-constrained DNN reformulation solves most QAPLIB instances to optimality and gives bounds within a few percent on the rest.","lead":"This paper reformulates the quadratic assignment problem as a rank-constrained doubly nonnegative program and solves it with a proximal difference-of-convex algorithm. The method finds optimal or near-optimal solutions for most QAPLIB instances up to dimension 60, often in minutes but sometimes in hours.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5's rank-one feasibility threshold is not established: the dual bound η is not shown independent of ρ, and Eq. (22) uses I+W_k while Eqs. (23)/(27) use I−W_k.","rationale":"The reader's weakest assumption concerns the exact-penalty equivalence in Proposition 2 and the norm ambiguity in dist(Y,R) = ||Y||_* − ||Y||_2. That is a genuine gap: the equality is false in the Frobenius norm, and the calmness of Γ is assumed rather than verified. However, Proposition 2 is not used in the convergence and feasibility theorems; it only motivates the penalized problem. The more load-bearing gap for the abstract's stated theoretical claim is Proposition 5, which directly underpins 'the generated sequence ... is feasible to the rank constrained DNN problem.' The proof's boundedness step for dual variables is not shown uniform in ρ, and the sign inconsistency between (22) and (23)/(27) compounds the issue. This does not refute the empirical results, which are reported in detail and include feasible permutations with small gaps; it does mean the theoretical guarantee of rank-one feasibility is currently unproven. Since this is a proof gap that can likely be repaired, the CONDITIONAL verdict from the reader remains appropriate; no change to the verdict is needed.","tokens_in":23110,"tokens_out":32997,"duration_ms":324162,"concrete_test":"Derive the dual of the proximal subproblem (20) directly from its Lagrangian. If the quadratic term in the dual must contain C + ρ(I − W_k), then Eq. (22) as printed is a sign error. Then, on a small instance such as nug12, run Algorithm 1 (or just solve the dual (22) for the true sign) for ρ = 10, 100, 1000 and compute m(ρ) = max_k λ1(−C − A^*y_k − Z_k). If m(ρ) grows linearly in ρ, Proposition 5's proof needs a new uniform-bound argument; if m(ρ) is bounded, the theorem likely survives with a minor correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's theoretical claim that the generated sequence is feasible for the rank-constrained DNN problem rests on Proposition 5, which asserts that for ρ sufficiently large, rank(Y_{k+1}) ≤ 1 eventually. The proof's key step is the assertion that there exists a finite constant η, independent of the penalty parameter, such that λ1(−C − A^*y_{k+1} − Z_{k+1}) ≤ η for all large k, justified by boundedness of the dual level set from Assumption 2. This step is not justified. For a fixed ρ, Assumption 2 gives bounded dual optimal sets, but the bound generally depends on ρ because the dual objective (22) contains the data term C + ρ(I + W_k). A simple analogue is the dual of min_x (1/2)||x||^2 + ρa^T x subject to x = 0, whose unique dual solution is y = −ρa; the dual bound is O(ρ). The paper gives no argument that the corresponding η is uniform in ρ. If η = O(ρ), the condition ρ > η + ζ/σ is unsatisfiable for large ρ, and the chain leading to λ2(S_{k+1}) < 0 and rank(Y_{k+1}) ≤ 1 collapses. There is also a concrete sign inconsistency: Eq. (22) writes C + ρ(I + W_k), while Eq. (23) and the KKT system (27) write C + ρ(I − W_k); these cannot both be correct. Thus the rank-one feasibility guarantee in the abstract is not proven as written, independent of the numerical successes.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reformulates the quadratic assignment problem (QAP) as an equivalent rank-constrained doubly nonnegative (DNN) problem, with analogous reformulations for the standard quadratic problem and the minimum-cut graph tri-partitioning problem. It then proposes a proximal difference-of-convex (DC) algorithm whose subproblems are solved by a semi-proximal augmented Lagrangian method, establishes convergence to stationary points of a penalized DC problem, and claims that for sufficiently large penalty the iterates eventually satisfy the rank-one constraint and are feasible for the rank-constrained DNN problem. Numerical experiments on 107 QAPLIB and 'dre' instances are reported, finding exact optimal values for 69 instances and feasible solutions within 4% for 32 additional instances.","tokens_in":23540,"tokens_out":9179,"duration_ms":92678,"significance":"If the theoretical claims hold, the paper offers a principled DC-penalty route to the QAP that combines an exact rank-constrained DNN reformulation with an implementable semi-proximal DCA and the mature SDPNAL+ solver. The equivalence theorems in Sections 2 and 3 are elementary and correct, and the numerical study is substantial: 107 instances with 69 solved exactly is a useful empirical result. The convergence-to-stationarity results follow from standard DC and Kurdyka-\\L{}ojasiewicz machinery. However, the headline theoretical assertion that the generated sequence is eventually feasible for the rank-constrained DNN problem rests on Proposition 5, whose proof contains a uniformity gap and a sign inconsistency; the exact-penalty Proposition 2 also relies on an unverified calmness condition and an unstated norm in the distance identity. These issues do not invalidate the numerical evidence, but they mean the central feasibility guarantee is not established as written.","major_comments":[{"comment":"The proof of eventual rank-one feasibility asserts that there is a finite constant η, independent of the penalty parameter ρ, such that λ1(−C−A^*y_{k+1}−Z_{k+1}) ≤ η for all large k. This is justified only by boundedness of the dual level set from Assumption 2, but the dual objective in Eq. (22) contains the data term C + ρ(I + W_k). For a fixed ρ, Assumption 2 bounds the dual optimal set, yet the bound can depend on ρ; no argument is given for uniformity in ρ. Consequently the condition ρ > η + ζ/σ may be unsatisfiable when η grows with ρ, and the chain leading to λ2(S_{k+1}) < 0 and rank(Y_{k+1}) ≤ 1 collapses. A simple analogue is the dual of min_x (1/2)||x||^2 + ρ a^T x subject to x = 0, whose unique dual solution is y = −ρa; there the dual bound is O(ρ). The authors should either prove a uniform bound exploiting the specific structure of the QAP constraints or weaken the claim in the abstract and Proposition 5.","section":"Section 4, Proposition 5, Eqs. (28)-(29)"},{"comment":"The same subproblem (20) is described inconsistently: the majorant objective in Eq. (21) has linear term C − ρW_k, the dual problem in Eq. (22) writes C + ρ(I + W_k), and the primal recovery formula (23) and the KKT system (27) write C + ρ(I − W_k). These expressions differ by 2ρW_k, so at least one of them is wrong. Since no dual derivation is provided, the reader cannot determine the correct form, and the inconsistency propagates directly into the eigenvalue estimate (28) used in Proposition 5. This needs to be corrected before the convergence and feasibility arguments can be checked.","section":"Section 4, Eqs. (22), (23), (27)"},{"comment":"The exact-penalty equivalence between the rank-constrained problem (12) and the penalized problem (19) is conditional on the calmness of Γ at 0, and this calmness is assumed but not verified for the QAP/DNN feasible set Ω. In addition, the proof uses the identity dist(Y, R) = ||Y||_* − ||Y||_2 without specifying the norm. This identity is valid for the nuclear-norm distance to the rank-one set, but the error bound dist(Y, Ω∩R) ≤ τ dist(Y, R) invoked from [6] is typically stated in the Euclidean/Frobenius norm, for which the identity is false (e.g., Y = diag(3,2,1) gives ||Y||_* − ||Y||_2 = 3 but Frobenius distance to rank-one is sqrt(5)). As written, the distance equality is not established, so the claim that (19) is an exact penalty reformulation of (12) is not fully supported.","section":"Section 4, Proposition 2"}],"minor_comments":[{"comment":"The paper states that A and B are symmetric as a standard assumption, but it should clarify whether this is without loss of generality for the QAP instances tested, since some QAPLIB data are not symmetric.","section":"Section 2, page 3"},{"comment":"The header line 'Problem set (No.) gap Problem0 ≤ 4% > 4%' is garbled; it should clearly separate the three columns, e.g., 'gap = 0', '0 < gap ≤ 4%', and 'gap > 4%'.","section":"Table 1"},{"comment":"The expression 'ApTN qprYqq' appears to be a typesetting error; it should presumably be A(T_{N^q}(Y)) or similar.","section":"Assumption 2"},{"comment":"The distance is defined as 'dist(x,Z)=min_{z∈Z} ||y−x||', but the variable y is not defined; this should be ||x−z||. Also, 'Kurdyka-ojaziewicz' should be 'Kurdyka–Łojasiewicz'.","section":"Section 4, Definition 1"},{"comment":"The caption contains the typo 'paramenters' for 'parameters', and the figure axes are not described in enough detail to know what the left and right scales represent.","section":"Figure 1 and Section 5.1"},{"comment":"The phrase 'for most QAP instances' is supported by 69 exact solutions out of 107, but the threshold should be stated explicitly in the abstract or conclusions, especially because the theoretical claim on which it is based is currently unproven.","section":"Abstract and Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The numerical work is extensive and potentially useful, but the theoretical narrative in the abstract is stronger than the proofs. The main issue is Proposition 5's uniform-in-ρ bound, which is a genuine gap, not a typo; the sign inconsistency in Eqs. (22) versus (23)/(27) also needs resolution. If the authors can prove the uniform bound or explicitly restrict the feasibility claim, a revised version would be suitable for reconsideration. I would not recommend rejection on the basis of the numerical section alone, but the theoretical claims must be fixed or softened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper has a nice algorithmic idea and surprisingly good numerics, but the headline theoretical claim — that the generated sequence becomes feasible for the rank-constrained DNN — is not actually proven. Proposition 5 has a genuine gap, and there's a sign inconsistency in the subproblem formulation.\n\nWhat's new: the authors combine the known Povh–Rendl copositive reformulation of QAP with the Gao–Sun DC penalty (nuclear norm minus spectral norm) and a proximal DCA. The equivalence theorems (Thm 1–3) are elementary but correct. The convergence to a stationary point of the penalized DC problem (Thm 5) follows from standard KL machinery and is fine. The numerical study on 107 QAPLIB/dre instances is the real contribution: 69 solved exactly and most others within 4%, using a single relaxation. That's worth paying attention to.\n\nThe problem is the proof of rank-one feasibility. In Prop 5, the constant η bounding λ1(−C − A^*y − Z) is claimed finite for all large k, justified by boundedness of the dual level set from Assumption 2. But that bound is for a fixed ρ; nothing shows it is uniform in ρ. With the data term C+ρ(I+W_k) in the dual objective, the dual solution can scale with ρ. The example of min ½||x||²+ρaᵀx s.t. x=0 gives dual y=−ρa. So the condition ρ > η+ζ/σ may be impossible. There's also a concrete sign error: Eq. (22) writes C+ρ(I+W_k), while Eq. (23) and KKT (27) have C+ρ(I−W_k). Those can't both be right. So the abstract's feasibility conclusion doesn't follow from the proof as written. Prop 2 has a related soft spot: the calmness of Γ is assumed and the distance identity dist(Y,R)=||Y||_*−||Y||_2 is norm-sensitive; it holds in nuclear norm but not generally in Frobenius. That makes the exact penalty result conditional rather than established.\n\nNone of this kills the numerical contribution. The experiments are extensive and the reported gaps are credible, though there's no code and the parameter detail is thin. For a reader interested in practical DCA methods for QAP, the numerical part is the main value. For a reader trusting the theory, the paper needs revision: fix Prop 5 (or soften the claim to stationarity of the penalized problem), clean up the sign inconsistency, and be explicit about the norm and calmness assumptions.\n\nI'd send it to referees. The core idea is sound and the numerics are genuinely interesting; the flaws look addressable. With a corrected theory it would be a solid contribution.\n\nRecommended outcome: major revision.","headline":"A useful DCA-for-QAP paper whose numerical results outrun its theory: the rank-one feasibility claim rests on an unproven dual-bound uniformity and a sign slip.","tokens_in":23985,"tokens_out":4474,"would_cite":false,"duration_ms":44775,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C25","90C26","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes an exact rank-constrained doubly nonnegative reformulation of the quadratic assignment problem and gives a proximal difference-of-convex algorithm that reaches the global optimum on most tested instances.","keywords":["quadratic assignment problem","doubly nonnegative programming","rank constraint","difference of convex functions","DC programming","exact penalty","augmented Lagrangian method","semidefinite programming relaxation"],"falsifier":"Choose a QAP instance with $n\\ge 30$, solve the penalized problem (19) for an increasing sequence of penalty parameters $\\rho$, and record the ranks of the iterates produced by Algorithm 1. If for arbitrarily large $\\rho$ the limit point is stationary for (19) but has rank at least two while its objective value is strictly better than the best feasible permutation value, then Proposition 5 is false. A more direct check targets Proposition 2: search the DNN feasible set $\\Omega$ for points where $\\|Y\\|_*-\\|Y\\|_2$ is tiny but the distance from $Y$ to $\\Omega\\cap R$ is comparatively large; such a point would disprove the error-bound identity that carries the exact-penalty argument.","tokens_in":22928,"feed_emoji":"🧩","tokens_out":15062,"duration_ms":124648,"temperature":0.7,"pith_summary":"The paper claims that the quadratic assignment problem (QAP) — the NP-hard task of placing $n$ facilities on $n$ locations while minimizing flow times distance — can be restated exactly as a rank-constrained doubly nonnegative (DNN) program. It then replaces the rank-one condition by a penalty equal to the difference between the nuclear norm and the spectral norm, $\\|Y\\|_*-\\|Y\\|_2$, which is zero exactly for rank-one matrices, turning the problem into a difference-of-convex (DC) program. A proximal DC algorithm is proposed, with inner subproblems solved by a majorized semismooth Newton augmented Lagrangian method, and the paper proves that its iterates converge to a stationary point that is feasible for the rank-constrained problem whenever the penalty parameter is large enough. In experiments on 107 QAPLIB and “dre” instances, the algorithm finds the global optimum for 69 instances, obtains a solution within 4% of the optimum for 32 more, and stays above 4% on only 6. If the claims hold, a single nonconvex relaxation can produce upper bounds that often match the best-known solutions obtained elsewhere by branch-and-bound or by combining many relaxations.","feed_headline":"Quadratic assignment solved exactly on 69 of 107 instances","feed_subtitle":"A rank-one doubly nonnegative reformulation plus a proximal DC algorithm matches the global optimum on most QAPLIB and dre problems.","key_machinery":"The load-bearing object is the rank-one constraint written as a DC penalty: for symmetric matrices, rank at most one is equivalent to $\\|Y\\|_*-\\|Y\\|_2=0$, where the nuclear norm is the sum of the singular values and the spectral norm is the largest singular value. The paper embeds this in the abstract problem (12), with $\\Omega=\\{Y\\in S_+^q\\cap N^q : \\mathcal{A}(Y)=b\\}$ and $R=\\{Y : \\operatorname{rank}(Y)\\le 1\\}$, then minimizes $f_\\rho(Y)=\\langle C,Y\\rangle+\\rho(\\|Y\\|_*-\\|Y\\|_2)$ over $\\Omega$. The proximal DC algorithm linearizes the concave term $-\\rho\\|Y\\|_2$ at each iterate and solves a strongly convex nuclear-norm-regularized subproblem through a dual semidefinite program with an additional nonnegativity cone constraint; the KL property (a local descent condition satisfied by semialgebraic functions) supplies global convergence, and rank-one feasibility of the limit follows from an eigenvalue argument on the dual multiplier. The same $\\Omega$ / $R$ template covers the standard quadratic program and the minimum-cut graph tri-partitioning problem.","core_discovery":"The paper's central claim is Theorem 1: a matrix $Y$ in the doubly nonnegative cone that satisfies the three linear constraints of problem (6) and has $\\operatorname{rank}(Y)\\le 1$ is exactly of the form $\\operatorname{vec}(X)\\operatorname{vec}(X)^T$ for a unique permutation matrix $X$, so the rank-constrained DNN problem (6) and the standard trace formulation (2) share their feasible points and their optimal values. Since $\\operatorname{rank}(Y)\\le 1$ is equivalent to $\\|Y\\|_*-\\|Y\\|_2=0$, the authors study the penalized DC problem (19). Under a calmness assumption on the set-valued map $\\Gamma(w)=\\{Y\\in\\Omega : \\|Y\\|_*-\\|Y\\|_2=w\\}$ at $w=0$, Proposition 2 asserts that for large enough $\\rho$ the penalized problem and the rank-constrained problem have the same global optima, and Proposition 5 asserts that the iterates of the proximal DC algorithm eventually have rank at most one. The convergence proof combines the error-bound inequality $\\operatorname{dist}(Y,\\Omega\\cap R)\\le \\tau(\\|Y\\|_*-\\|Y\\|_2)$ with the KL property of the semialgebraic objective to show that every accumulation point is a stationary point of (19).","pith_inferences":["If the calmness condition in Proposition 2 turns out to hold generically on QAP's DNN feasible sets, the same exact-penalty construction offers a uniform way to certify optimality for instances of moderate size from a single relaxation, rather than assembling many SDP lower bounds.","A concrete numerical check of the error-bound identity $\\operatorname{dist}(Y,\\Omega\\cap R)\\le\\tau(\\|Y\\|_*-\\|Y\\|_2)$ on hard instances such as the “dre” set would separate the theorem from the empirical 69/107 success rate; the paper does not report such a check.","Because the DC penalty relies only on the eigenvalues of $Y$, the approach could be transferred to other rank-constrained DNN models, for example densest-$k$-subgraph or max-cut variants, whenever the linear constraints define a bounded feasible set."],"forward_implications":["For any QAP instance whose DNN feasible set is nonempty and bounded, choosing the penalty parameter $\\rho$ large enough makes every global solution of the penalized DC problem rank-one, hence recoverable as a permutation matrix.","The proximal DC iterates converge to a stationary point of the penalized problem from any starting point in $\\Omega$, with monotonically decreasing objective values.","The same rank-constrained DNN reformulation applies to the standard quadratic program and to the minimum-cut graph tri-partitioning problem, so the DCA pipeline carries over to those NP-hard problems.","On 107 QAPLIB and “dre” instances the method finds the global optimum for 69 and a feasible permutation within 4% for 32 more, so the algorithm can serve as an upper-bound generator without branch-and-bound."],"supporting_citations":[{"why":"It supplies the completely positive relaxation of QAP whose DNN feasible set and rank-one identification $Y=\\operatorname{vec}(X)\\operatorname{vec}(X)^T$ are used in Theorem 1.","marker":"[29]"},{"why":"It introduces the idea of replacing a rank constraint by the DC penalty $\\|Y\\|_*-\\|Y\\|_2$, which is the core of problem (19).","marker":"[17]"},{"why":"It provides the error-bound inequality $\\operatorname{dist}(Y,\\Omega\\cap R)\\le\\tau(\\|Y\\|_*-\\|Y\\|_2)$ used in the proof of Proposition 2.","marker":"[6]"},{"why":"It supplies the majorized-penalty framework on which the convergence argument for Algorithm 1 is modelled.","marker":"[18]"},{"why":"It provides the refined KL convergence result for proximal DCA used to prove Theorem 5.","marker":"[25]"},{"why":"It gives the majorized semismooth Newton-CG augmented Lagrangian method that solves the inner subproblem (20) through its dual.","marker":"[40]"},{"why":"It defines the hard 'dre' QAP instances that make up part of the numerical test bed.","marker":"[15]"},{"why":"It supplies the QAPLIB instances and their optimal or best-known values, providing the benchmark for the reported gaps.","marker":"[19]"}],"fun_headline_variants":["QAP global optimum on 69/107 instances via proximal DC","Proximal DC algorithm solves QAP to global optimality on 69/107","Rank-one DNN reformulation yields QAP global optima on most cases","69/107 QAP instances globally solved via DC approach"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the exact-penalty equivalence of Proposition 2: the paper assumes that the set-valued map $\\Gamma(w)=\\{Y\\in\\Omega : \\|Y\\|_*-\\|Y\\|_2=w\\}$ is calm at $w=0$, and it uses the identity $\\operatorname{dist}(Y,R)=\\|Y\\|_*-\\|Y\\|_2$ without stating that the distance is measured in the nuclear norm; if that calmness fails, or if the distance identity is used in the wrong norm, the penalized problem (19) need not have the same optimal solutions as the rank-constrained problem (12).","fun_headline_variants_meta":{"raw":{"variants":["QAP global optimum on 69/107 instances via proximal DC","Proximal DC algorithm solves QAP to global optimality on 69/107","Rank-one DNN reformulation yields QAP global optima on most cases","69/107 QAP instances globally solved via DC approach"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001894,"raw_usage":{"total_tokens":7434,"prompt_tokens":964,"completion_tokens":6470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":6391}},"tokens_in":580,"tokens_out":6470,"duration_ms":42142,"temperature":1.0,"reasoning_tokens":6391,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:39:43.867242+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a QAP instance with $n\\ge 30$, solve the penalized problem (19) for an increasing sequence of penalty parameters $\\rho$, and record the ranks of the iterates produced by Algorithm 1. If for arbitrarily large $\\rho$ the limit point is stationary for (19) but has rank at least two while its objective value is strictly better than the best feasible permutation value, then Proposition 5 is false. A more direct check targets Proposition 2: search the DNN feasible set $\\Omega$ for points where $\\|Y\\|_*-\\|Y\\|_2$ is tiny but the distance from $Y$ to $\\Omega\\cap R$ is comparatively large; such a point would disprove the error-bound identity that carries the exact-penalty argument.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the completely positive relaxation of QAP whose DNN feasible set and rank-one identification $Y=\\operatorname{vec}(X)\\operatorname{vec}(X)^T$ are used in Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the idea of replacing a rank constraint by the DC penalty $\\|Y\\|_*-\\|Y\\|_2$, which is the core of problem (19)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the error-bound inequality $\\operatorname{dist}(Y,\\Omega\\cap R)\\le\\tau(\\|Y\\|_*-\\|Y\\|_2)$ used in the proof of Proposition 2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the majorized-penalty framework on which the convergence argument for Algorithm 1 is modelled."},{"cited_title":"Computational Optimization Applications 73, 69-100 (2019)","cited_arxiv_id":null,"evidence_quote":"It provides the refined KL convergence result for proximal DCA used to prove Theorem 5."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It gives the majorized semismooth Newton-CG augmented Lagrangian method that solves the inner subproblem (20) through its dual."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines the hard 'dre' QAP instances that make up part of the numerical test bed."},{"cited_title":"seas.upenn.edu/qaplib","cited_arxiv_id":null,"evidence_quote":"It supplies the QAPLIB instances and their optimal or best-known values, providing the benchmark for the reported gaps."}],"review_version":1}