Dattorro Convex Optimization of Eternity II

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 8: Line 8:
*'''zero_varbs_cone''': row-vector identifying 53,666 more columns removed from <math>\,E</math> to make <math>\,A</math>;<br> but only those columns not belonging to smallest face of <math>\mathcal{K}</math> containing <math>\tilde{\tau}</math>.
*'''zero_varbs_cone''': row-vector identifying 53,666 more columns removed from <math>\,E</math> to make <math>\,A</math>;<br> but only those columns not belonging to smallest face of <math>\mathcal{K}</math> containing <math>\tilde{\tau}</math>.
-
I regard the following linear program as a very difficult problem, having spent considerable time with it.
+
The following linear program is a very difficult problem:
<center>
<center>
Line 21: Line 21:
Vector <math>b_{\!}\in\!\{0,1\}^{7362}</math> has only 358 nonzeros.
Vector <math>b_{\!}\in\!\{0,1\}^{7362}</math> has only 358 nonzeros.
-
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 in 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 <math>\mathbf{1}</math>.
+
[[Convex Iteration]] to find a minimal cardinality solution <math>x\,</math>.&nbsp; Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256. Any minimal cardinality solution is binary and solves the Eternity II puzzle. Constraints <math>A_{}x\!=\!b\,</math> bound the variable from above by <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.
+
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 01:20, 14 February 2011

Eternity II puzzle formulation discussed thoroughly in section 4.6.0.0.15 of 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: \mathcal{K}\triangleq\{\tilde{E}^{}x~|~x\!\succeq\!0\},
  • zero_varbs: row-vector identifying 57,840 columns removed from LaTeX: \,E to make LaTeX: \tilde{E}
  • zero_varbs_cone: row-vector identifying 53,666 more columns removed from LaTeX: \,E to make LaTeX: \,A;
    but only those columns not belonging to smallest face of LaTeX: \mathcal{K} containing LaTeX: \tilde{\tau}.

The following linear program is a very difficult problem:

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: 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.

Vector LaTeX: c\, is left unspecified because it is varied later in a Convex Iteration to find a minimal cardinality solution LaTeX: x\,.  Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256. Any minimal cardinality solution is binary and solves the Eternity II puzzle. Constraints LaTeX: A_{}x\!=\!b\, bound the variable from above by LaTeX: \mathbf{1}.

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