Exact proof finds global minimum for complex partition problem

Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning

Artificial Intelligence

Summary

This paper solves a difficult math puzzle called QPLIB_2096, which involves dividing items into groups to get the best total score. The authors used an AI system to help find and check the solution exactly. They turned the problem into a special kind of puzzle about grouping items with certain restrictions and costs. By carefully checking all possible groups within size limits, they confirmed the best total score is 7,025,720 and proved no better answer exists. Their work gives a precise proof for this instance without relying on guesswork or incomplete methods.

What this means in practice

Authors

Jingyang Du, Zixiong Yi, Yang Shen

Abstract

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.