{"id":"e2e950ec-277f-4c71-af7f-ce9526c42f8f","arxiv_id":"2411.11722","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For convex MIQPs with indicator variables and a constraint-block graph of bounded treewidth, the authors present a polynomial-time algorithm that computes a solution that is near-feasible, superoptimal, and satisfies all combinatorial constraints, plus matching NP-hardness results.","lead":"This paper gives a polynomial-time approximation scheme for a family of mixed-integer quadratic programs in which blocks of variables are switched on and off by binary indicators, provided the underlying constraint graph has bounded treewidth. It also shows the problem is NP-hard even for very restricted special cases, so the tractable family is tightly characterized.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 39(d) tracks the unweighted δ-sum for combinatorial constraints, but feasibility uses ∑ v_i^r δ_i with v_i^r = -1; the DP state is not a sufficient statistic, so Lemma 312 and Theorem 14 are unsupported as written.","rationale":"The reader's weakest_assumption identifies precisely the same load-bearing concern: the DP state for combinatorial constraints is not a sufficient statistic for the signed partial sums that determine feasibility. My reading of the paper confirms that Definition 39(d) defines κ̂_r as the sum of δ_i, while (15b) bounds it by signed counts; these are mutually inconsistent whenever any incident block has coefficient -1. This is not a cosmetic issue: the DP cannot even represent a feasible leaf state for a block with v_i^r = -1 and δ_i = 1, so feasible solutions are dropped and Lemma 312's merging rule is invalid. The central algorithmic claim of Theorem 14 depends on the DP solving the minimum sketch ensemble problem exactly, so this gap directly threatens the main result. The concern is concrete and repairable: redefining the state to track the signed partial sum ∑ v_i^r δ_i gives at most 2κ+1 possible values per combinatorial constraint, preserving the polynomial runtime up to constants. Because the repair appears routine and the underlying algorithmic idea remains plausible, the reader's CONDITIONAL verdict is appropriate; no change to the verdict is needed. I found no other independent fatal flaw in the argument: the hardness reductions in Section 4 are self-contained, and the sketch-based approximation structure is otherwise coherent. The signed-combinatorial-state issue is the most fragile point and should be fixed before the proof is accepted.","tokens_in":12336,"tokens_out":18818,"duration_ms":177988,"concrete_test":"Implement the DP exactly as in Section 3 on a minimal instance: two singleton blocks B1, B2, indicators δ1, δ2, one combinatorial constraint r: δ1 - δ2 ≤ 0, empty objective, treewidth 0 (single r in root bag with leaf bags for B1 and B2). Brute force gives optimal value 0 with (δ1,δ2)=(0,1). If the DP, as written with Definition 39(d)/(15b), either rejects δ2=1 at the B2 leaf or returns value > 0 (or reports infeasible), the concern is confirmed. As a broader check, generate all instances with ≤4 blocks and random v_i^r ∈ {0,±1}, compare DP output against exhaustive enumeration over δ; any mismatch settles the issue.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is the DP state for combinatorial constraints. Definition 39(d) requires, for r ∈ C_t, ∑_{i∈β_t} δ_i = κ̂_r, while the actual combinatorial constraint is ∑_{i∈β_t} v_i^r δ_i ≤ b_r with v_i^r ∈ {0,1,-1}. Bound (15b) tries to constrain κ̂_r by the counts of positive/negative incident blocks, but (d) never uses v_i^r. Concretely, take a leaf designated for block B_i with v_i^r = -1 and δ_i = 1: the signed contribution is -1, feasible in many cases, but Definition 39(d) gives κ̂_r = 1, which violates the upper bound in (15b) (0 for this leaf). The state with δ_i = 1 is therefore discarded, so the DP cannot represent feasible solutions that use negatively signed blocks. Lemma 312 merges states by adding κ̂ values, which is only valid if all v_i^r = +1; with negative coefficients the combined signed sum is not the sum of unweighted δ-counts. Since Definition 39 is used in the DP recurrence and the complexity analysis, the correctness of the algorithm (and hence Theorem 14) depends on this unproven and, as written, false state sufficiency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies convex quadratic programs in which blocks of continuous variables are activated by binary indicators, with constraints split into mixed-integer constraints (carrying quadratic/linear terms in the continuous variables) and combinatorial constraints (with coefficients v_i^r in {0,1,-1} on the indicators). The main contribution is a treewidth-parameterized approximation scheme: under a normalized scaling assumption, the authors define per-block convex QCQP sketches and combine them by dynamic programming on the constraint-block intersection graph. Theorem 14 claims a running time of O((n+m)(2/ε)^{2ω+2κ^2 min{mc,ω+1}}) plus per-block sketch solves to either certify infeasibility or return a superoptimal solution that satisfies all combinatorial constraints and violates mixed-integer constraints by at most max_r |B_r| ε. The paper also gives two NP-hardness reductions from SUBSET SUM for very restricted cases, and discusses applications to portfolio optimization, banded quadratic programs, and truss topology design.","tokens_in":12616,"tokens_out":13075,"duration_ms":127477,"significance":"If the main theorem is correct, the paper provides a clean parameterized approximation framework for a broad class of structured MIQPs, with the attractive feature that combinatorial constraints are enforced exactly while mixed-integer constraints are violated only by an additive amount controlled by ε. The proof strategy is coherent, mostly self-contained, and does not rely on fitted constants or external assumptions; the per-block sketch idea is natural, and the hardness reductions are elementary and appear sound. The potential value is substantial, since many practical sparse/QP models fit the QIB form. However, the correctness of the DP state for combinatorial constraints and the claimed polynomial-time consequences for the applications currently need repair before the results can be accepted as stated.","major_comments":[{"comment":"Definition 39(d) states ∑_{i∈β_t} δ_i = κ̂_r, but the actual combinatorial constraint is ∑_{i∈β_t} v_i^r δ_i ≤ b_r with v_i^r ∈ {0,1,-1}, and the declared range in (15b) is a bound on the signed quantity. As written, the state is not a sufficient statistic: for a block with v_i^r = -1 and δ_i = 1, condition (d) increments κ̂_r while the signed contribution is -1, so a feasible solution using that block may be discarded. The merging rule in Lemma 312, which adds κ̂ values across children, is valid only for v_i^r = +1. This is load-bearing for Theorem 14: the DP recurrence can undercount the optimum unless (d) is replaced by ∑_{i∈β_t} v_i^r δ_i = κ̂_r (with corresponding changes in the merge equations), or a separate proof is given that the unweighted δ-sum is recoverable from the state.","section":"Definition 39 / Lemma 312"},{"comment":"The application results are claimed as polynomial-time consequences, but the displayed complexity in Lemma 21 contains an exponent of 2n²: in the portfolio model the cardinality constraint has support κ = n, so a direct application of the Theorem 14 bound is O(n(2/ε)^{2ω+2n²}), which is not polynomial in n. Lemma 22 inherits the same issue, since the orthogonality and cardinality constraints again have O(n) support. The paper should state the precise parameter regime for the polynomial-time claim, either by treating κ as a fixed parameter or by proving a sharper DP bound in which the combinatorial state ranges are bounded by the size of the current bag/subtree rather than by the global support κ.","section":"Lemma 21 / Lemma 22"},{"comment":"The complexity estimate appears inconsistent with the state-count argument. Lemma 314 bounds the number of Π states by (2/ε)^{|M_t|} (max_{r∈C_t}|B_r|)^{|C_t|} ≤ (2/ε)^{ω+1} κ^{min{mc,ω+1}}. When combining two children, the enumeration of pairs of child states squares this quantity, giving roughly (2/ε)^{2ω+2} κ^{2 min{mc,ω+1}}. The printed formula in Theorem 14 and Lemma 314 instead displays an exponent of the form 2ω + 2κ² min{mc,ω+1}, which does not follow from that bound. The authors should reconcile the displayed exponent with the actual DP state enumeration, or provide the precise derivation of the stated complexity.","section":"Theorem 14 / Lemma 314"}],"minor_comments":[{"comment":"Lemma 37(c) states that every node of T has degree ≤ 2, but Case 2 in Section 3.1 describes a node with two children, so the intended statement is that every node has at most two children (equivalently, degree at most 3 in the rooted tree).","section":"Lemma 37(c)"},{"comment":"The quantification 'for all r ∈ β_t' in equation (12a) is not meaningful because β_t is a set of blocks; it should read 'for each mixed-integer constraint r contained in T_t'.","section":"Lemma 38, Eq. (12a)"},{"comment":"In the last two lines of equation (17a), the notation for the combinatorial state uses ˜k_r where the context requires ˜κ_r; the equality κ̂_r = ˜κ_r should be stated consistently.","section":"Lemma 312, Eq. (17a)"},{"comment":"The glossary entry for R_t says 'Ct ∪ Rt', which is circular; it should be 'Ct ∪ Mt' as in Definition 310.","section":"Section 5 Glossary"},{"comment":"The footnote claims the results extend to combinatorial constraints with integral v_i^r in a fixed range, but Definition 39 and Lemma 312 do not explicitly handle this extension; if retained, the extension should be justified in the DP proof.","section":"Footnote 3, page 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is self-contained and the NP-hardness arguments appear sound. The main correctness issue is the combinatorial state definition: if the missing v_i^r in Definition 39(d) is a typographical omission, the fix is local, but it is nonetheless load-bearing because Lemma 312 and Theorem 14 rely on it. The application-level complexity claims also need a careful restatement, since a direct reading of Lemma 21 gives a running time exponential in n², which conflicts with the abstract's polynomial-time wording. I would not reject the paper; the core algorithmic idea is valuable and the issues seem addressable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe genuinely new idea here is the constraint-block intersection graph plus a sketch-based dynamic program for convex QIBs with indicator variables and combinatorial constraints. That is a real extension of the treewidth approach in [4], and the NP-hardness reductions from SUBSET SUM are clean and self-contained. If the main theorem held, this would be a useful general tool for structured MIQPs that previous treewidth methods could not touch, because blocks can be arbitrarily large.\n\nBut there is a load-bearing flaw in Definition 39(d). The DP state for a combinatorial constraint r is κ̂_r, defined as the unweighted sum of δ_i over blocks in the subtree. The actual combinatorial constraint is ∑ v_i^r δ_i ≤ b_r with v_i^r ∈ {0,1,-1}. Take a leaf covering a single block with v_i^r = -1 and δ_i = 1: the signed contribution is -1, feasible in many cases, but (d) forces κ̂_r = 1, which violates the upper bound in (15b) (which is 0 for that leaf). That state is discarded, so the DP cannot represent feasible solutions using negatively signed blocks. Lemma 312 merges states by adding κ̂ values, which is only valid when all v_i^r = +1. This is not a peripheral typo; it is the state definition used in the correctness proof of Theorem 14.\n\nI also want to give credit where it is due: the sketch construction respects the row-scaling assumption, the complexity analysis is careful, and the hardness results are solid. The good news is that the fix is straightforward — define κ̂_r as the signed sum ∑ v_i^r δ_i, which is what (15b) actually bounds, and the merge works because subtrees are disjoint. Nothing I saw requires the unweighted version.\n\nThis paper deserves a serious referee and a revision. I would not cite the current version in my own work until the DP state is fixed, but the framework is worth watching. Bring it to the reading group if you want a concrete case of a small definitional slip breaking a treewidth DP.","headline":"New treewidth framework for structured MIQPs, but the DP state for combinatorial constraints is defined with unweighted δ-sums, which breaks for negative coefficients; fixable, yet as written the main theorem is unsupported.","tokens_in":13100,"tokens_out":3520,"would_cite":false,"duration_ms":34000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C20","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a broad class of NP-hard convex quadratic programs with indicator variables becomes polynomial-time approximable when the constraint-block incidence graph has bounded treewidth, via a dynamic program over sketch…","keywords":["mixed-integer quadratic programming","indicator variables","treewidth","dynamic programming","cardinality constraints","convex QCQP","NP-hardness","structured sparsity"],"falsifier":"Run the dynamic program on the instance whose only combinatorial constraint is $\\delta_a+\\delta_b-\\delta_c\\le 0$, with a tree decomposition whose two children contain only blocks $\\{a\\}$ and $\\{b,c\\}$. Take the left child state $\\delta_a=1$ (so $\\hat\\kappa=1$) and the right child state $\\delta_b=1$, $\\delta_c=0$ (also $\\hat\\kappa=1$). The merge in Lemma 312 accepts total $\\hat\\kappa=2$, which lies in the interval $[-1,2]$ allowed by (15b) and matches Definition 39(d), yet the true signed sum is $1+1-0=2>0$, violating the constraint. If the algorithm returns the ensemble built from this merge as feasible, that is a counterexample to the DP's correctness.","tokens_in":12146,"feed_emoji":"🧮","tokens_out":11773,"duration_ms":104690,"temperature":0.7,"pith_summary":"The paper studies convex quadratic programs in which disjoint blocks of continuous variables are switched on and off by binary indicators, subject to mixed-integer constraints (convex quadratics) and combinatorial constraints such as cardinality limits. It claims that whenever the graph linking constraints to blocks has bounded treewidth, the problem admits a polynomial-time approximation algorithm: the algorithm returns a solution whose objective is no worse than the true optimum, which satisfies every combinatorial constraint exactly, and which violates each mixed-integer constraint by at most $\\max_r |B_r|\\varepsilon$. This matters because several practically studied problems—portfolio selection, banded-matrix indicator quadratic programs, and truss topology design—fit the template. The paper also proves that the tractability boundary is tight: even restricted feasibility versions are NP-hard when the graph has pathwidth 2 or when only two linear mixed-integer constraints are present.","feed_headline":"Structured MIQPs get a polynomial-time ε-feasible solver","feed_subtitle":"Returns superoptimal solutions that keep combinatorial constraints exact, continuous violations within ε.","key_machinery":"The load-bearing object is the sketch ensemble. A sketch for block $B_i$ is a pair $(\\delta,\\{\\hat k_r\\}_{r\\in M_i})$ in which $\\delta\\in\\{0,1\\}$ says whether the block's indicator is on and each integer $\\hat k_r$ buckets the block's contribution to mixed-integer constraint $r$ into intervals of width $\\varepsilon$; the sketch's value is the optimum of a small convex QCQP restricted to that block. A feasible sketch ensemble selects one sketch per block so that the bucket sums fit each mixed-integer constraint's budget and the signed indicator sums satisfy each combinatorial constraint. The dynamic program propagates, up a tree decomposition of the constraint-block intersection graph, state pairs $(\\{\\hat k_r\\}_{r\\in M_t},\\{\\hat\\kappa_r\\}_{r\\in C_t})$ summarizing the partial sums in the processed subtree; at a bag with two children it merges states by adding these counters. Lemma 312 asserts that merging in this way is exact, which is the step that carries the whole complexity bound.","core_discovery":"On its own terms, the paper establishes a fixed-parameter-style theorem. For problem QIB, let $\\omega$ be the treewidth of the constraint-block intersection graph, $\\kappa$ the largest support of a combinatorial constraint, and $m_c$ the number of combinatorial constraints. Theorem 14 states that for any $0<\\varepsilon<1$ there is an algorithm running in time $O((n+m)(2/\\varepsilon)^{2\\omega+2\\kappa^2\\min\\{m_c,\\omega+1\\}})$ plus the cost of solving $O(|B|(2/\\varepsilon)^\\omega)$ convex QCQPs, each with at most $\\omega+1$ constraints, that either proves infeasibility or outputs a vector which is superoptimal (value no larger than the true optimum), feasible for all combinatorial constraints, and has maximum infeasibility at most $\\max_r |B_r|\\varepsilon$ over mixed-integer constraints. The proof builds a minimum-value sketch ensemble and assembles it by dynamic programming over a tree decomposition. The negative results are reductions from SUBSET SUM: feasibility with a cardinality constraint is NP-hard even when the incidence graph has pathwidth 2, and the full problem is NP-hard even with only two linear mixed-integer constraints plus a cardinality constraint.","pith_inferences":["The paper does not discuss the consequence that if exact merging requires signed counters rather than a single active-block count, the DP state would grow from $\\kappa^2$ to something exponential in $\\kappa$ or in the coefficient range, so the theorem's runtime would change.","A testable extension would be an empirical comparison on QPLIB instances such as 5925: run the sketch DP with modest $\\varepsilon$ and check whether the superoptimal objective and $\\varepsilon$-infeasible solution beat commercial solvers' 3% gap in wall-clock time; the paper reports no experiments.","Because the infeasibility guarantee is additive in the number of incident blocks, applying the theorem to constraints that touch many blocks requires rescaling $\\varepsilon$ by $1/\\max_r|B_r|$; the paper leaves this rescaling implicit."],"forward_implications":["For cardinality-constrained portfolio optimization with a low-rank quadratic term and $O(1)$ linear constraints, the theorem gives a polynomial-time algorithm whose output is superoptimal, satisfies the cardinality constraint exactly, and violates the linear constraints by at most $\\varepsilon$ per incident-block count.","For convex quadratic problems with banded matrices and indicator variables, the method gives an $O(n(2/\\varepsilon)^{2k})$ algorithm when the bandwidth is $k$, an alternative to the existing real-time method.","For truss topology design with a bounded-treewidth constraint-block graph, approximate solutions can be computed in polynomial time even though testing feasibility exactly is NP-hard at pathwidth 2.","The algorithm either certifies infeasibility or produces the $\\varepsilon$-feasible, superoptimal vector described in Theorem 14, so the approximation guarantee does not require guessing the active-block set in advance.","The NP-hardness results mark the boundary of this approach: bounded treewidth alone is insufficient once a cardinality constraint is added, and two linear constraints plus cardinality already make the problem weakly NP-hard."],"supporting_citations":[{"why":"Supplies the classical NP-hardness result for cardinality-constrained quadratic programs that motivates the QIB model.","marker":"[3]"},{"why":"Provides the treewidth-based polynomial-optimization framework whose different setup the paper extends to block-indicator QPs.","marker":"[4]"},{"why":"Supplies the dynamic-programming-on-bounded-treewidth paradigm underlying the sketch DP.","marker":"[5]"},{"why":"Gives the banded-matrix indicator-QP algorithm whose runtime and guarantee the paper compares against.","marker":"[8]"},{"why":"Defines the truss topology design problem used as an application of the framework.","marker":"[1]"},{"why":"Provides the QPLIB instance that motivates the empirical relevance of bounded-pathwidth structure.","marker":"[6]"},{"why":"Gives a recent scalable algorithm for sparse portfolio selection, a comparison target for the portfolio application.","marker":"[2]"}],"fun_headline_variants":["Fixed-parameter ε-feasible solver for convex QPs","Superoptimal ε-feasible solutions for structured QPs","Treewidth-based algorithm for MIQPs with combinatorial constraints","NP-hardness and fixed-parameter tractability for indicator QPs","Polynomial-time for fixed treewidth: convex QPs with indicators"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dynamic program's correctness depends on the assumption that, for each combinatorial constraint, a single integer recording how many blocks are active in the processed subtree completely determines that subtree's contribution to the constraint, even when the constraint has negative coefficients.","fun_headline_variants_meta":{"raw":{"variants":["Fixed-parameter ε-feasible solver for convex QPs","Superoptimal ε-feasible solutions for structured QPs","Treewidth-based algorithm for MIQPs with combinatorial constraints","NP-hardness and fixed-parameter tractability for indicator QPs","Polynomial-time for fixed treewidth: convex QPs with indicators"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001289,"raw_usage":{"total_tokens":5210,"prompt_tokens":840,"completion_tokens":4370,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":456,"completion_tokens_details":{"reasoning_tokens":4284}},"tokens_in":456,"tokens_out":4370,"duration_ms":29875,"temperature":1.0,"reasoning_tokens":4284,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:14:01.726939+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the dynamic program on the instance whose only combinatorial constraint is $\\delta_a+\\delta_b-\\delta_c\\le 0$, with a tree decomposition whose two children contain only blocks $\\{a\\}$ and $\\{b,c\\}$. Take the left child state $\\delta_a=1$ (so $\\hat\\kappa=1$) and the right child state $\\delta_b=1$, $\\delta_c=0$ (also $\\hat\\kappa=1$). The merge in Lemma 312 accepts total $\\hat\\kappa=2$, which lies in the interval $[-1,2]$ allowed by (15b) and matches Definition 39(d), yet the true signed sum is $1+1-0=2>0$, violating the constraint. If the algorithm returns the ensemble built from this merge as feasible, that is a counterexample to the DP's correctness.","supporting_citations":[{"cited_title":"SIAM Journal on Optimization 3(2), 322–358 (1993)","cited_arxiv_id":null,"evidence_quote":"Defines the truss topology design problem used as an application of the framework."},{"cited_title":"Mathematical Programming 74, 121–140 (1996)","cited_arxiv_id":null,"evidence_quote":"Supplies the classical NP-hardness result for cardinality-constrained quadratic programs that motivates the QIB model."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the treewidth-based polynomial-optimization framework whose different setup the paper extends to block-indicator QPs."},{"cited_title":"In: Lepist¨ o, T., Salomaa, A","cited_arxiv_id":null,"evidence_quote":"Supplies the dynamic-programming-on-bounded-treewidth paradigm underlying the sketch DP."},{"cited_title":"arXiv:2 405.03051 pp","cited_arxiv_id":null,"evidence_quote":"Gives the banded-matrix indicator-QP algorithm whose runtime and guarantee the paper compares against."},{"cited_title":"Informs J","cited_arxiv_id":null,"evidence_quote":"Gives a recent scalable algorithm for sparse portfolio selection, a comparison target for the portfolio application."}],"review_version":1}