From Daan
Jump to: navigation, search
m
m (So, is this a hard problem?)
(45 intermediate revisions by 2 users not shown)
Line 1: Line 1:
  
==Introduction==
+
==Paper==
  
ASQAS-34 is a perfect rectangle packing problem solved by Braam, Moes, Suilen, Van den Berg and Bhulai in 2016 and earlier (unpublished) by Giovanni Resta. I'm still working on this page, but [http://www.heuristieken.nl/resources/2016Braametal-AlmostSquares.pdf our '''paper''' is here]. I (Daan van den Berg) welcome all feedback you might have. Look me up in the UvA-directory, on LinkedIn or FaceBook.
+
I'm still working on this page, but [http://www.heuristieken.nl/resources/2016Braametal-AlmostSquares.pdf our '''paper''' is here]. I (Daan van den Berg) welcome all feedback you might have. Look me up in the UvA-directory, on LinkedIn or FaceBook.
  
  
==Q&A==
+
==What is ASQAS-34 ?==
 
 
 
<Center>
 
<Center>
{| align="left" | style=" align="top"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
+
{| align="justify" | style=" align="top"; text-align:center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 
|-  
 
|-  
|valign="top"| '''1. What is ASQAS-34 ?'''
+
|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 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).
  
  
ASQAS-34 is a '''Perfect Rectangle Packing Problem'''. In general, rectangle packing problems involve putting some 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 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. 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 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 the second one [[http://mathworld.wolfram.com/PerfectSquareDissection.html begin unsolvable]].
+
|valign="top" |[[Image:Asqas34los2_k.png|frame|This is Asqas-34: consecutive almost-square tiles to be fit in an almost-square frame. There are 5 instances of ASQAS, and ASQAS-34 was the only unsolved instance yet.]]
  
 +
|}
 +
</Center>
  
|valign="top" |[[Image:Asqas34los2_k.png|frame|link=Rush Hour|This is Asqas-34: consecutive almost-square tiles to be fit in an almost-square frame. There are 5 instances of ASQAS, and ASQAS-34 was the only unsolved instance yet.]]
+
==How did you solve it?==
|-
+
<Center>
|valign="top"| '''2. Is it a hard problem?'''
+
{| align="justify" | style=" align="top"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 +
|-  
  
 +
|valign="top"|
  
That's a very difficult question. I don't know. First, we employed every trick we imagined, then wrote the best program we could and STILL it took us 80 full-time calculation days on 1,000 computers. 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 hard, why did it take us so long? I just don't know, to be honest.
+
With 10<SUP>48</SUP> possible configurations, this problem was way too big to solve on a stand-alone computer. So we needed some tricks to nudge the odds in our favour. Such tricks are called "heuristics" if they involve an element of guessing, and "optimizations" if they just speed up the computation process.  
  
  
In general, it's very hard to say whether a problem is hard or not. For some problems (or ''problem instances'', to be precise), we have a few hallmarks that make them easy: small state-space, highly constrained, high solution density, availability of clues or good heuristics. But the absence of these ease-hallmarks still doesn't mean a problem is hard; it means we don't know.  
+
We pryed a valuable heuristic out of a smaller instance, the ASQAS-20. This instance had 54,992 solutions, most of which had borders consisting of large tiles. We figured that this might be true for the ASQAS-34 instance too, so we decided to first make all borders of 12 tiles and this is where we got lucky. Combinatorially speaking, we could make about 10<SUP>21</SUP> of these 12-tile borders. But a single day's work showed that only 4,425,341 borders actually fitted the frame. That's less than 0.00000000001%. So that's a huge improvement, but 4,4 million borders is still a lot. Basically, you still have to solve 4,4 million puzzles of 22 tiles.
  
 +
|valign="top" |[[Image:ASQAS20heur.jpg|frame|link=Heuristieken|Most of ASQAS-20 solutions have large border tiles. In fact, tiles 14x15, 17x18, 18x19, 19x20 are in the border of nearly all 54,992 solutions.]]
  
This problem has none of these hallmarks, or better: we haven't identified any. But since Resta's results and ours are so contradictory, we have absolutely no idea whether this problem is hard or easy. Maybe it depends on how lucky your are, or on where you look.
+
|}
  
 +
</Center>
  
|valign="top" |[[Image:LeuvenSolution_k.jpg|frame|link=Fruitvliegen|Solution found on the server of Cees van Leeuwen's [[http://perceptualdynamics.be lab for perceptual dynamics]] in Leuven. Thanks to Marco Maas for helping out too.]]
+
==How did you solve the 4,4 million borders?==
 +
<Center>
 +
{| align="justify" | style=" align="top"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 
|-
 
|-
|valign="top"| '''2. So how did you solve it?'''
+
|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, 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.
 +
 
  
 +
Such a distributed approach, and especially reserving room for error, is highly recommendable for a project of this scale because stuff goes wrong all the time. You find out you made a mistake somewhere. Some of your files turn out to be corrupt. A remote server is shut down for maintenance. A system administrator keeps killing your processes because your continuously processor-pounding programs look kind of suspicious to him. It's really not worth it to start all over, so count on these things to happen and prepare to restart any given batch at any given time, without affecting the already completed results.
  
First thing we did is take a look at the state space, which is the ensemble of all possible consecutions of the 34 rectangles in both horizontal and vertical positions. Even for this relatively small puzzel, the number of states is 10^48. In the worst case scenario, we would have to check all of them to find a solution. A very fast computer program can generate and check about a million of states per second, but even with a million of these computers, it would take about a billion times a billion times the lifespan of the universe to find a solution. That's too much. That's way too much.
 
  
 +
|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.]]
  
So we needed some tricks to tip the odds in our favour. Such are called "heuristics" if they involve a(n educated) guess and "optimizations" if they just speed up the computation process. We pryed a valuable heuristic out of a smaller instance, the ASQAS-20. This instance had 54,992 solutions (which maybe isn't that many) and most of these had borders consisting mostly of large tiles. We figured that this might be true for ASQAS-34 instance too, so we decided to make all borders of 12 tiles.
+
|}
 +
</Center>
  
 +
==So, is this a hard problem?==
 +
<Center>
 +
{| align="justify" | style=" align="top"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 +
|-
 +
|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 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.
  
(Under Construction)
 
  
 +
In general, it's very hard to say whether a problem is hard or not. For some problems (or ''problem instances'', to be precise), we have a few hallmarks that make them easy: small state-space, highly constrained, high solution density, availability of clues or good heuristics. But the absence of these ease-hallmarks still doesn't mean a problem is hard; it means we don't know.
 +
 +
 +
This problem has none of these hallmarks, or better: we haven't identified any. But since Resta's results and ours are so contradictory, we have absolutely no idea whether this problem is hard or easy. Maybe it depends on how lucky your are, or on where you look.
  
|valign="top" |[[Image:LeuvenSolution_k.jpg|frame|link=Fruitvliegen|Solution found on the server of Cees van Leeuwen's PDL lab @KU Leuven. Thanks to Marco Maas for helping out too.]]
 
|-
 
|valign="top"| '''3. You call yourselves an "VU-UvA consortium". Why is that?'''
 
  
 +
|valign="top" |[[Image:2oplossingen_k.jpg|frame|Left: solution found on the server of [http://perceptualdynamics.be/index.php/staff/133-prof-dr-cees-van-leeuven Cees van Leeuwen]'s [[http://perceptualdynamics.be lab for perceptual dynamics]] in Leuven. Thanks to Marco Maas for helping out too. Right: solution found on the astronomical supercomputer ASTRON in Dwingeloo, The Netherlands]]
  
 +
|}
 +
</Center>
  
Because we are a true VU-UvA collaboration. 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 "minor programming" (www.mprog.nl) where we teach the course of Heuristics. That course was originally built up at the VU back when I worked there so there's another link. Our colleagues teaching Heuristics at VU are 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.
+
==Who are you guys?==
 +
<Center>
 +
{| align="justify" | style=" align="top"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 +
|-
 +
|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 [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.]]
 
|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.]]
Line 59: 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).

Revision as of 21:19, 13 December 2017

Paper

I'm still working on this page, but our paper is here. I (Daan van den Berg) welcome all feedback you might have. Look me up in the UvA-directory, on LinkedIn or FaceBook.


What is ASQAS-34 ?

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. This is somewhat different from consecutive squares-in-squares which has only two instances (1 and 24), the first one being completely trivial and the second one being unsolvable.


This is Asqas-34: consecutive almost-square tiles to be fit in an almost-square frame. There are 5 instances of ASQAS, and ASQAS-34 was the only unsolved instance yet.

How did you solve it?

With 1048 possible configurations, this problem was way too big to solve on a stand-alone computer. So we needed some tricks to nudge the odds in our favour. Such tricks are called "heuristics" if they involve an element of guessing, and "optimizations" if they just speed up the computation process.


We pryed a valuable heuristic out of a smaller instance, the ASQAS-20. This instance had 54,992 solutions, most of which had borders consisting of large tiles. We figured that this might be true for the ASQAS-34 instance too, so we decided to first make all borders of 12 tiles and this is where we got lucky. Combinatorially speaking, we could make about 1021 of these 12-tile borders. But a single day's work showed that only 4,425,341 borders actually fitted the frame. That's less than 0.00000000001%. So that's a huge improvement, but 4,4 million borders is still a lot. Basically, you still have to solve 4,4 million puzzles of 22 tiles.

Most of ASQAS-20 solutions have large border tiles. In fact, tiles 14x15, 17x18, 18x19, 19x20 are in the border of nearly all 54,992 solutions.

How did you solve the 4,4 million borders?

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.


Such a distributed approach, and especially reserving room for error, is highly recommendable for a project of this scale because stuff goes wrong all the time. You find out you made a mistake somewhere. Some of your files turn out to be corrupt. A remote server is shut down for maintenance. A system administrator keeps killing your processes because your continuously processor-pounding programs look kind of suspicious to him. It's really not worth it to start all over, so count on these things to happen and prepare to restart any given batch at any given time, without affecting the already completed results.


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.

So, is this a hard problem?

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


In general, it's very hard to say whether a problem is hard or not. For some problems (or problem instances, to be precise), we have a few hallmarks that make them easy: small state-space, highly constrained, high solution density, availability of clues or good heuristics. But the absence of these ease-hallmarks still doesn't mean a problem is hard; it means we don't know.


This problem has none of these hallmarks, or better: we haven't identified any. But since Resta's results and ours are so contradictory, we have absolutely no idea whether this problem is hard or easy. Maybe it depends on how lucky your are, or on where you look.


Left: solution found on the server of Cees van Leeuwen's [lab for perceptual dynamics] in Leuven. Thanks to Marco Maas for helping out too. Right: solution found on the astronomical supercomputer ASTRON in Dwingeloo, The Netherlands

Who are you guys?

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

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.


More



  • and in Folia (in Dutch).