Solving Rectangle-Fit problem

This repository focuses on solving the well-known problem of Rectangle-Fit. Problem is known to be NP-hard, so a meta-heuristic approach called Nelder-Mead method is used to find a near-optimal solution.

Problem instance

Since packing problems like this problem can have many formulations & variants, I provide an exact problem description:

Given n rectangles of width w and height h (w. h are real numbers), we want to find a packing of those rectangles into a bigger bounding rectangle which minimizes bounding rectangle area. Rectangles can't overlap & they need to be within the bounding rectangle area. We're interested in a minimal area that can be achieved for a given set of rectangles. Alternatively, W, H can be supplied - which are dimensions of bounding rectangle.

Idea of solution

Minimalisation problem stated that way cannot be solved using typical linear programming techniques - at least without adding additional constraints. But there are effective (O(n) or O(n * log(n)) algorithms finding an approximate result for ribbon-fit problem. A ribbon is a sub-surface of width W where we try to fit rectangles (similar constraints as in Rectangle-Fit problem), minimizing the y position (effective height) of the top-most corner of rectangle placed in that way.

That may find a good approximate for bounding rectangle area I'm looking for. But we don't know what W to choose to find an optimal bounding rectangle. Here, meta-heuristics come into play. Nelder-Mead method is used to traverse solution space, finding optimal W (using meta-heuristics) and H (using heuristic algorithm from bounding-ribbon problem).

Installation

To use this code, you need to have Python (2.x) & SciPy installed. The easiest way to have an environment for so-called scientific Python is to use one of ready-made solutions like Anaconda Python. You can also install scipy on your local Python - see here for details.

Then just clone the repo:

git clone https://github.com/Killavus/fitting-rectangles.git
cd fitting-rectangles

Usage

There are two ways to use the code. Heuristics available are naive, nfdh, ffdh, rf:

• test mode, where you can run one of bounding-ribbon heuristics with a given, set W:

python main.py -t 20.0 nfdh

Program then waits for your input, which are pairs of width & height for rectangles. You end entering input by emitting EOF (ctrl + d in majority of shells). So for example:

2.0 1.0
3.0 1.5
2.34 2.33
<EOF>

is a valid input. You can use < to easily feed file contents to this script:

python main.py -t 5.0 nfdh < test/simple1.in

• normal mode, where Nelder-Mead is used to find the solution:

python main.py nfdh < test/simple1.in

Heuristics overview:

• naive - the simplest one. Go one-by-one through rectangles, trying to fit them right after the previously placed one. If it's not possible, place the new rectangle at the top of the previous 'level'. For data (w, h): (3.0, 1.0), (2.0, 1.0), (1.0, 1.0), W: 4, the result will be (x, y): (0.0, 0.0), (0.0, 1.0), (1.0, 1.0). (no approximation error upper bound)
• nfdh - next-fit decreasing height - very similar to naive, but we sort rectangles by decreasing height first. (at most 3 times worse than an optimal solution)
• ffdh - first-fit decreasing height- idea is like innfdh`, but with every rectangle we try to fit it to every level "opened" before. So if there's W: 4 and (3.0, 3.0) rectangle on (0, 0) position, (1.0, 1.0) will be added to (3.0, 0.0) position, 'filling' the hole. (at most 2,7-times worse than an optimal solution)
• rf - reverse-fit. This one gives the best solution, but it's the most complex one. It is described in this paper. (at most 2 times worse than an optimal solution).