Dattorro Convex Optimization of Eternity II - Revision history

Ranjelin at 21:28, 16 January 2026

Ranjelin — Fri, 16 Jan 2026 21:28:41 GMT

←Older revision		Revision as of 21:28, 16 January 2026
Line 1:		Line 1:
-	An [http://www.eternityii.ro/try-eternity2-online/index.htm Eternity II puzzle] problem formulation <math>A_{}x\!=b\,</math> 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.	+	An [http://www.eternityii.ro/try-eternity2-online/index.htm Eternity II puzzle] problem formulation <math>A_{}x\!=b\,</math> is discussed thoroughly in section 4.8 of the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry] which is freely available.
	That <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.		That <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 that larger system:		This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that larger system:

Ranjelin at 00:48, 7 September 2015

Ranjelin — Mon, 07 Sep 2015 00:48:34 GMT

←Older revision		Revision as of 00:48, 7 September 2015
Line 5:		Line 5:
	*<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 some 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 some 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}=\{\tilde{E}^{}x~\|~x\!\succeq0\}</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>\mathcal{K}=\{\tilde{E}^{}x~\|~x\!\succeq0\}</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:

Ranjelin at 00:07, 7 September 2015

Ranjelin — Mon, 07 Sep 2015 00:07:42 GMT

←Older revision		Revision as of 00:07, 7 September 2015
Line 14:		Line 14:
	</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>.

	Vector <math>b_{\!}\in\!\{0\,,\,1\}^{7362}</math> has only 358 nonzeros.		Vector <math>b_{\!}\in\!\{0\,,\,1\}^{7362}</math> has only 358 nonzeros.
Line 31:		Line 31:
	z^{\rm T\!}x^=_{}256		z^{\rm T\!}x^=_{}256
	</math></center>		</math></center>
-	Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.	+	Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, <math>256</math>.


	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 <math>x^*</math>, are declared binary.		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 <math>x^*</math>, are declared binary.

Ranjelin at 00:05, 7 September 2015

Ranjelin — Mon, 07 Sep 2015 00:05:47 GMT

Ranjelin at 00:01, 7 September 2015

Ranjelin — Mon, 07 Sep 2015 00:01:35 GMT

←Older revision		Revision as of 00:01, 7 September 2015
Line 2:		Line 2:
	That <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.		That <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 that larger system:		This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that 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 rows and columns removed analytically,	+	*<math>\tau_{\rm orig}\!\in\mathbb{R}^{864593}</math> and <math>\,E_{\rm orig}\!\in\mathbb{R}^{864593\times1048576}</math> is the original Eternity II matrix
-	*<math>\tilde{\tau}\!\in\!\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\!\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to some known zero variables (removal produced dependent rows),	+	*<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>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}=\{\tilde{E}^{}x~\|~x\!\succeq0\}</math>.	+	*<math>\tilde{\tau}\!\in\mathbb{R}^{10054}</math> and <math>\,\tilde{E}\!\in\mathbb{R}^{10054\times204304}</math> has columns removed corresponding to some 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}=\{\tilde{E}^{}x~\|~x\!\succeq0\}</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:

Dattorro at 05:32, 14 November 2012

Dattorro — Wed, 14 Nov 2012 05:32:31 GMT

←Older revision		Revision as of 05:32, 14 November 2012
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 the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry] which is freely available.	+	An [http://www.eternityii.ro/try-eternity2-online/index.htm Eternity II puzzle] problem formulation <math>A_{}x\!=b\,</math> 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 <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.		That <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 that larger system:		This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that larger system:

Ranjelin at 05:51, 5 December 2011

Ranjelin — Mon, 05 Dec 2011 05:51:43 GMT

Ranjelin at 19:56, 24 November 2011

Ranjelin — Thu, 24 Nov 2011 19:56:46 GMT

←Older revision		Revision as of 19:56, 24 November 2011
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 some 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 some 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>.	+	*<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}=\{\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:
Line 19:		Line 19:
	Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:		Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:
	<center>		<center>
-	<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^~~\star~~\\	+	<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^*\\
	\mbox{subject to}&0\preceq z\preceq\mathbf{1}\\		\mbox{subject to}&0\preceq z\preceq\mathbf{1}\\
	&z^{\rm T}\mathbf{1}=256		&z^{\rm T}\mathbf{1}=256
Line 28:		Line 28:
	The Eternity II puzzle is solved when		The Eternity II puzzle is solved when
	<center><math>		<center><math>
-	z^{~~\star~~\rm T\!}x^~~\star\triangleq_~~{}256	+	z^{\rm T\!}x^=_{}256
	</math></center>		</math></center>
	Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256.		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, corresponding to the largest entries of iterate <math>x^~~\star~~</math>, are declared binary.	+	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 <math>x^*</math>, are declared binary.

Dattorro at 12:22, 23 February 2011

Dattorro — Wed, 23 Feb 2011 12:22:54 GMT

←Older revision		Revision as of 12:22, 23 February 2011
Line 25:		Line 25:
	</center>		</center>
	These two problems are iterated		These two problems are iterated
-	to find a minimal cardinality solution <math>x\,</math>.  ~~Constraints~~ <math>A_{}x\!=\!b\,</math> ~~bound~~ the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.	+	to find a minimal cardinality solution <math>x\,</math>.  Constraint <math>A_{}x\!=\!b\,</math> bounds the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.
	The Eternity II puzzle is solved when		The Eternity II puzzle is solved when
	<center><math>		<center><math>

Dattorro at 11:24, 23 February 2011

Dattorro — Wed, 23 Feb 2011 11:24:49 GMT

←Older revision		Revision as of 11:24, 23 February 2011
Line 17:		Line 17:
	Vector <math>b_{\!}\in\!\{0,1\}^{7362}</math> has only 358 nonzeros.		Vector <math>b_{\!}\in\!\{0,1\}^{7362}</math> has only 358 nonzeros.

-	Direction vector <math>z\,</math> is determined by	+	Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:
	<center>		<center>
	<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^\star\\		<math>\begin{array}{rl}\mbox{maximize}_z&z^{\rm T\!}x^\star\\
Line 24:		Line 24:
	\end{array}</math>		\end{array}</math>
	</center>		</center>
-	These two problems are iterated ~~([[Convex Iteration]])~~	+	These two problems are iterated
	to find a minimal cardinality solution <math>x\,</math>.  Constraints <math>A_{}x\!=\!b\,</math> bound the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.		to find a minimal cardinality solution <math>x\,</math>.  Constraints <math>A_{}x\!=\!b\,</math> bound the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.
	The Eternity II puzzle is solved when		The Eternity II puzzle is solved when

←Older revision		Revision as of 00:05, 7 September 2015
Line 2:		Line 2:
	That <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.		That <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 that larger system:		This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that larger system:
-	*<math>\tau_{\rm orig}\!\in\mathbb{R}^{864593}</math> and <math>\,E_{\rm orig}\!\in\mathbb{R}^{864593\times1048576}</math> is the original Eternity II matrix	+	*<math>\tau_{\rm orig}\!\in\mathbb{R}^{864593}</math> and <math>\,E_{\rm orig}\!\in\mathbb{R}^{864593\times1048576}</math> is the original Eternity II matrix,
	*<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 some 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 some known zero variables (removal produced dependent rows),
Line 16:		Line 16:
	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>.

-	Vector <math>b_{\!}\in\!\{0,1\}^{7362}</math> has only 358 nonzeros.	+	Vector <math>b_{\!}\in\!\{0\,,\,1\}^{7362}</math> has only 358 nonzeros.

	Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:		Direction vector <math>z\,</math> is determined by [[Convex Iteration]]:
Line 26:		Line 26:
	</center>		</center>
	These two problems are iterated		These two problems are iterated
-	to find a minimal cardinality solution <math>x\,</math>.  Constraint <math>A_{}x\!=b\,</math> bounds the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.	+	to find a minimal cardinality solution <math>x\,</math>.  Constraint <math>A_{}x\!=b\,</math> bounds the variable from above by <math>\mathbf{1}</math>.  Any minimal cardinality solution is binary and solves the Eternity II puzzle.
	The Eternity II puzzle is solved when		The Eternity II puzzle is solved when
	<center><math>		<center><math>

←Older revision		Revision as of 05:51, 5 December 2011
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 the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry] which is freely available.	+	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 the book [http://meboo.convexoptimization.com/Meboo.html Convex Optimization & Euclidean Distance Geometry] which is freely available.
	That <math>A\,</math> matrix is obtained by presolving a sparse 864,593 <math>\!\times\!</math> 1,048,576 system.		That <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 that larger system:		This [http://www.convexoptimization.com/TOOLS/EternityII.mat Matlab binary] contains three successive reductions, each equivalent to that 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 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 some 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 some 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}=\{\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>\mathcal{K}=\{\tilde{E}^{}x~\|~x\!\succeq0\}</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:
Line 25:		Line 25:
	</center>		</center>
	These two problems are iterated		These two problems are iterated
-	to find a minimal cardinality solution <math>x\,</math>.  Constraint <math>A_{}x\!=\!b\,</math> bounds the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.	+	to find a minimal cardinality solution <math>x\,</math>.  Constraint <math>A_{}x\!=b\,</math> bounds the variable from above by <math>\mathbf{1}</math>. Any minimal cardinality solution is binary and solves the Eternity II puzzle.
	The Eternity II puzzle is solved when		The Eternity II puzzle is solved when
	<center><math>		<center><math>