MeesterDaan (talk  contribs) (→So, is this a hard problem?) 
m (→What is ASQAS34 ?) 

Line 10:  Line 10:  
    
valign="top"  valign="top"  
−  ASQAS34 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  +  ASQAS34 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 ASQAS34, 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 almostsquare frame. Four ASQAS problems had already been solved (ASQAS1, ASQAS3, ASQAS8 and ASQAS20). In our paper, we show that ASQAS34 is the last instance, and that it can be solved  +  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 almostsquare frame. Four ASQAS problems had already been solved (ASQAS1, ASQAS3, ASQAS8 and ASQAS20). In our paper, we show that ASQAS34 is the last instance, and that it can be solved. This is somewhat different from consecutive squaresinsquares 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]. 
Revision as of 18:08, 27 November 2016
Contents
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 UvAdirectory, on LinkedIn or FaceBook.
What is ASQAS34 ?
ASQAS34 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 ASQAS34, are constraint satisfaction problems (or equivalently: a decision problem).

How did you solve it?
With 10^{48} possible configurations, this problem was way too big to solve on a standalone 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.

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, 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, is this a hard problem?
That's a very difficult question. I don't know. It took us 80 fulltime calculation days on 1,000 computers to find only 15 solutions, and we think we had a pretty clever approach. But then there's 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.

Who are you guys?
We are a genuine VUUvA consortium. Mark, Florian and Emiel were VUstudents when we started this work. They're all professionals now, and Emiel does some occasional work in proofreading Heuristicsreports 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 statespace reductions which is exactly the trick we deployed to solve ASQAS34. So there's connections all over, we're truly a VUUvA team. 