# Dattorro Convex Optimization of Eternity II

(Difference between revisions)
 Revision as of 11:48, 16 June 2009 (edit)← Previous diff Current revision (17:48, 6 September 2015) (edit) (undo) (31 intermediate revisions not shown.) Line 1: Line 1: - [http://www.convexoptimization.com/TOOLS/E/E_full.mat E996c.mat] + An [http://www.eternityii.ro/try-eternity2-online/index.htm Eternity II puzzle] problem formulation $A_{}x\!=b\,$ is discussed thoroughly in section 4.6.0.0.15 of the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry] which is freely available. + That $A\, matrix is obtained by presolving a sparse 864,593 [itex]\!\times\! 1,048,576 system. + This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that larger system: + *[itex]\tau_{\rm orig}\!\in\mathbb{R}^{864593}$ and $\,E_{\rm orig}\!\in\mathbb{R}^{864593\times1048576}$ is the original Eternity II matrix, + *$\tau\!\in\mathbb{R}^{11077}$ and $\,E\!\in\mathbb{R}^{11077\times262144}$ is the million column Eternity II matrix having redundant rows and columns removed analytically, + *$\tilde{\tau}\!\in\mathbb{R}^{10054}$ and $\,\tilde{E}\!\in\mathbb{R}^{10054\times204304}$ has columns removed corresponding to some known zero variables (removal produced dependent rows), + * $b\!\in\mathbb{R}^{7362}$   and  $A\!\in\mathbb{R}^{7362\times150638}$  has columns removed not in smallest face (containing $\tilde{\tau}$) of polyhedral cone $\mathcal{K}=\{\tilde{E}^{}x~|~x\!\succeq0\}$. -
+                                                         The following linear program is a very difficult problem that remains unsolved:
-                                                         %%% Theorem of the Alternative.                                                                                 +
- clear all + $\begin{array}{cl}\mbox{maximize}_x&z^{\rm T}x\\ - clc + \mbox{subject to}&A\,x=b\\ - load E_small + &x\succeq_{}\mathbf{0}\end{array}$ - %load E_full +
- [m n] = size(E); + Matrix $A\!\in\!\mathbb{R}^{7362\times150638}$ is sparse having only 782,087 nonzeros. - found=[]; + All entries of $A\,$ are integers from the set $\{{-1}\,,\,0\,,\,1\}$. - cvx_quiet('true') + - cvx_precision('low') + Vector $b_{\!}\in\!\{0\,,\,1\}^{7362}$ has only 358 nonzeros. - for i=1:n + - inconclusive = true; + Direction vector $z\,$ is determined by [[Convex Iteration]]: - cvx_begin +
- variable a(n+1,1); + $\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^*\\ - a(1:n) >= 0; + \mbox{subject to}&0\preceq z\preceq\mathbf{1}\\ - -E(:,i) == [E t]*a; + &z^{\rm T}\mathbf{1}=256 - cvx_end + \end{array}$ - if strcmp(cvx_status,'Solved') || strcmp(cvx_status,'Solved/Inaccurate') +
- problem_solved = 1; + These two problems are iterated - inconclusive = false; + to find a minimal cardinality solution x\,.  Constraint $A_{}x\!=b\,$ bounds the variable from above by $\mathbf{1}$.  Any minimal cardinality solution is binary and solves the Eternity II puzzle. - else + The Eternity II puzzle is solved when - cvx_begin +
$- variable z(m,1); + z^{*\rm T\!}x^*=_{}256 - t'*z == 0; +$
- E(:,i)'*z == 1; + Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, [itex]256. - E'*z >= 0; + - cvx_end + - if strcmp(cvx_status,'Solved') || strcmp(cvx_status,'Solved/Inaccurate') + 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, corresponding to the largest entries of iterate [itex]x^*, are declared binary. - problem_solved = 2; + - inconclusive = false; + - end + - end + - fprintf('%6d/%6d',i,n); + - if inconclusive, fprintf(' numeric failure\n'), else fprintf(' problem %d solved\n',problem_solved), end + - end + -
+

## Current revision

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

• $LaTeX: \tau_{\rm orig}\!\in\mathbb{R}^{864593}$ and $LaTeX: \,E_{\rm orig}\!\in\mathbb{R}^{864593\times1048576}$ is the original Eternity II matrix,
• $LaTeX: \tau\!\in\mathbb{R}^{11077}$ and $LaTeX: \,E\!\in\mathbb{R}^{11077\times262144}$ is the million column Eternity II matrix having redundant rows and columns removed analytically,
• $LaTeX: \tilde{\tau}\!\in\mathbb{R}^{10054}$ and $LaTeX: \,\tilde{E}\!\in\mathbb{R}^{10054\times204304}$ has columns removed corresponding to some known zero variables (removal produced dependent rows),
•  $LaTeX: b\!\in\mathbb{R}^{7362}$   and  $LaTeX: A\!\in\mathbb{R}^{7362\times150638}$  has columns removed not in smallest face (containing $LaTeX: \tilde{\tau}$) of polyhedral cone $LaTeX: \mathcal{K}=\{\tilde{E}^{}x~|~x\!\succeq0\}$.

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

$LaTeX: \begin{array}{cl}\mbox{maximize}_x&z^{\rm T}x\\ \mbox{subject to}&A\,x=b\\ &x\succeq_{}\mathbf{0}\end{array}$

Matrix $LaTeX: A\!\in\!\mathbb{R}^{7362\times150638}$ is sparse having only 782,087 nonzeros. All entries of $LaTeX: A\,$ are integers from the set $LaTeX: \{{-1}\,,\,0\,,\,1\}$.

Vector $LaTeX: b_{\!}\in\!\{0\,,\,1\}^{7362}$ has only 358 nonzeros.

Direction vector $LaTeX: z\,$ is determined by Convex Iteration:

$LaTeX: \begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^*\\ \mbox{subject to}&0\preceq z\preceq\mathbf{1}\\ &z^{\rm T}\mathbf{1}=256 \end{array}$

These two problems are iterated to find a minimal cardinality solution $LaTeX: x\,$.  Constraint $LaTeX: A_{}x\!=b\,$ bounds the variable from above by $LaTeX: \mathbf{1}$.  Any minimal cardinality solution is binary and solves the Eternity II puzzle. The Eternity II puzzle is solved when

$LaTeX:

z^{*\rm T\!}x^*=_{}256

$

Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, $LaTeX: 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, corresponding to the largest entries of iterate $LaTeX: x^*$, are declared binary.