Papers for

software engineers in optimization

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Exact proof finds global minimum for complex partition problem

Exact Optimality Certification of QPLIB 2096 through Complete Set Partitioning

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.

Tue 3 NovArtificial Intelligence
The gist
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.
Open → 2611.04230v1

Comparing thousands of chessboard colorings reveals key solver tricks

Coloring Queens with Thousands of Encodings

Abstract: In The Art of Computer Programming, Knuth benchmarked 10 encoding techniques for computing the chromatic number of the queen's graph: the minimum number of colors needed to color the squares of an $n \times n$ chessboard so that no two squares sharing a row, column, or diagonal receive the same color. In this paper, we extend his analysis much further by comparing thousands of encodings for the same problem, which allows us to identify additional factors that are important for solver performance. We obtain 1584 encodings for this problem by varying (a) the constraints that encode which color is assigned to each cell, (b) the constraints that forbid the same color appearing in a row, column, or diagonal line, and (c) the symmetry-breaking constraints. We find that the three most impactful encoding factors are (i) the choice of symmetry-breaking constraints, (ii) enabling so-called clique hints, and (iii) enforcing that each cell is assigned exactly one color through blocked clauses. Furthermore, while Knuth proposed clique hints as an advantage of the order encoding, we show in fact that they can be effectively employed for the one-hot encoding as well.

Wed 23 SeptLogic in Computer Science
The gist
The problem is to color a chessboard so no two squares in the same row, column, or diagonal have the same color, using the fewest colors possible. The authors studied over a thousand ways to set up this problem for computer solvers, examining how different rules and hints affect solving speed. They found that the choices for breaking symmetrical solutions, adding special clues called clique hints, and strict rules assigning colors to squares have the biggest impact. They also showed some hints work well beyond the specific method Knuth originally suggested.
Open → 2609.27674v1