secnot/rectpack

Is there a way choose the bins among a greater set of bins to pack the rectangles with the best fitness?

BeAntares opened this issue · 2 comments

BeAntares commented

I have n types of bins and I add x quantity of each bin to the packer. The algorithm always does a great job but it usually uses the bins in the order it receives them, therefore it sometimes doesn't output a good solution. I've tried every one of the options for the bin_algo parameter and also every one of the packing algorithms but in any case it chooses the bins according to the fitness.
I will use a pretty simple example to illustrate this problem, if I have 2 2x2 bins and 2 3x2 bins, and I try to fit 3 1x2 rectangles, the best solution is to put the 3 rectangles inside 1 3x2 bin. But if I don't provide the 3x2 bins first, the output will tell me to use 2 2x2 bins.
When I read the documentation, I thought the PackingBin.BBF (Bin Best Fit) option would do the job, but maybe I'm missing something.
By the way, thanks for rectpack, it's a great library.

secnot commented

Hi

Given the problem is np-hard, the algorithms used by rectpack are heuristic and won't find the best solution just a 'good enough' one in most cases.

That said, there are a couple of approaches you can try to improve the packing, in order of complexity:

  • Short the bins by descending area, and the rectangles using sort_algo=SORT_AREA before packing.

  • Try all the rectangle/bin area sorting combinations and select the best.

  • Rotate some or all of the rectangles before packing.

  • Also use PackingBin.Global, it should try all the rectangles in the first bin before opening a new one. (This will be slow when the number of rectangles is large)

  • Create several packers with all the possible combinations of bin selection, packing algorithm, and rectangle/bin sorting, or pre rotation. Then select the best solution. (slower still)

If all of the a above doesn't solve the problem you are out of luck with this library, but if the number of rectangles is low you can still find the optimal solution by brute force using depth-first search.

Good luck :)

BeAntares commented

I appreciate your support. I will follow your advice. Thank you