{"id":"5ee41a64-41f5-4743-994d-f15c395134bc","arxiv_id":"2501.05052","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Using a time-limited suboptimal relaxation to guide variable fixing beats using an optimal relaxation in RENS and Undercover on several MBQP benchmarks and a wind farm layout problem.","lead":"The paper introduces two primal heuristics, Relax-Search and Cover-Relax-Search, that use a quickly computed, possibly suboptimal relaxation solution to decide which binary variables to fix in a mixed binary quadratic program. On synthetic MBQP benchmarks and California wind farm layout instances, the NLP-based variants report much lower primal gap and primal integral than RENS, Undercover, and SCIP's built-in heuristics within 60 seconds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported advantage of 'suboptimal' relaxation is confounded with the p=0.7 fixing rule; without an optimal-relaxation + same-p control, the paper does not establish that suboptimality (rather than aggressive fixing) drives the gains.","rationale":"The reader's weakest assumption concerns a possible time-allocation asymmetry between RENS+/Undercover+ and the proposed methods. That asymmetry, if present, would only make the baselines stronger (they are explicitly allowed to continue BnB on the original problem after the heuristic), so it cannot generate an artificial advantage for the proposed heuristics. The more serious threat to the central claim is the omission of a same-p, optimal-relaxation control. The proposed method changes the relaxation quality and the fixing rule simultaneously. RENS fixes only variables that are integral in the optimal relaxation; on these benchmarks that may be a very small set, leaving a large subproblem. Relax-Search fixes 70% of all binary variables, creating a dramatically smaller subproblem. The time saved by using a suboptimal relaxation (up to 20s cutoff) also frees time for the sub-MBQP, but without an optimal-relaxation control there is no way to separate these two mechanisms. The paper's sensitivity analysis over p does not fix this: it only shows that within the proposed pipeline, p=0.7 is a reasonable choice; it does not show that the benefit over RENS survives when the relaxation is solved to optimality under the same fixing rule. Therefore the central novelty claim ('suboptimal rounding guidance') is not yet established, although the method itself is promising. This supports a conditional verdict with the additional control experiment as a condition.","tokens_in":13548,"tokens_out":9357,"duration_ms":92598,"concrete_test":"Add a control on the same 100-instance synthetic benchmarks and the WFLOP instances: solve the LP/NLP relaxation to optimality (no 20s cutoff), then apply Algorithm 2 with p=0.7 and the same 60s total budget and same warm start. Compare Relax-SearchOpt-p against Relax-Search (time-limited relaxation, p=0.7) on primal gap and primal integral. If the two are statistically indistinguishable, the suboptimality of the relaxation is not the driver; if the time-limited version dominates, suboptimality matters as claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that using a time-limited (suboptimal) relaxation as rounding guidance improves primal heuristics for MBQPs. But the experimental comparison does not isolate suboptimality. In Algorithm 2, Relax-Search fixes the k variables with largest Δ_i = |x̄_i − 0.5|, with k = p|U| and p = 0.7 for all synthetic benchmarks. RENS (Algorithm 1) fixes only variables for which the optimal relaxation is already integral, leaving fractional variables free. Thus Relax-Search vs RENS changes two things at once: (i) the relaxation is time-limited/suboptimal instead of optimal, and (ii) the fixing rule is 'top 70% by proximity to integrality' instead of 'fix only integral relaxation values'. The paper attributes the improvement to (i) in the 'Benefits of Suboptimal Relaxation' section, but the sensitivity analysis only varies p within the proposed suboptimal framework. There is no control that solves the relaxation to optimality and then applies the same top-p rounding rule. Consequently, the observed gains could be entirely due to the much smaller sub-MBQP created by fixing 70% of binaries, not to the suboptimal guidance per se. The WFLOP results are out-of-sample but reuse the same p and still cannot separate the two factors. This is the weakest load-bearing assumption: the novelty claim rests on suboptimality, but the experiments do not identify it as the causal mechanism.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two primal heuristics for nonconvex MBQPs, Relax-Search and Cover-Relax-Search, which generalize the RENS and Undercover heuristics. Instead of solving an LP or NLP relaxation to optimality, the methods stop after a short time limit (Tr=20s), compute delta_i = |xbar_i - 0.5| for each binary variable, fix the p=0.7 fraction of variables with the largest delta_i to their rounded values, and solve the resulting sub-MBQP with SCIP. Cover-Relax-Search restricts the candidate fixing set to a minimum vertex cover of the Hessian graph. The methods are evaluated on three synthetic benchmark families (CBQP, CQKP, QMKP) with 500 and 1000 binary variables, and on 100 small and 100 large WFLOP instances built from California offshore wind data. The headline results show that Relax-SearchNLP and, to a lesser extent, Cover-Relax-SearchNLP achieve lower average primal gaps and primal integrals than SCIP-LP-form, RENS+, and Undercover+ at a 60-second cutoff.","tokens_in":13844,"tokens_out":6932,"duration_ms":69102,"significance":"If the reported gains are robust, the paper makes a useful practical contribution: a simple and transferable recipe that improves primal bounds for hard MBQPs within one minute, together with a new uncertain-wind WFLOP benchmark family. The proposed methods have no theoretical performance guarantee, so the contribution is empirical. The key novel claim, that 'suboptimal' relaxation solutions provide better rounding guidance than optimal relaxations, is currently not isolated from the aggressive fixing rule used in the experiments. With the additional controls and reporting requested below, the paper could become a solid contribution to the primal-heuristic literature for quadratic mixed-integer problems.","major_comments":[{"comment":"The section titled 'Benefits of Suboptimal Relaxation' attributes the gains of Relax-Search and Cover-Relax-Search to the use of a time-limited, suboptimal relaxation, but the comparison against RENS and Undercover changes two factors at once. RENS fixes only variables that are integral in the optimal relaxation, whereas Relax-Search fixes p=0.7 of all binary variables by the largest delta_i. Thus the observed improvements could be entirely due to the much smaller sub-MBQP created by fixing 70% of the binaries, rather than to suboptimality of the relaxation. The sensitivity analysis over p is only performed inside the suboptimal framework. I request a control in which the LP and NLP relaxations are solved to optimality (or to a tight tolerance) and then the same p=0.7 top-delta fixing rule is applied. If that control matches Relax-Search, the manuscript's claim about suboptimal guidance is not supported by the current experiments.","section":"Experiments and Analysis, 'Benefits of Suboptimal Relaxation' and Fig. 1"},{"comment":"The baselines RENS+ and Undercover+ are explicitly allowed to spend the remaining time after the heuristic in SCIP branch-and-bound ('we allow SCIP to improve the solution returned by RENS through BnB until reaching the time limit'), but the paper does not state whether the proposed methods also continue branch-and-bound after the sub-MBQP solve. If the proposed methods terminate before the 60-second limit while the baselines exploit all remaining time, the comparison is not symmetric and the primal-integral advantage could reflect time allocation rather than guidance quality. Please state exactly what happens in the proposed pipeline when the sub-MBQP solve finishes before the time limit, and ideally rerun a matched comparison in which all methods either stop at the first heuristic solution or all continue in branch-and-bound for the full time budget.","section":"Setup, Baselines and Computational Setup"},{"comment":"The headline numbers are produced with p=0.7, which was selected from a sensitivity analysis on the same synthetic benchmarks that generate the headline tables; the authors also note that 'the best value of p is different for each benchmark.' This is an in-sample selection, and the WFLOP results, while out-of-sample, reuse the same p. Because the fixing ratio is a central component of the method, please report the per-p averages (at least in an appendix) and clarify which choices of p support the qualitative conclusion. Without this, the reader cannot assess how much of the reported advantage depends on the tuned value of p rather than on the method itself.","section":"Setup, Proposed Methods (p sensitivity)"},{"comment":"The paper uses the word 'significantly' but reports only averaged primal gaps and primal integrals over 100 instances, without standard deviations, confidence intervals, or paired significance tests. Some table entries also weaken the universal claim: in Table 3 (large QMKP), Cover-Relax-SearchLP+ has primal integral 40.74, which is worse than SCIP-LP-form's 37.33 (-9.13%). Please either restrict the headline claim to the specific variants that are consistently best (Relax-SearchNLP and Cover-Relax-SearchNLP) or add statistical tests and dispersion measures that support the word 'significantly' for the broader set of proposed methods.","section":"Results and Discussion, Tables 2 and 3"}],"minor_comments":[{"comment":"The row labeled 'Cover-Relax-SearchLP+' uses a '+' that is not defined and is inconsistent with Table 2's 'Cover-Relax-SearchLP'; please correct the notation or explain the difference.","section":"Table 3"},{"comment":"The statement that 'SCIP uses 0 as the trivial starting solution in all our tested benchmarks' is not correct for the cardinality-constrained CBQP and CQKP instances, where the all-zero vector violates the equality constraint sum_j x_j = K.","section":"Experiments and Analysis, 'Benefits of Suboptimal Relaxation'"},{"comment":"The pseudocode presents Relax-Search and Cover-Relax-Search in one block, but Line 3 (computing the cover) applies only to Cover-Relax-Search; please separate the algorithms or annotate the optional step more clearly.","section":"Algorithm 2"},{"comment":"The x-axis labels such as 'RENSLP' and 'RENSNLP' combined with the caption 'most similar baseline methods' are informal; please define the exact comparison pairs that produce each bar.","section":"Figure 1"},{"comment":"The column 'PD Gap' is not defined; please state whether it is the average SCIP primal-dual gap at 30 minutes and how it is computed for instances where no feasible solution is found.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope for a mathematical-optimization journal and the proposed heuristics are simple and potentially useful. The main weakness is experimental attribution: the title and abstract overstate the role of suboptimality relative to what the current experiments can establish. The requested controls and clarifications (optimal-relaxation plus same-p fixing, symmetric time budgets, per-p sensitivity, and statistical reporting) are feasible within the manuscript's scope and should not require a fundamentally different paper. I would support acceptance after a major revision addressing these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: The heuristic works, and the empirical story is consistent across synthetic and real-world MBQP benchmarks, but the paper's causal claim that suboptimal relaxation drives the gains is not actually tested. The improvement could be from fixing 70% of the binaries, not from the relaxation being suboptimal.\n\nWhat's new: Relax-Search and Cover-Relax-Search are simple extensions of RENS and Undercover—stop the relaxation early, rank variables by distance to 0.5, fix the top p fraction, solve the residual. That combination is not in the RENS/Undercover literature, and it is cheap to implement. The numerical results are consistent and large: Relax-SearchNLP cuts primal integral by 28–95% on synthetic benchmarks and by large margins on the new wind farm instances. The WFLOP data, built from NOW-23 California wind, is a genuine addition, and the sensitivity analysis over p in {0.5, 0.6, 0.7, 0.8, 0.9, 1} is a thoughtful inclusion. The paper is written clearly and the tables are internally consistent.\n\nSoft spots: The biggest one is the confound. RENS fixes only variables that are already integral; Relax-Search fixes the top 70%. So the comparison changes two things at once. The 'Benefits of Suboptimal Relaxation' section attributes the gains to suboptimality, but there is no control that solves the relaxation to optimality and then applies the same top-p fixing rule. The sensitivity analysis varies p only inside the suboptimal framework, so it doesn't separate the two factors. That said, the confound is less damaging than it first looks: for these instances, an 'optimal' relaxation is expensive and often consumes most of the 60s, so early termination is precisely what makes the heuristic useful. The paper should still add the control, or soften the causal language.\n\nTwo more moderate issues. First, no error bars, confidence intervals, or significance tests on 100-instance averages. The differences are large enough that they are probably real, but the reader should be able to check. Second, p is tuned on the same synthetic benchmarks used for the headline numbers; the fact that WFLOP uses the same p and works is reassuring, but a short note on the stability of p across the sensitivity range would help. Also, no code or data is provided, which limits reproducibility.\n\nWho this is for: anyone building primal heuristics for MBQPs, especially in model predictive control or wind farm layout. The paper deserves a serious referee. It will need revisions, mostly to the experimental claims, not to the core algorithm.","headline":"A clean, useful heuristic for MBQPs with a confounded causal claim; still deserves refereeing.","tokens_in":14371,"tokens_out":6173,"would_cite":false,"duration_ms":53004,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","90C11","90C59","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"A time-limited relaxation solution can guide rounding better than the optimal relaxation for mixed binary quadratic programs.","keywords":["mixed binary quadratic programming","primal heuristics","rounding-based heuristics","suboptimal relaxation","RENS","Undercover","wind farm layout optimization","primal integral"],"falsifier":"Run the same comparison on fresh MBQP instances with $p$ chosen on a separate training set and with every method given the same post-heuristic branch-and-bound time; if Relax-SearchNLP no longer achieves the lowest primal integral, the paper's central claim is refuted.","tokens_in":13369,"feed_emoji":"⚡","tokens_out":5708,"duration_ms":52572,"temperature":0.7,"pith_summary":"The paper tries to establish that solving the LP or NLP relaxation of a mixed binary quadratic program only briefly, and using whatever suboptimal solution comes out as rounding guidance, makes two established primal heuristics much more effective. The proposed Relax-Search and Cover-Relax-Search fix the binary variables whose relaxed values lie closest to 0 or 1, then solve the resulting smaller sub-MBQP. Across synthetic benchmarks with 500–1000 binary variables and real-world wind-farm layout instances, the NLP-guided variant reports the lowest average primal gap and primal integral within a 60-second cutoff. If true, this gives practitioners a cheap and transferable way to produce high-quality feasible solutions for hard MBQPs.","feed_headline":"Early-stopped relaxations beat optimal ones in MBQP heuristics","feed_subtitle":"Two RENS/Undercover variants fix near-integral variables and find better feasible solutions within 60 seconds.","key_machinery":"The load-bearing mechanism is the distance-to-integrality rule $\\Delta_i = |\\bar{x}_i - 0.5|$ applied to a candidate set, together with a fixing ratio $p$ that controls how many top variables are fixed. In Relax-Search the candidate set is all binary variables; in Cover-Relax-Search it is the minimum vertex cover of the Hessian graph, computed by solving $\\min \\sum_i \\alpha_i$ subject to $\\alpha_i + \\alpha_j \\geq 1$ for every nonlinear pair. The relaxation is stopped early, and the chosen variables are fixed to $\\lfloor \\bar{x}_i \\rceil$, while the rest are left free in the sub-MBQP. This machinery trades a small loss in relaxation quality for a much larger budget to solve the restricted subproblem, and it deliberately leaves some nonlinear terms or cover variables free rather than fixing everything.","core_discovery":"The central discovery is that a relaxation does not need to be solved to optimality to guide rounding and variable fixing. A suboptimal relaxation, stopped after a 20-second limit or after the first NLP iterate, carries enough information about which binary variables are nearly integral. The proposed methods select the top fraction $p$ of variables with the largest distance from 0.5, fix them to their rounded relaxation values, and optimize a sub-MBQP over the rest. This yields better feasible solutions and lower primal integrals than RENS, which uses the optimal relaxation, and than Undercover, which fixes an entire minimum vertex cover. The NLP relaxation gives the strongest guidance, likely because the LP relaxation of these MBQPs is weak. On wind-farm instances, the best Relax-SearchNLP design reduces expected wind speed losses by 8% relative to the SCIP LP-form baseline, corresponding to a 32% increase in expected power production.","pith_inferences":["Because the only new ingredients are early stopping and distance-based fixing, the same recipe could be transplanted to other rounding-based heuristics, such as feasibility pumps or local branching, and to related problem classes like MIQCPs; the paper does not test this.","The best fixing ratio differs by benchmark, so an adaptive or confidence-based choice of $p$ could outperform the fixed $p = 0.7$; this is a testable extension.","The large wind-farm gains suggest that optimizing wake interactions under uncertain winds rewards sparse, perimeter-favoring layouts, an engineering claim that could be checked against site-specific wake-model validation.","The comparison between LP and NLP guidance on other nonconvex MBQPs could reveal when the weaker LP relaxation is sufficient and when the extra cost of an NLP relaxation pays off."],"forward_implications":["Relax-SearchNLP and Cover-Relax-SearchNLP achieve the lowest average primal gap and primal integral among all tested methods on every synthetic and real-world benchmark.","Stopping the relaxation early is beneficial: the time saved is spent on the sub-MBQP solve, and the result holds across all tested fixing ratios $p \\in \\{0.5, 0.6, 0.7, 0.8, 0.9, 1\\}$.","NLP relaxation, despite being slower, gives better rounding guidance than LP relaxation for these MBQPs, suggesting the LP relaxation is too weak to guide variable fixing.","For wind farm layout optimization under uncertain wind conditions, the method produces sparser turbine layouts with greater inter-turbine spacing, reducing wake losses and increasing expected power production.","Both proposed heuristics are standalone start heuristics that do not require an initial feasible solution, so they can be dropped into a branch-and-bound solver at the root node."],"supporting_citations":[{"why":"Defines RENS, the optimal-relaxation rounding heuristic that Relax-Search extends by replacing the optimal relaxation with a time-limited suboptimal one.","marker":"Berthold 2014b"},{"why":"Defines Undercover and the minimum vertex cover of the Hessian graph that Cover-Relax-Search builds on.","marker":"Berthold and Gleixner 2014"},{"why":"Provides the SCIP solver used for relaxations, cover problems, sub-MBQP solving, and the branch-and-bound baselines.","marker":"Bestuzheva et al. 2021"},{"why":"Defines the primal gap and primal integral metrics used to compare all methods.","marker":"Berthold 2013"},{"why":"Supplies the instance-generation procedure and the linear reformulation approach used for the synthetic MBQP benchmarks.","marker":"Forrester and Hunt-Isaak 2020"},{"why":"Supplies the wind farm layout optimization MBQP formulation that the paper extends to uncertain wind conditions.","marker":"Turner et al. 2014"},{"why":"Supplies the NOW-23 California offshore wind data used to instantiate the real-world WFLOP benchmarks.","marker":"Bodini et al. 2023"}],"fun_headline_variants":["Suboptimal relaxation yields better MBQP primal heuristics","Early-stopped relaxations improve rounding-based MBQP search","Rounding with suboptimal relaxation beats optimal in MBQPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the measured advantage comes from suboptimal relaxation guidance rather than from an uneven time budget: the fixing ratio $p = 0.7$ was tuned on the same synthetic benchmarks used for the headline results, and the baseline heuristics are allowed extra branch-and-bound improvement time after they finish.","fun_headline_variants_meta":{"raw":{"variants":["Suboptimal relaxation yields better MBQP primal heuristics","Early-stopped relaxations improve rounding-based MBQP search","Rounding with suboptimal relaxation beats optimal in MBQPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00025,"raw_usage":{"total_tokens":1570,"prompt_tokens":979,"completion_tokens":591,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":538}},"tokens_in":595,"tokens_out":591,"duration_ms":6794,"temperature":1.0,"reasoning_tokens":538,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:19:53.730653+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same comparison on fresh MBQP instances with $p$ chosen on a separate training set and with every method given the same post-heuristic branch-and-bound time; if Relax-SearchNLP no longer achieves the lowest primal integral, the paper's central claim is refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the SCIP solver used for relaxations, cover problems, sub-MBQP solving, and the branch-and-bound baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the primal gap and primal integral metrics used to compare all methods."},{"cited_title":"J.; and Hunt-Isaak, N","cited_arxiv_id":null,"evidence_quote":"Supplies the instance-generation procedure and the linear reformulation approach used for the synthetic MBQP benchmarks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the wind farm layout optimization MBQP formulation that the paper extends to uncertain wind conditions."},{"cited_title":"K.; Pronk, V.; Castagneri, S.; Purkayastha, A.; Draxl, C.; et al","cited_arxiv_id":null,"evidence_quote":"Supplies the NOW-23 California offshore wind data used to instantiate the real-world WFLOP benchmarks."}],"review_version":1}