# Dattorro Convex Optimization of Eternity II

### From Wikimization

Line 4: | Line 4: | ||

*<math>\tau\!\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix having redundant rows and columns removed analytically, | *<math>\tau\!\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix having redundant rows and columns removed analytically, | ||

*<math>\tilde{\tau}\!\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to known zero variables (removal produced dependent rows), | *<math>\tilde{\tau}\!\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to known zero variables (removal produced dependent rows), | ||

- | *<math>b\!\in\!\mathbb{R}^{7362}</math> and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math> has columns removed not in smallest face (containing <math>\tilde{\tau}</math>) of polyhedral cone <math>\mathcal{K}\triangleq\{\tilde{E}^{}x~|~x\!\succeq\!0\ | + | *<math>b\!\in\!\mathbb{R}^{7362}</math> and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math> has columns removed not in smallest face (containing <math>\tilde{\tau}</math>) of polyhedral cone <math>\mathcal{K}\triangleq\{\tilde{E}^{}x~|~x\!\succeq\!0\}</math>. |

- | + | ||

- | + | ||

The following linear program is a very difficult problem that remains unsolved: | The following linear program is a very difficult problem that remains unsolved: |

## Revision as of 00:48, 23 February 2011

An Eternity II puzzle problem formulation is discussed thoroughly in section 4.6.0.0.15 of the book Convex Optimization & Euclidean Distance Geometry which is freely available. That matrix is obtained by presolving a sparse 864,593 1,048,576 system. This Matlab binary contains three successive reductions, each equivalent to that larger system:

- and is the million column Eternity II matrix having redundant rows and columns removed analytically,
- and has columns removed corresponding to known zero variables (removal produced dependent rows),
- and has columns removed not in smallest face (containing ) of polyhedral cone .

The following linear program is a very difficult problem that remains unsolved:

Matrix is sparse having only 782,087 nonzeros. All entries of are integers from the set .

Vector has only 358 nonzeros.

Vector is left unspecified because it is varied later in a Convex Iteration to find a minimal cardinality solution . Constraints bound the variable from above by . Any minimal cardinality solution is binary and solves the Eternity II puzzle. Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.

Comment: 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 here except 256 variables are declared binary.