Metraipolis › archive › dc_7c72d6840cd6
Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations — arXiv:2610.11154
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.11154
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:27:59.832Z
- SHA-256 of the archived text
4b93f57abc24e6c32146362129d127baeb3bd8763d4e1c300db415404a6c7966- Stable URL of this page
https://metraipolis.com/documento/dc_7c72d6840cd6
How to cite
Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations — arXiv:2610.11154 — arXiv (en), https://arxiv.org/abs/2610.11154 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7c72d6840cd6 (Metraipolis archive dc_7c72d6840cd6, sha256 4b93f57abc24e6c32146362129d127baeb3bd8763d4e1c300db415404a6c7966)
BibTeX
@misc{dc7c72d6840cd6,
title = {Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations — arXiv:2610.11154},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.11154},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7c72d6840cd6; sha256 4b93f57abc24e6c32146362129d127baeb3bd8763d4e1c300db415404a6c7966},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11154. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2610.11154 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:52:31.587Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).