Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
Abstract
We develop MIQCR-FR, a framework for exact convex reformulation from facially reduced semidefinite relaxations of equality-constrained binary quadratic problems. Standard mixed-integer quadratic convex reformulation (MIQCR) uses dual multipliers of the original relaxation. Facial reduction (FR) reduces the semidefinite matrix order, but recovery of the original dual multipliers is not guaranteed in general. For this class of problems, we identify how retaining the linear equalities and their products with each binary variable enables this recovery. An established dual recovery formula gives an explicit extension of every feasible solution of the reduced dual to the original dual, preserving its bound. For approximate multiplier estimates, we give a spectral shift restoring dual feasibility and two constructions optimizing different bounds within a restricted multiplier family. Maximizing the dual bound yields a trust-region subproblem; maximizing the continuous MIQCR bound requires only a reduced eigenvalue calculation. The latter construction enforces convexity directly, rather than full dual feasibility. We implement it using multiplier estimates from the alternating direction method of multipliers (ADMM). On 431 instances from six problem families, the complete method certifies 296 optima, compared with 156 for the conic-bundle method MIQCR-CB and 187 for direct Gurobi under a common time budget.
Related
- A Bilevel Market Equilibrium Model for Natural Gas Pipeline Network Operations: Convex Relaxations and Single-level Reformulations
- Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
- Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations
- Contextual Distributionally Robust Chance-Constrained Programs: Exact Reformulations and Valid Inequalities
- On Completely Positive and Semidefinite Programs for Moment Bounds on Maximum of Random Quadratics
BibTeX
@misc{hu2026exact,
title = {{Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations}},
author = {Hao Hu and Mingming Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11154},
eprint = {2610.11154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11154},
}
RIS
TY - UNPB
TI - Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
AU - Hao Hu
AU - Mingming Xu
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11154
UR - https://arxiv.org/abs/2610.11154
AB - We develop MIQCR-FR, a framework for exact convex reformulation from facially reduced semidefinite relaxations of equality-constrained binary quadratic problems. Standard mixed-integer quadratic convex reformulation (MIQCR) uses dual multipliers of the original relaxation. Facial reduction (FR) reduces the semidefinite matrix order, but recovery of the original dual multipliers is not guaranteed in general. For this class of problems, we identify how retaining the linear equalities and their products with each binary variable enables this recovery. An established dual recovery formula gives an explicit extension of every feasible solution of the reduced dual to the original dual, preserving its bound. For approximate multiplier estimates, we give a spectral shift restoring dual feasibility and two constructions optimizing different bounds within a restricted multiplier family. Maximizing the dual bound yields a trust-region subproblem; maximizing the continuous MIQCR bound requires only a reduced eigenvalue calculation. The latter construction enforces convexity directly, rather than full dual feasibility. We implement it using multiplier estimates from the alternating direction method of multipliers (ADMM). On 431 instances from six problem families, the complete method certifies 296 optima, compared with 156 for the conic-bundle method MIQCR-CB and 187 for direct Gurobi under a common time budget.
ER -