{"id":"69c5856e-6314-499a-abb2-0ec4371c2ec0","arxiv_id":"2506.18265","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors apply spectral outer-approximation cuts from continuous SDP to binary SDP reformulations of binary QCQPs, reporting strong speedups on Boolean least squares and mixed results on quadratic knapsack.","lead":"The paper develops faster ways to solve integer optimization problems where a correlation matrix must stay positive semidefinite, using specially chosen matrix directions to cut down the search. Its main method beats existing integer semidefinite solvers on random Boolean least squares instances, but not on quadratic knapsack.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's q1/q2 construction is under-specified: for the quadratic-knapsack instances no linear combination of the stated constraint matrices equals I, and the n-dimensional diagonalization is never reconciled with the (n+1)-dimensional lifted SDP.","rationale":"The central claim is empirical: OA_SOC is competitive with or faster than SCIP-SDP and PAJARITO on BSDP reformulations of BQCQPs. For that claim to be meaningful, Algorithm 2 must be well-defined on the test instances. The reader's weakest assumption captures this, and the text confirms the gap: Section 5.2's QK has only one quadratic-constraint matrix diag(w), so step 1 cannot hold as written; Section 4's transition from the standard SDP (3) to the lifted cone used by the actual BSDP is never formalized. My stress-test adds that program (6) as written enforces only commutativity, not the disjoint-support or nonzero conditions on q2, so the zero vector is always feasible and the spectral set can collapse to eigenvectors of C alone. This is an under-specification rather than a proven falsehood: the authors may have used a lifted formulation with implied bound constraints, but that is not in the manuscript. The conditional verdict remains appropriate; I would not move to reject because the empirical results could survive a clarification and the code is publicly referenced. The required revision is to state the exact constraint matrices used in Algorithm 2 and either prove or explicitly construct q1 and q2 for each problem family in Sections 5.1 and 5.2.","tokens_in":21171,"tokens_out":10060,"duration_ms":102988,"concrete_test":"Instrument the released repository (github.com/SECQUOIA/Spectral-Outer-Approximation) to print, for the QK and BLS instances of Tables 1-3, the full list of matrices A_i actually used in Algorithm 2 step 1, the computed q1, q2, and the commutator norm ||C A(q2) - A(q2) C||. Verify that sum_i q1_i A_i = I and that q2 is nonzero with support disjoint from q1. If the printed A_i include constraints not stated in Sections 5.1-5.2 (e.g., 0<=x_i<=1 or Z_{n+1,n+1}=1), or if step 1 is skipped or adjusted by an ad hoc rule, then the paper's Algorithm 2 is not the algorithm that produced Tables 1-3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 (Section 4) starts from a standard SDP min <C,X> s.t. <A_i,X>=b_i, X⪰0, and requires, in step 1, q1 with sum_i q1_i A_i = I, and in step 2, q2 of disjoint support with [C, sum_i A_i q2_i]=0. The paper's test problems are not instances of (3) in the form stated. For QK (Section 5.2), after eliminating x via Diag(X)=x, the only constraint matrix is diag(w), so sum_i q1_i A_i=I would require q1 diag(w)=I, impossible for non-constant weights. If instead the lifted (n+1)x(n+1) formulation is used, I_{n+1} has a nonzero last diagonal and off-diagonal entries; canceling the off-diagonal contributions of Diag(X)=x forces q_card = 1/w_i for all i or requires additional domain constraints (0<=x_i<=1, Z_{n+1,n+1}=1) that are never listed in Section 5.2. The paper never states which constraint set the A_i in Algorithm 2 refer to, so the reported QK/OA_SOC results cannot be reproduced from the algorithm as written. Program (6) also omits the 'support disjoint from q1' and nonzero requirements; with a zero objective, q2=0 is feasible, in which case S is just eigenvectors of C and the method is not the advertised simultaneous-diagonalization algorithm.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two outer-approximation algorithms for integer semidefinite programs arising from binary QCQPs: a spectral second-order outer approximation (OA_SOC, Algorithm 2) and a lazy-constraint branch-and-cut variant (LAZY_SOC, Algorithm 3). The key idea is to generate valid cuts v^T(X−xx^T)v ≥ 0 from eigenvectors of a matrix that simultaneously diagonalizes the objective C and an aggregation A(q2) of the constraint matrices, and to update the outer approximation with dual cuts, with finite termination guaranteed by Lemma 1. The paper reports computational experiments on cardinality-constrained Boolean least squares (Section 5.1) and quadratic knapsack (Section 5.2), comparing OA_SOC and LAZY_SOC with SCIP-SDP, PAJARITO, and the Kobayashi–Takano algorithms. Tables 1–3 show OA_SOC solving BLS instances up to n=100 in seconds and being competitive on QK for small n, while SCIP-SDP wins on larger QK instances. The central claim is that the spectral outer-approximation approach is competitive with, and sometimes faster than, state-of-the-art ISDP solvers.","tokens_in":21540,"tokens_out":10833,"duration_ms":98618,"significance":"If the algorithm were fully specified and the experimental results reproducible, this would be a useful empirical contribution to the emerging area of integer semidefinite programming for binary QCQPs. The study is comparatively broad: ten random instances per parameter setting, shifted geometric means, a one-hour time limit, and comparisons against several established solvers, with the code made available. The paper honestly notes that specialized MIQP solvers such as Gurobi can outperform ISDP-based approaches on QK. The main novelty—spectral cuts from simultaneous diagonalization—is clearly motivated, and Lemma 2 provides a neat disaggregation of dual PSD cuts into second-order constraints. However, the significance is contingent on clarifying how the spectral set S is actually constructed for the test problems; as written, the algorithm's description does not match the problems solved.","major_comments":[{"comment":"Algorithm 2 requires a vector q1 with sum_i q1_i A_i = I and a vector q2, with support disjoint from q1, such that C and sum_i A_i q2_i commute. The paper never states which constraint matrices A_i are used (the original n×n matrices or the lifted (n+1)×(n+1) matrices of the BSDP reformulation), and for the test problems neither interpretation supports the existence of such q1. In the quadratic knapsack formulation QKSDP of Section 5.2, after encoding Diag(X)=x, the n×n constraint matrices are the single matrix diag(w), and no scalar multiple of diag(w) equals I_n for non-constant weights. In the lifted formulation, the matrices encoding Diag(X)=x introduce off-diagonal entries that cannot be canceled by any linear combination of the available constraint matrices, so no combination equals I_{n+1}. The same obstruction applies to the BLS problem of Section 5.1. Consequently, Algorithm 2 as written cannot be instantiated for the problems whose results are reported in Tables 1–3, and the OA_SOC results are not reproducible from the manuscript. The authors must specify the constraint set used in Algorithm 2, prove the existence of q1 and q2 for the test instances, or describe the construction actually used in the experiments.","section":"Section 4, Algorithm 2, steps 1–2; Sections 5.1–5.2"},{"comment":"Program (6) is stated as min f(y) subject to C A(y) = A(y) C, and the text notes that the zero matrix always serves as a feasible solution. The constraints that q2 be nonzero and have support disjoint from q1, which are stated in Algorithm 2 step 2, do not appear in the displayed program. As written, q2=0 is always feasible, in which case the commuting condition is trivial and the set S in Algorithm 2 reduces to the eigenvectors of C alone; the method then degenerates to standard eigenvector cuts and is not the advertised simultaneous-diagonalization algorithm. The authors should present the full optimization problem including the missing constraints (with variables in R^r rather than R^n, since there are r constraint matrices) and discuss when feasible aggregations exist.","section":"Section 4, Eq. (6)"},{"comment":"The labels 'basic' and 'spectral' are used inconsistently. The text says that problems with the cuts v^T(X−xx^T)v ≥ 0 are 'basic' and those without are 'spectral', yet immediately afterward the same cuts are called 'spectral cuts', and the discussion says that 'spectral cuts reduce the performance' of most methods while 'OA_SOC with the basic formulation performs the best.' Since the tables and figures compare PAJARITO_OA-basic versus PAJARITO_OA-spectral, SCIPSDP-basic versus SCIPSDP-spectral, and related pairs, the reader cannot determine which formulation was used for each reported number. This ambiguity affects the interpretation of the central empirical comparison and must be resolved.","section":"Section 6, first paragraph of experimental setup"}],"minor_comments":[{"comment":"The definition of [n] reads 'For an integer k∈N, [n] denotes the set of natural numbers {1,...,k}'; this should be 'For an integer n∈N, [n] denotes {1,...,n}.'","section":"Section 1.1 (Notation)"},{"comment":"The optimization variable in program (6) is written as y∈R^n, but the number of constraint matrices is r; it should be y∈R^r. The accompanying sentence 'the zero matrix always serves as a feasible solution' should refer to the zero vector.","section":"Section 4, Eq. (6)"},{"comment":"The definition of the standard second-order cone L^{1+n} is written as r ≥ ||t||_2^2; the standard second-order cone is r ≥ ||t||_2. The squared norm belongs to the rotated second-order cone defined just below.","section":"Section 4.1"},{"comment":"The suggested cut in Algorithm 2 step 8 is written as w_j^T X w_j ≥ (w_j z_j)^2; this is dimensionally inconsistent and should be w_j^T X w_j ≥ (w_j^T x)^2, matching the hypothesis of Lemma 2.","section":"Section 4.2, paragraph after Lemma 2"},{"comment":"The sentence 'Let S′ be optimal for the latter program' should refer to the dual program DSDP(X_L); the variable S′ lives in the dual, so 'latter' should be 'former'. Also, 'Set T={S′}' should be 'Set T = T ∪ {S′}' to align with Algorithm 1 step 6.","section":"Section 3, Lemma 1"},{"comment":"The last line of Algorithm 3 is garbled ('Go to 3. return X^'); the stopping criterion for the lazy-constraint loop (namely λ_n(X^) ≥ −ε) should be stated explicitly as a condition in the branch-and-bound procedure.","section":"Section 4, Algorithm 3"},{"comment":"The sentence 'Since CUTSDP is essentially the same algorithm as the cutting plane algorithm of these two authors, we do not test the latter algorithm' is unclear, because KOB_Cutting_Plane appears in the tables and figures; presumably the authors mean they do not test CUTSDP, not the Kobayashi–Takano cutting-plane algorithm.","section":"Section 6, experimental setup paragraph"},{"comment":"The paragraph beginning 'The results of the cardinality-constrained Boolean least squares problem are consistent...' appears twice with slightly different wording; one copy should be deleted.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the mismatch between Algorithm 2's specification and the test problems. This is a load-bearing gap, but it is fixable in a revision: the authors need to define the constraint matrices explicitly, prove or state the exact construction of q1 and q2 for BLS and QK, and clarify the basic/spectral naming. If they instead used q2=0 or only eigenvector cuts of C throughout, the claimed novelty of simultaneous diagonalization would be substantially weakened, and the paper would need to honestly state that. The computational study itself appears internally consistent and compares against external solvers, so I see no circularity concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe takeaway: OA_SOC is genuinely fast on Boolean least squares — sub-minute at n=100 in their tables — and the comparison against SCIP-SDP and PAJARITO is broad and fairly presented. But the paper's central algorithmic mechanism, the spectral outer approximation, is the weakest part, and the text doesn't fully specify what the code actually does.\n\nWhat's new: the transfer of de Roux et al.'s instance-specific spectral OA to BSDPs from BQCQPs, a lazy branch-and-cut variant, and a cut-disaggregation lemma. Those are legitimate additions.\n\nWhere the paper earns credit: the computational study is honest. It says spectral cuts often hurt. It says SCIP-SDP dominates on QK. Many papers in this area would bury those results. That candor counts.\n\nWhere it's soft, in order:\n\n1. Algorithm 2's initialization is not reproducible from the paper. Step 1 requires q1 with sum q1_i A_i = I. For QK, with constraints Diag(X)=x and the knapsack inequality, no linear combination of the stated constraint matrices equals the identity — the stress-test note works that out for the lifted (n+1)x(n+1) formulation as well. The paper never says what A_i are in the actual instances. If the code fills the gap, fine, but a reader can't reconstruct the method as written.\n\n2. Program (6) as stated is degenerate: q2=0 is always feasible, and the 'support disjoint' and nonzero conditions are dropped in the displayed program. Without them, S may reduce to eigenvectors of C, and the simultaneous-diagonalization claim is empty.\n\n3. The marketed 'spectral' part is not the performance driver. Their own tables show the basic OA_SOC wins, and spectral cuts often make things worse. The abstract's emphasis on spectral decomposition is thus at odds with the evidence.\n\n4. Minor: the 'basic' vs 'spectral' naming in Section 6 is confusing, and no commit hash or instance data is provided despite the code link.\n\nThe central empirical claim is plausible and the comparison is useful. The reproducibility gap is real but likely fixable. This deserves a serious referee, especially to force the authors to specify the formulation and provide the code artifact.\n\nRecommendation: send to peer review; expect a major revision asking for a precise statement of A_i, a corrected program (6), and code/data.","headline":"Genuinely useful empirical results on Boolean least squares, but Algorithm 2's spectral initialization is under-specified and the marketed spectral mechanism isn't what drives the wins.","tokens_in":22033,"tokens_out":6375,"would_cite":false,"duration_ms":60305,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C10","90C20","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that binary quadratically constrained quadratic programs, rewritten as binary semidefinite programs, can be solved faster with a spectral outer-approximation algorithm whose cuts come from a common eigenbasis of the…","keywords":["binary semidefinite programming","outer approximation","eigenvector cuts","simultaneous diagonalization","binary quadratically constrained quadratic programs","integer semidefinite programming","Boolean least squares","quadratic knapsack"],"falsifier":"Run the algorithm on a binary semidefinite reformulation of a BQCQP whose quadratic constraint matrices are all diagonal and have no positive linear combination equal to the identity; if the solver still succeeds quickly, the identity aggregation is not load-bearing, and if it fails, the reported speed-ups depend on an aggregation the paper never explicitly constructs.","tokens_in":20993,"feed_emoji":"⚡","tokens_out":5217,"duration_ms":48134,"temperature":0.7,"pith_summary":"This paper claims that binary quadratically constrained quadratic programs, once rewritten exactly as binary semidefinite programs, can be solved efficiently by a specialized outer-approximation scheme that uses eigenvector-based cuts. The cuts come from a matrix that simultaneously diagonalizes the objective and a weighted sum of the constraints, yielding a polyhedral or second-order outer approximation of the semidefinite cone. The authors report that the resulting algorithm solves cardinality-constrained Boolean least squares instances with up to 100 variables in seconds and is competitive with or faster than established integer-semidefinite solvers on the tested problems. If correct, this makes integer semidefinite programming a practical route for a broad class of binary quadratic problems.","feed_headline":"Eigenvector cuts speed up binary semidefinite solves","feed_subtitle":"A spectral outer-approximation solves Boolean least squares instances with up to 100 variables in seconds.","key_machinery":"The load-bearing object is the simultaneous diagonalizer: a matrix $U$ whose columns are eigenvectors of both the objective matrix $C$ and an aggregation $A(q_2) = \\sum_i q_{2,i} A_i$ that commutes with $C$, found by solving the linear program $\\min f(y)$ subject to $C A(y) = A(y) C$. Its columns $v_1,\\dots,v_n$ define the second-order cuts $v^\\top (X - xx^\\top) v \\geq 0$ that outer-approximate $X - xx^\\top \\succeq 0$; the identity aggregation $q_1$ with $\\sum_i q_{1,i} A_i = I$ enters through the augmented matrix $\\begin{pmatrix} X & x \\\\ x^\\top & 1 \\end{pmatrix}$ used in the second-order formulation. Lemma 2 shows that disaggregating a dual positive semidefinite matrix into eigenvector terms turns one linear cut into several second-order cuts that together imply it, which is what allows the outer approximation to tighten until the lower and upper bounds meet.","core_discovery":"The central discovery is that the simultaneous-diagonalization idea, previously used for instance-specific linear relaxations of ordinary semidefinite programs, transfers to the binary setting: for binary semidefinite programs arising from binary QCQPs, take the constraint $X - xx^\\top \\succeq 0$, find two weighted aggregations of the original quadratic constraint matrices — one equal to the identity, one commuting with the objective — and use their common eigenvectors as cut directions $v^\\top (X - xx^\\top) v \\geq 0$. Adding these spectral cuts to an outer-approximation loop (Algorithm 2) and to a lazy branch-and-bound variant (Algorithm 3) gives a solver that the paper shows outperforms the generic outer-approximation, cutting-plane, and branch-and-bound integer-semidefinite baselines on Boolean least squares and remains competitive on quadratic knapsack.","pith_inferences":["The identity aggregation $\\sum_i q_{1,i} A_i = I$ cannot hold for the raw quadratic constraint matrices of the tested problems unless the affine constraints $\\mathrm{Diag}(X) = x$ are silently folded into the matrices $A_i$; the paper never states this, and without it the eigenvector set collapses to eigenvectors of $C$ alone.","The cut-generation recipe may generalize to mixed-integer conic programs beyond semidefinite ones, wherever a simultaneous diagonalizer exists for the objective and one constraint aggregation, though the paper only demonstrates the semidefinite case.","The tables show spectral cuts sometimes hurt performance (for instance, on some quadratic knapsack settings), so a testable extension is to characterize when the common-eigenbasis cuts tighten the relaxation enough to justify the extra second-order cone burden."],"forward_implications":["Integer semidefinite programming becomes a practically viable way to solve binary quadratically constrained quadratic programs, not just a theoretical reformulation.","The spectral cuts $v^\\top (X - xx^\\top) v \\geq 0$ can be added to existing integer-semidefinite solvers as a strengthened formulation, independent of the outer-approximation loop.","The lazy single-tree variant avoids restarting the mixed-integer solver from scratch at every outer iteration, which is why it scales to larger Boolean least squares instances.","The method applies beyond BQCQP-derived problems to any integer semidefinite program where an objective and a constraint aggregation admit a common eigenbasis.","On quadratic knapsack, the same algorithm remains competitive for small instances but is beaten by a generic branch-and-bound approach for $n \\geq 30$, so the spectral recipe is not universally dominant."],"supporting_citations":[{"why":"Supplies the exact reformulation theorem that converts any BQCQP into a binary semidefinite program, which is the starting point of the paper's approach.","marker":"[de Meijer and Sotirov 2023]"},{"why":"Provides the simultaneous-diagonalization aggregation method and the instance-specific linear relaxation theory that the spectral cuts are built on.","marker":"[de Roux et al. 2025]"},{"why":"Supplies the general outer-approximation algorithm for mixed-integer convex programs and the PAJARITO implementation used as a baseline.","marker":"[Lubin et al. 2018]"},{"why":"Provides the second-order cone outer-approximation variant and the single-tree branch-and-bound idea that Algorithm 3 adapts.","marker":"[Coey et al. 2020]"},{"why":"Supplies the SCIP-SDP branch-and-bound solver used as a baseline and the shifted geometric mean aggregation metric for timings.","marker":"[Gally et al. 2018]"},{"why":"Supplies the cutting-plane and branch-and-cut algorithms used as baselines and the eigenvector-cut idea for mixed-integer SDP.","marker":"[Kobayashi and Takano 2020]"},{"why":"Supplies the quadratic knapsack instance generator used for the computational tests.","marker":"[Pisinger 2007]"}],"fun_headline_variants":["Spectral cuts beat generic ISDP solvers on binary QCQPs","Common eigenvectors yield efficient binary SDP outer bounds","Binary QCQP reformulations solved via spectral cuts in ISDP","Simultaneous diagonalization powers new binary SDP algorithm","New spectral outer approximation outperforms generic ISDP solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method needs two weighted combinations of the constraint matrices: one that equals the identity matrix and another, with no overlapping weights, that commutes with the objective matrix; if such combinations do not exist, the advertised eigenvector set reduces to eigenvectors of the objective alone.","fun_headline_variants_meta":{"raw":{"variants":["Spectral cuts beat generic ISDP solvers on binary QCQPs","Common eigenvectors yield efficient binary SDP outer bounds","Binary QCQP reformulations solved via spectral cuts in ISDP","Simultaneous diagonalization powers new binary SDP algorithm","New spectral outer approximation outperforms generic ISDP solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001748,"raw_usage":{"total_tokens":6884,"prompt_tokens":908,"completion_tokens":5976,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":5893}},"tokens_in":524,"tokens_out":5976,"duration_ms":39075,"temperature":1.0,"reasoning_tokens":5893,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:52:42.219347+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on a binary semidefinite reformulation of a BQCQP whose quadratic constraint matrices are all diagonal and have no positive linear combination equal to the identity; if the solver still succeeds quickly, the identity aggregation is not load-bearing, and if it fails, the reported speed-ups depend on an aggregation the paper never explicitly constructs.","supporting_citations":[{"cited_title":"On Integrality in Semidefinite Programming for Discrete Optimization","cited_arxiv_id":"2306.09865","evidence_quote":"Supplies the exact reformulation theorem that converts any BQCQP into a binary semidefinite program, which is the starting point of the paper's approach."},{"cited_title":"Instance-specific linear relaxations of semidefinite optimization problems","cited_arxiv_id":null,"evidence_quote":"Provides the simultaneous-diagonalization aggregation method and the instance-specific linear relaxation theory that the spectral cuts are built on."},{"cited_title":"Polyhedral approximation in mixed-integer convex optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the general outer-approximation algorithm for mixed-integer convex programs and the PAJARITO implementation used as a baseline."},{"cited_title":"Outer approximation with conic certificates for mixed-integer convex problems","cited_arxiv_id":null,"evidence_quote":"Provides the second-order cone outer-approximation variant and the single-tree branch-and-bound idea that Algorithm 3 adapts."},{"cited_title":"A framework for solving mixed-integer semidefinite programs","cited_arxiv_id":null,"evidence_quote":"Supplies the SCIP-SDP branch-and-bound solver used as a baseline and the shifted geometric mean aggregation metric for timings."},{"cited_title":"A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems","cited_arxiv_id":null,"evidence_quote":"Supplies the cutting-plane and branch-and-cut algorithms used as baselines and the eigenvector-cut idea for mixed-integer SDP."},{"cited_title":"The quadratic knapsack problem—a survey","cited_arxiv_id":null,"evidence_quote":"Supplies the quadratic knapsack instance generator used for the computational tests."}],"review_version":2}