(→How did you solve the 4,4 million borders?) 
MeesterDaan (talk  contribs) (→How did you solve the 4,4 million borders?) 

Line 50:  Line 50:  
−  valign="top" [[Image:solvingInterior_k.gifframelink=HeuristiekenA distributed approach: All 12tiles borders were constructed first, then put in files and distributedly solved by 'supercomputers' around the country. It took  +  valign="top" [[Image:solvingInterior_k.gifframelink=HeuristiekenA distributed approach: All 12tiles 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 12tile borders.]] 
}  } 
Revision as of 22:05, 1 December 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, 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.

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. 