Metraipolis › archive › dc_66109a2941ea
Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning — arXiv:2611.04230
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04230
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T18:34:28.620Z
- SHA-256 of the archived text
3182bd721e19d76d5da00070e8e14cadcaa4113b28d6e176050def59ac59c0bd- Stable URL of this page
https://metraipolis.com/documento/dc_66109a2941ea
How to cite
Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning — arXiv:2611.04230 — arXiv (en), https://arxiv.org/abs/2611.04230 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_66109a2941ea (Metraipolis archive dc_66109a2941ea, sha256 3182bd721e19d76d5da00070e8e14cadcaa4113b28d6e176050def59ac59c0bd)
BibTeX
@misc{dc66109a2941ea,
title = {Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning — arXiv:2611.04230},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04230},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_66109a2941ea; sha256 3182bd721e19d76d5da00070e8e14cadcaa4113b28d6e176050def59ac59c0bd},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04230. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We present an exact computational proof that the frozen QPLIB_2096 instance has global minimum 7,025,720. The solution and certification approach was explored and refined through ZiYor, a self-evolving AI system. The authors provide the mathematical account and exact validation reported here. The original formulation has 300 binary variables, 6,900 triangle inequalities, and 25 nonconvex quadratic constraints. A coefficient-level reconstruction identifies its variables with the unordered pairs of 25 items. The triangle inequalities encode partitions, while each quadratic constraint becomes a bound on the total weight of edges incident to one partition block. This yields a set-partitioning formulation over all capacity-feasible blocks, with a separate edge-cost graph determining the objective. Exact enumeration examines 245,505 subsets of sizes one through six and finds 14,981 feasible blocks. Every six-element subset is infeasible; nonnegative capacity weights exclude all larger blocks. An integer price vector satisfies the dual inequality for every feasible block and has sum 2,229,456. Subtracting this sum from the total objective edge cost 9,255,176 gives a lower bound of 7,025,720, attained by the supplied six-block partition. Fresh solver-free checks validate the candidate against both frozen model formats and verify the certificate. The result is an instance-specific optimality proof with an exact primal and dual witness; no cross-instance performance conclusion is drawn. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2611.04230 — 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-11-04T18:32:37.287Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).