Dattorro Convex Optimization of Eternity II
From Wikimization
Eternity II puzzle formulation is thoroughly discussed in section 4.6.0.0.15 of the book Convex Optimization & Euclidean Distance Geometry.
This Matlab binary contains:
- and is the million column Eternity II matrix having redundant columns removed,
- and has columns removed corresponding to known zero variables,
- and has columns removed not in smallest face (containing ) of polyhedral cone
I regard the following linear program as a very difficult problem, having spent considerable time with it.
Matrix is sparse having only 1,170,516 nonzeros.
All entries of are integers from the set . .
Vector is left unspecified because it is varied later as part of a Convex Iteration to find a minimal cardinality solution. The minimal cardinality of Eternity II is equal to number of puzzle pieces, 256. Any minimal cardinality solution is binary and solves the Eternity II puzzle. The constraints bound the variable from above by .
I was astonished to discover that the technique, convex iteration, requires no modification (and works very well) when applied instead to mixed integer programming (MIP, not discussed in book). There is no modification to the linear program statement except 256 variables are declared binary.