Dattorro Convex Optimization of Eternity II

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
An [http://www.eternityii.com Eternity II puzzle] problem formulation <math>A_{}x\!=\!b\,</math> is discussed thoroughly in section 4.6.0.0.15 of online book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization &amp; Euclidean Distance Geometry].&nbsp;
An [http://www.eternityii.com Eternity II puzzle] problem formulation <math>A_{}x\!=\!b\,</math> is discussed thoroughly in section 4.6.0.0.15 of online book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization &amp; Euclidean Distance Geometry].&nbsp;
-
This <math>A\,</math> matrix is obtained by presolving a 864,593 <math>\!\times\!</math> 1,048,576 system.
+
This <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.
This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to this larger system:
This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to this larger system:
-
*<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>\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,
+
*<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 produces dependent rows),
*<math>b\!\in\!\mathbb{R}^{7362}</math>&nbsp;&nbsp; and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math>&nbsp; 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>,
*<math>b\!\in\!\mathbb{R}^{7362}</math>&nbsp;&nbsp; and <math>A\!\in\!\mathbb{R}^{7362\times150638}</math>&nbsp; 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>,
*'''zero_varbs''': row-vector identifying 57,840 columns removed from <math>\,E</math> to make <math>\tilde{E}</math>
*'''zero_varbs''': row-vector identifying 57,840 columns removed from <math>\,E</math> to make <math>\tilde{E}</math>
*'''zero_varbs_cone''': row-vector identifying 53,666 more columns removed from <math>\,E</math> to make <math>\,A</math>;<br> ''i.e.'', 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> ''i.e.'', those columns not belonging to smallest face of <math>\mathcal{K}</math> containing <math>\tilde{\tau}</math>.
-
The following linear program is a very difficult problem:
+
The following linear program is a very difficult problem that remains unsolved:
-
 
+
<center>
<center>
<math>\begin{array}{cl}\mbox{minimize}_x&c^{\rm T}x\\
<math>\begin{array}{cl}\mbox{minimize}_x&c^{\rm T}x\\
Line 15: Line 14:
&x\succeq_{}\mathbf{0}\end{array}</math>
&x\succeq_{}\mathbf{0}\end{array}</math>
</center>
</center>
- 
Matrix <math>A\!\in\!\mathbb{R}^{7362\times150638}</math> is sparse having only 782,087 nonzeros.
Matrix <math>A\!\in\!\mathbb{R}^{7362\times150638}</math> is sparse having only 782,087 nonzeros.
All entries of <math>A\,</math> are integers from the set <math>\{{-1},0,1\}\,</math>.
All entries of <math>A\,</math> are integers from the set <math>\{{-1},0,1\}\,</math>.

Revision as of 04:31, 14 February 2011

An Eternity II puzzle problem formulation LaTeX: A_{}x\!=\!b\, is discussed thoroughly in section 4.6.0.0.15 of online book Convex Optimization & Euclidean Distance Geometry.  This 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 this larger system:

  • 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 known zero variables (removal produces 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}\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;
    i.e., those columns not belonging to smallest face of LaTeX: \mathcal{K} containing LaTeX: \tilde{\tau}.

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

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\,.  Constraints LaTeX: A_{}x\!=\!b\, bound the variable from above by LaTeX: \mathbf{1}. 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.

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