ASQAS-34

Introduction

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

1. What is ASQAS-34 ? 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 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 [begin 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.
2. Is it a hard problem? That's a very difficult question. I don't know.	Solution found on the server of Cees van Leeuwen's PDL lab @KU Leuven. Thanks to Marco Maas for helping out too.
2. How did you solve it? 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. So we needed some tricks. (Under Construction)	Solution found on the server of Cees van Leeuwen's PDL lab @KU Leuven. Thanks to Marco Maas for helping out too.
3. You call yourself an "VU-UvA consortium". Why is that? 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.	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.