Metraipolis › archive › dc_72a0e4e321f7
Convexification of mixed-integer quadratic optimization via decision diagrams — arXiv:2608.22815
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.22815
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T08:25:43.794Z
- SHA-256 of the archived text
e72669abe99eb62023e9f00632ee93fcf93c6203e16530f9121a1a41a3a11224- Stable URL of this page
https://metraipolis.com/documento/dc_72a0e4e321f7
How to cite
Convexification of mixed-integer quadratic optimization via decision diagrams — arXiv:2608.22815 — arXiv (en), https://arxiv.org/abs/2608.22815 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_72a0e4e321f7 (Metraipolis archive dc_72a0e4e321f7, sha256 e72669abe99eb62023e9f00632ee93fcf93c6203e16530f9121a1a41a3a11224)
BibTeX
@misc{dc72a0e4e321f7,
title = {Convexification of mixed-integer quadratic optimization via decision diagrams — arXiv:2608.22815},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.22815},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_72a0e4e321f7; sha256 e72669abe99eb62023e9f00632ee93fcf93c6203e16530f9121a1a41a3a11224},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.22815. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study mixed-integer quadratic optimization (MIQO) problems with indicator variables. We propose a unified framework, based on decision diagrams, that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set. The construction applies to arbitrary quadratics and to any combinatorial constraints admitting a tractable dynamic programming representation. The resulting diagrams and the ensuing convex hull descriptions are of polynomial size when the quadratic is low-rank, or when the support graph of the Hessian or of its inverse is a tree, recovering and generalizing several results from the literature. For structured sparse and inverse-sparse quadratics, we show that approximate decision diagrams have size linear in the dimension while yielding solutions with arbitrarily low optimality gap. Computational experiments demonstrate the effectiveness of the proposed approach. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2608.22815 — 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-18T08:18:05.702Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).