Dattorro Convex Optimization of Eternity II

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
-
Eternity II puzzle formulation is discussed in section 4.6.0.0.15 of [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry].
+
Eternity II puzzle formulation is thoroughly discussed in section 4.6.0.0.15 of the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry].
This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains:
This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains:
-
*<math>\,\tau\in\!\mathbb{R}^{11077}</math> and <math>\,E\!\in\!\mathbb{R}^{11077\times262144}</math> is the million column Eternity II matrix with redundant columns removed,
+
*<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 columns removed,
-
*<math>\,\tilde{\tau}\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to zero variables,
+
*<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,
*<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>\{\tilde{E}^{}x~|~x\!\succeq\!0\}</math>
*<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>\{\tilde{E}^{}x~|~x\!\succeq\!0\}</math>
-
I regard the following as a very difficult problem, having spent considerable time with it.
+
I regard the following linear program as a very difficult problem, having spent considerable time with it.
<center>
<center>
<math>\begin{array}{cl}\mbox{minimize}_x&c^{\rm T}x\\
<math>\begin{array}{cl}\mbox{minimize}_x&c^{\rm T}x\\
-
\mbox{subject to}&\tilde{E}\,x=\tilde{\tau}\\
+
\mbox{subject to}&A\,x=b\\
&x\succeq_{}\mathbf{0}\end{array}</math>
&x\succeq_{}\mathbf{0}\end{array}</math>
</center>
</center>
Line 20: Line 20:
Vector <math>c\,</math> is left unspecified because it is varied later as part of a
Vector <math>c\,</math> is left unspecified because it is varied later as part of a
-
[[Convex Iteration]]. &nbsp;
+
[[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 <math>\mathbf{1}</math>.
-
Vector <math>c\,</math> may arbitrarily be set to <math>\mathbf{0}</math> or <math>\mathbf{1}</math>.
+
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.

Revision as of 00:23, 14 February 2011

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:

  • LaTeX: \,\tau\in\!\mathbb{R}^{11077} and LaTeX: \,E\!\in\!\mathbb{R}^{11077\times262144} is the million column Eternity II matrix having redundant columns removed,
  • LaTeX: \,\tilde{\tau}\in\!\mathbb{R}^{10054} and LaTeX: \,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304} has columns removed corresponding to known zero variables,
  • 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: \{\tilde{E}^{}x~|~x\!\succeq\!0\}

I regard the following linear program as a very difficult problem, having spent considerable time with it.

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

Matrix LaTeX: \tilde{E}\!\in\!\mathbb{R}^{10054\times204304} is sparse having only 1,170,516 nonzeros.

All entries of LaTeX: \tilde{E}\, are integers from the set LaTeX: \{{-1},0,1\}\,.   LaTeX: \tilde{\tau}\in\{0,1\}^{10054}.

Vector LaTeX: c\, 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 LaTeX: \mathbf{1}.

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.

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Dattorro_Convex_Optimization_of_Eternity_II"
Personal tools