ASQAS-34 - Revision history

MeesterDaan at 12:21, 14 December 2019

2019-12-14T12:21:50Z

MeesterDaan: /* So, is this a hard problem? */

2017-12-13T21:19:30Z

‎So, is this a hard problem?

MeesterDaan at 19:09, 9 December 2017

2017-12-09T19:09:29Z

MeesterDaan: /* So, is this a hard problem? */

2016-12-01T19:05:34Z

‎So, is this a hard problem?

MeesterDaan: /* How did you solve the 4,4 million borders? */

2016-12-01T19:05:04Z

‎How did you solve the 4,4 million borders?

Mark: /* How did you solve the 4,4 million borders? */

2016-11-27T16:18:30Z

‎How did you solve the 4,4 million borders?

Mark: /* What is ASQAS-34 ? */

2016-11-27T16:08:41Z

‎What is ASQAS-34 ?

MeesterDaan: /* So, is this a hard problem? */

2016-11-23T20:11:03Z

‎So, is this a hard problem?

MeesterDaan at 01:07, 23 November 2016

2016-11-23T01:07:41Z

MeesterDaan: /* Who are you guys? */

2016-11-23T01:06:31Z

‎Who are you guys?

← Older revision		Revision as of 12:21, 14 December 2019
Line 85:		Line 85:
	\|}		\|}
	</Center>		</Center>
		+
		+
		+	==Corrections, trivia & Errata ==
		+
		+	* I (Daan van den Berg) am mentioned as the first author of this paper. I am not. I am fourth author, and Florian Braam, Mark Moes and Emiel have done all the ground work in solving this problem, and should be authors one, two and three respectively. I did most of the writing, and Sandjai did the editing and submission.

@@ Line 60: / Line 60: @@
 |-
 |valign="top"|
-That's a very difficult question. I don't know. It took us 55 full-time calculation days on 1,000 computer cores to find only 15 solutions, and we think we had a pretty clever approach. But then there's [http://webhost.services.iit.cnr.it/staff/giovanni.resta/ Giovanni Resta], an Italian guy who solved the exact same problem on his desktop computer. So is Resta brilliant, or just lucky? Probably a little bit of both. Or maybe the problem isn't so hard after all. But if it wasn't that hard, why did it take us 80,000 computer days? I just don't know, to be honest.
+That's a very difficult question. I don't know. It took us 55 full-time calculation days on 1,000 computer cores to find only 15 solutions, and we think we had a pretty clever approach. But then there's [http://webhost.services.iit.cnr.it/staff/giovanni.resta/ Giovanni Resta], an Italian researcher who solved the exact same problem on his desktop computer. So is Resta brilliant, or just lucky? Probably a little bit of both. Or maybe the problem isn't so hard after all. But if it wasn't that hard, why did it take us 80,000 computer days? I just don't know, to be honest.

← Older revision		Revision as of 19:09, 9 December 2017
Line 85:		Line 85:
	\|}		\|}
	</Center>		</Center>
		+
		+
		+	==More==
		+
		+
		+	* So our [http://www.heuristieken.nl/resources/2016Braametal-AlmostSquares.pdf our '''paper''' is here].
		+
		+
		+	* This story also appeared in [https://newscientist.nl/nieuws/informatici-onthullen-oplossing-inpakprobleem/ NewScientist] (in Dutch).
		+
		+
		+	* and in [https://www.folia.nl/wetenschap/106236/uva-vu-informatici-lossen-als-eerst-wiskundig-inpakprobleem-op Folia] (in Dutch).

@@ Line 60: / Line 60: @@
 |-
 |valign="top"|
-That's a very difficult question. I don't know. It took us 80 full-time calculation days on 1,000 computers to find only 15 solutions, and we think we had a pretty clever approach. But then there's [http://webhost.services.iit.cnr.it/staff/giovanni.resta/ Giovanni Resta], an Italian guy who solved the exact same problem on his desktop computer. So is Resta brilliant, or just lucky? Probably a little bit of both. Or maybe the problem isn't so hard after all. But if it wasn't that hard, why did it take us 80,000 computer days? I just don't know, to be honest.
+That's a very difficult question. I don't know. It took us 55 full-time calculation days on 1,000 computer cores to find only 15 solutions, and we think we had a pretty clever approach. But then there's [http://webhost.services.iit.cnr.it/staff/giovanni.resta/ Giovanni Resta], an Italian guy who solved the exact same problem on his desktop computer. So is Resta brilliant, or just lucky? Probably a little bit of both. Or maybe the problem isn't so hard after all. But if it wasn't that hard, why did it take us 80,000 computer days? I just don't know, to be honest.

← Older revision		Revision as of 19:05, 1 December 2016
Line 50:		Line 50:


−	\|valign="top" \|[[Image:solvingInterior_k.gif\|frame\|link=Heuristieken\|A distributed approach: All 12-tiles borders were constructed first, then put in files and distributedly solved by 'supercomputers' around the country. It took 80 days using 1,000 solvers to find all 15 solutions with 12-tile borders.]]	+	\|valign="top" \|[[Image:solvingInterior_k.gif\|frame\|link=Heuristieken\|A distributed approach: All 12-tiles borders were constructed first, then put in files and distributedly solved by 'supercomputers' around the country. It took 55 days using 1,000 solvers to find all 15 solutions with 12-tile borders.]]

	\|}		\|}

@@ Line 44: / Line 44: @@
 |-
 |valign="top"|
-So then we needed to fill up the 4,4 million borders with their of 22 tiles. Combinatorially speaking, even just one puzzle of 22 tiles is too difficult to solve on a single computer, so we still had a serious problem. We programmed an 'interior solver' - a small, efficient computer program capable of puzzling the 22 remaining tiles inside the borders. We put multiple copies of this program on scientific supercomputers throughout The Netherlands, and set up a central server to distribute the borders, in batches of 1,000 over the supercomputers.
+So then we needed to fill up the 4,4 million borders with their of 22 tiles. Combinatorially speaking, even just one puzzle of 22 tiles is too difficult to solve on a single computer, leaving us with a serious challenge. To tackle this we programmed an 'interior solver' - a small, efficient computer program capable of puzzling the 22 remaining tiles inside the borders. We ran several dozen instances of this solver on scientific supercomputers throughout The Netherlands, and set up a central server to distribute the borders, in batches of 1,000 over the supercomputers.
@@ Line 50: / Line 50: @@
-|valign="top" |[[Image:solvingInterior_k.gif|frame|link=Heuristieken|A distributed approach: All 12-tiles borders were constructed first, then put in files, and then distributedly solved by 'supercomputers' around the country. It took 80 days on 1,000 computers to find all 15 solutions with 12-tile borders.]]
+|valign="top" |[[Image:solvingInterior_k.gif|frame|link=Heuristieken|A distributed approach: All 12-tiles borders were constructed first, then put in files and distributedly solved by 'supercomputers' around the country. It took 80 days using 1,000 solvers to find all 15 solutions with 12-tile borders.]]
 |}

@@ Line 10: / Line 10: @@
 |-
 |valign="top"|
-ASQAS-34 is a '''Perfect Rectangle Packing Problem'''. In general, rectangle packing problems involve putting a set of rectangles inside a rectangular frame (often called a "container"). Those problems requires that you find the smallest container possible, hence it is an '''constrained optimization problem'''. In ''perfect'' rectangle packing problems, the frame has exactly the same area of all the rectangles summed up. This means that if it fits, it fits perfectly, without free space or overlap in the rectangles, and a smaller container does not exist. Therefore, perfect rectangle packing problems such as ASQAS-34, are '''constraint satisfaction problems ''' (or equivalently: a decision problem).
+ASQAS-34 is a '''Perfect Rectangle Packing Problem'''. In general, rectangle packing problems involve putting a set of rectangles inside a rectangular frame (often called a "container"). Those problems requires that you find the smallest container possible, hence it is a '''constrained optimization problem'''. In ''perfect'' rectangle packing problems, the frame has exactly the same area of all the rectangles summed up. This means that if it fits, it fits perfectly, without free space or overlap in the rectangles, and a smaller container does not exist. Therefore, perfect rectangle packing problems such as ASQAS-34, are '''constraint satisfaction problems ''' (or equivalently: a decision problem).
-There are five ASQAS problems in total, and they all consist of a serie of rectangles from 1x2, 2x3, 3x4 to NxN+1 which need to be fitted into an almost-square frame. Four ASQAS problems had already been solved (ASQAS-1, ASQAS-3, ASQAS-8 and ASQAS-20). In our paper, we show that ASQAS-34 is the last instance, and that it can be solved also. This is somewhat different from consecutive squares-in-squares, which has only two instances (1 and 24), the first one being completely trivial and [http://mathworld.wolfram.com/PerfectSquareDissection.html the second one being unsolvable].
+There are five ASQAS problems in total, and they all consist of a serie of rectangles from 1x2, 2x3, 3x4 to NxN+1 which need to be fitted into an almost-square frame. Four ASQAS problems had already been solved (ASQAS-1, ASQAS-3, ASQAS-8 and ASQAS-20). In our paper, we show that ASQAS-34 is the last instance, and that it can be solved. This is somewhat different from consecutive squares-in-squares which has only two instances (1 and 24), the first one being completely trivial and [http://mathworld.wolfram.com/PerfectSquareDissection.html the second one being unsolvable].

@@ Line 79: / Line 79: @@
 |-
 |valign="top"|
-We are a genuine VU-UvA consortium. Mark, Florian and Emiel were VU-students when we started this work. They're all professionals now, and Emiel does some occasional work in proofreading Heuristics-reports at the UvA. That's where I work, in the [www.mprog.nl minor programming] where we teach the course of Heuristics. That course was originally built up at the VU back when I worked there with Guszti Eiben and Bushra Malik. Sandjai, our senior author, also works at the VU as a Full Professor Business Analytics. He works on state-space reductions which is exactly the trick we deployed to solve ASQAS-34. So there's connections all over, we're truly a VU-UvA team.
+We are a genuine VU-UvA consortium. Mark, Florian and Emiel were VU-students when we started this work. They're all professionals now, and Emiel does some occasional work in proofreading Heuristics-reports at the UvA. That's where I work, in the [http://www.mprog.nl minor programming] where we teach the course of Heuristics. That course was originally built up at the VU back when I worked there with Guszti Eiben and Bushra Malik. Sandjai, our senior author, also works at the VU as a Full Professor Business Analytics. He works on state-space reductions which is exactly the trick we deployed to solve ASQAS-34. So there's connections all over, we're truly a VU-UvA team.
 |valign="top" |[[Image:thatsUs_k.jpg|frame|link=Heuristieken|Left-to-right: Mark Moes, Emiel Suilen & Florian Braam who did most of the ground work. Bottom right is me (Daan van den Berg), I did coordination and wrote the paper's first draft. Top right is Sandjai Bhulai who also did some writing and took care of the entire publication process. A good team.]]