Pith. sign in

REVIEW 4 major objections 5 minor 29 references

Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A time-limited relaxation solution can guide rounding better than the optimal relaxation for mixed binary quadratic programs.

desk verdict A clean, useful heuristic for MBQPs with a confounded causal claim; still deserves refereeing. read the letter →

arxiv 2501.05052 v2 pith:KZWLSFE7 submitted 2025-01-09 math.OC

Weimin Huang , Natalie M. Isenberg , Jan Drgona , Draguna L Vrabie , Bistra Dilkina This is my paper · ORCID
classification math.OC MSC 90C2090C1190C5990C26
keywords mixedbinaryquadraticprogrammingprimalheuristicsrounding-basedsuboptimalrelaxationRENSUndercoverwindfarmlayoutoptimizationintegral
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Experiments and Analysis, 'Benefits of Suboptimal Relaxation' and Fig. 1] 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.
  2. [Setup, Baselines and Computational Setup] 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.
  3. [Setup, Proposed Methods (p sensitivity)] 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.
  4. [Results and Discussion, Tables 2 and 3] 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.
minor comments (5)
  1. [Table 3] 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.
  2. [Experiments and Analysis, 'Benefits of Suboptimal Relaxation'] 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.
  3. [Algorithm 2] 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.
  4. [Figure 1] 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.
  5. [Table 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's heuristics are evaluated against external benchmarks, and the p=0.7 choice is a tuning concern, not a self-referential derivation.

full rationale

The paper proposes two primal heuristics, Relax-Search and Cover-Relax-Search, defined by Algorithm 2, and evaluates them against RENS, Undercover, and SCIP baselines on synthetic MBQP benchmarks and real-world WFLOP instances. There is no derivation chain whose output reduces to its input: the heuristics are algorithmic procedures whose performance is measured empirically, not derived from assumptions that already contain the target result. The only self-referential element is the selection of the fixing ratio p=0.7 on the same synthetic benchmarks used in the headline tables; however, the paper reports a sensitivity analysis showing the conclusion is valid for all tested p values and then applies p=0.7 to an out-of-sample real-world benchmark, which mitigates rather than creates circularity. The absence of a control that solves the relaxation to optimality and then applies the same top-p fixing rule is a legitimate experimental confound for attributing gains to suboptimality, but it is not a case where a prediction is equivalent to a fitted input, a self-citation carries the argument, or an equation reduces to its own premise. Baselines are drawn from external published algorithms, not from the authors' prior claims. No circular step can be exhibited, so the appropriate finding is no significant circularity.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claims are empirical and rest on solver behavior, benchmark construction, and a small number of hand-chosen algorithmic parameters. No new theoretical entities are postulated. The most important ledger entry is p, which is tuned on the same synthetic benchmark suite used for headline comparisons.

free parameters (3)
  • fixing ratio p = 0.7
    Selected by the authors based on sensitivity analysis with p in {0.5, 0.6, 0.7, 0.8, 0.9, 1} on the same synthetic benchmarks used for the headline results; the best p differs by benchmark. This is a hyperparameter tuned on the evaluation set.
  • relaxation time limit Tr = 20 s
    Hand-chosen cutoff for the LP and NLP relaxation in all Relax-Search and Cover-Relax-Search variants; no sensitivity study of Tr is reported.
  • cover time limit Tc = 1 s
    Hand-chosen cutoff for solving the minimum vertex cover subproblem in Cover-Relax-Search.
assumptions (5)
  • domain assumption SCIP v8.0.1 with the described settings is a correct black-box solver for relaxations and sub-MBQPs.
    All numerical claims depend on SCIP's correctness and on the specific SCIP configurations, which are not fully specified.
  • standard math The LP relaxation of the RLT/McCormick linearization is a valid lower bound for the MBQP.
    Used in the background and for LP-based variants; RLT-0 constraints are standard.
  • standard math Minimum vertex cover of the Hessian graph gives a minimal set of variables whose fixing removes all quadratic terms.
    This is Undercover's cover-set construction and is standard graph theory.
  • domain assumption The NREL NOW-23 simulated wind data and kernel density estimates provide a realistic distribution p(U, theta) for wind farm layout optimization.
    The WFLOP instances are built on this data and the KDE fit; realism of the instances is assumed.
  • domain assumption Minimizing expected wind speed losses in Equation (2) is equivalent to maximizing expected wind farm power production.
    The model omits the constant base power term and assumes power depends monotonically on speed losses; the paper's '32% increase in expected power' claim relies on this mapping.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance." pith.science (2026). https://pith.science/paper/KZWLSFE7

@misc{pith2026250105052,
  author       = {Pith},
  title        = {Pith review of: Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KZWLSFE7}},
  note         = {Machine review of arXiv:2501.05052}
}
read the original abstract

Mixed Binary Quadratic Programs (MBQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and chemical and energy systems. Large-scale MBQPs are challenging to solve with exact algorithms due to the combinatorial search space and nonlinearity. Primal heuristics have been developed to quickly identify high-quality solutions to challenging combinatorial optimization problems. In this paper, we propose an extension for two well-established rounding-based primal heuristics, RENS and Undercover. Instead of using the optimal solution to a relaxation for variable rounding and search as in RENS, we use a suboptimal relaxation solution of the MBQP as the basis for rounding and guidance for searching over a restricted subproblem where a certain percentage of binary variables are free. We apply a similar idea to the Undercover heuristic that fixes a variable cover to the rounded relaxation values. Instead, we relax a subset of the cover variables based on the suboptimal relaxation and search over a larger restricted subproblem. We evaluate our proposed methods on synthetic MBQP benchmarks and real-world wind farm layout optimization problem instances. The results show that our proposed heuristics identify high-quality solutions within a small time limit and significantly reduce the primal gap and primal integral compared to RENS, Undercover, and solvers with additional primal heuristics integrated inside Branch-and-Bound.

Figures

Figures reproduced from arXiv: 2501.05052 by the authors.

Figure 1
Figure 1. Benefits of using suboptimal relaxation as guidance for rounding and variable fixing on standard MBQP benchmarks. % improvement in primal integral at 60s using the proposed methods when compared to their most similar baseline methods. Equations (2)–(4). min X m∈M p (m) U (m)X j∈J X i∈J  d (m) ij 2 yiyj (2) s.t.: X j∈J yj = K (3) yj ∈ {0, 1} ∀j ∈ J (4) Data We use wind data from the National Energy Technol￾ogy Labo… view at source ↗
Figure 2
Figure 2. (a) 100 geographic sites selected from the NOW [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Final turbine layout designs returned by each respective algorithm for a given large WFLOP instance. Grids represent [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 25 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    J.; Hansen, K.; Frandsen, S

    Barthelmie, R. J.; Hansen, K.; Frandsen, S. T.; Rathmann, O.; Schepers, J.; Schlez, W.; Phillips, J.; Rados, K.; Zervos, A.; Politis, E.; et al. 2009. Modelling and measuring flow and wind turbine wakes in large wind farms offshore. Wind Energy: An International Journal for Progress and Applications in Wind Power Conversion Technology, 12(5)

    work page 2009

  4. [4]

    Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; and Mahajan, A. 2013. Mixed-integer nonlinear optimization. Acta Numerica, 22: 1--131

    2013

  5. [5]

    Berthold, T. 2013. Measuring the impact of primal heuristics. Operations Research Letters, 41(6): 611--614

    work page 2013

  6. [6]

    Berthold, T. 2014 a . Primal MINLP heuristics in a nutshell. In Operations Research Proceedings 2013, 23--28. Springer

    work page 2014

  7. [7]

    Berthold, T. 2014 b . RENS: the optimal rounding. Mathematical Programming Computation, 6: 33--54

    work page 2014

  8. [8]

    Berthold, T.; and Gleixner, A. M. 2014. Undercover: a primal MINLP heuristic exploring a largest sub-MIP. Mathematical Programming, 144: 315--346

    work page 2014

Show all 29 references
  1. [9]

    Bertsimas, D.; and Shioda, R. 2009. Algorithm for cardinality-constrained quadratic optimization. Computational Optimization and Applications, 43(1): 1--22

    2009

  2. [10]

    Bestuzheva, K.; Besan c on, M.; Chen, W.-K.; and et al. 2021. The SCIP Optimization Suite 8.0 . Technical report, Optimization Online

    2021

  3. [11]

    K.; Pronk, V.; Castagneri, S.; Purkayastha, A.; Draxl, C.; et al

    Bodini, N.; Optis, M.; Redfern, S.; Rosencrans, D.; Rybchuk, A.; Lundquist, J. K.; Pronk, V.; Castagneri, S.; Purkayastha, A.; Draxl, C.; et al. 2023. The 2023 National Offshore Wind data set (NOW-23). Earth System Science Data Discussions, 2023: 1--57

    2023

  4. [12]

    Bonami, P.; Cornu \'e jols, G.; Lodi, A.; and Margot, F. 2009. A feasibility pump for mixed integer nonlinear programs. Mathematical Programming, 119(2): 331--352

    2009

  5. [13]

    J.; and Hunt-Isaak, N

    Forrester, R. J.; and Hunt-Isaak, N. 2020. Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners. Journal of Applied Mathematics, 2020(1): 5974820

    2020

  6. [14]

    Gomez, A.; Han, S.; and Lozano, L. 2024. Real-time solution of quadratic optimization problems with banded matrices and indicator variables. arXiv preprint arXiv:2405.03051

    2024 arXiv

  7. [15]

    A.; Glover, F.; Alidaee, B.; and Rego, C

    Kochenberger, G. A.; Glover, F.; Alidaee, B.; and Rego, C. 2005. An unconstrained quadratic binary programming approach to the vertex coloring problem. Annals of Operations Research, 139: 229--241

    2005

  8. [16]

    L \'e tocart, L.; Plateau, M.-C.; and Plateau, G. 2014. An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem. Pesquisa Operacional, 34

    2014

  9. [17]

    M.; De Abreu, N

    Loiola, E. M.; De Abreu, N. M. M.; Boaventura-Netto, P. O.; Hahn, P.; and Querido, T. 2007. A survey for the quadratic assignment problem. European journal of operational research, 176(2): 657--690

    2007

  10. [18]

    Misener, R.; and Floudas, C. A. 2013. GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization, 57(1): 3--50

    2013

  11. [19]

    Nannicini, G.; and Belotti, P. 2012. Rounding-based heuristics for nonconvex MINLPs. Mathematical Programming Computation, 4: 1--31

    2012

  12. [20]

    Parpas, P.; and Rustem, B. 2006. Global optimization of the scenario generation and portfolio selection problems. In International Conference on Computational Science and Its Applications, 908--917. Springer

    2006

  13. [21]

    P \'e rez, B.; M \' nguez, R.; and Guanche, R. 2013. Offshore wind farm layout optimization using mathematical programming techniques. Renewable energy, 53: 389--399

    2013

  14. [22]

    D.; Dey, S

    Pia, A. D.; Dey, S. S.; and Molinaro, M. 2017. Mixed-integer quadratic programming is in NP. Mathematical Programming, 162: 225--240

    2017

  15. [23]

    Rebennack, S. 2024. Stable set problem: Branch & cut algorithms. In Encyclopedia of optimization, 1--14. Springer

    2024

  16. [24]

    D.; and Adams, W

    Sherali, H. D.; and Adams, W. P. 2013. A reformulation-linearization technique for solving discrete and continuous nonconvex problems, volume 31. Springer Science & Business Media

    2013

  17. [25]

    C.; and Darvish, M

    Silva, A.; Coelho, L. C.; and Darvish, M. 2021. Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search. European Journal of Operational Research, 292(3): 1066--1084

    2021

  18. [26]

    C.; Klemp, J

    Skamarock, W. C.; Klemp, J. B.; Dudhia, J.; Gill, D. O.; Liu, Z.; Berner, J.; Wang, W.; Powers, J. G.; Duda, M. G.; Barker, D. M.; et al. 2019. A description of the advanced research WRF model version 4. National Center for Atmospheric Research: Boulder, CO, USA, 145(145): 550

    2019

  19. [27]

    Takapoui, R.; Moehle, N.; Boyd, S.; and Bemporad, A. 2020. A simple effective heuristic for embedded mixed-integer quadratic programming. International journal of control, 93(1): 2--12

    2020

  20. [28]

    Turner, S.; Romero, D.; Zhang, P.; Amon, C.; and Chan, T. 2014. A new mathematical programming approach to optimize wind farm layouts. Renewable Energy, 63: 674--680

    2014

  21. [29]

    Zheng, X.; Sun, X.; Li, D.; and Sun, J. 2012. Successive convex approximations to cardinality-constrained quadratic programs: a DC approach. Technical report, Tech. rep., School of Management, Fudan University

    2012

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.