moptipyapps.binpacking2d.encodings package¶

Different encodings for the two-dimensional bin packing problem.

The following encodings are implemented:

The improved bottom-left encoding 1, ibl_encoding_1, processes a permutation of objects from beginning to end and places the objects into the last bin (according to the improved-bottom-left method) until that bin is full and then begins to put them into the next bin.
The improved bottom-left encoding 2, ibl_encoding_2, processes a permutation of objects from beginning to end and places the objects into the first bin into which they fit (according to the improved-bottom-left method). It is slower than ibl_encoding_1 but its results are never worse for any permutation and better for several.

Submodules¶

moptipyapps.binpacking2d.encodings.ibl_encoding_1 module¶

An improved bottom left encoding by Liu and Teng extended to multiple bins.

Here we provide an implementation of the improved bottom left encoding by Liu and Teng [1], but extended to bins with limited height. If the height of the bin is a limiting factor, then our implementation will automatically use multiple bins. Another implementation is given in moptipyapps.binpacking2d.encodings.ibl_encoding_2.

An instance of the two-dimensional bin packing problem defines a set of objects to be packed and a bin size (width and height). Each object to be packed has itself a width and a height as well as a repetition counter, which is 1 if the object only occurs a single time and larger otherwise (i.e., if the repetition counter is 5, the object needs to be packaged five times).

The encoding receives signed permutations with repetitions as input. Each element of the permutation identifies one object from the bin packing instance. Each such object ID must occur exactly as often as the repetition counter of the object in the instance data suggest. But the ID may also occur negated, in which case the object is supposed to rotated by 90°.

Now our encoding processes such a permutation from beginning to end. It starts with an empty bin 1. Each object is first placed with its right end at the right end of the bin and with its bottom line exactly at the top of the bin, i.e., outside of the bin. Then, in each step, we move the object as far down as possible. Then, we move it to the left as far as possible, but we immediately stop if there was another chance to move the object down. In other words, downward movements are preferred over left movements. This is repeated until no movement of the object is possible anymore.

Once the object cannot be moved anymore, we check if it is fully inside the bin. If yes, then the object is included in the bin and we continue with the next object. If not, it does not fit into the bin.

This is the “Improved Bottom Left” heuristic by Liu and Teng [1].

If the object does not fit into the current bin, we place it at the bottom-left corner of a new bin. We therefore increase the bin counter. From now on, all the following objects will be placed into this bin until the bin is full as well, in which case we move to the next bin again. This means that the current bin is closed at the same moment the first object is encountered that does not fit into it anymore. Therefore, the objects in a closed bin do no longer need to be considered when packing subsequent objects.

This is different from the second variant of this encoding implemented in file moptipyapps.binpacking2d.encodings.ibl_encoding_2, which always checks all the bins, starting at bin 1, when placing any object. That other encoding variant therefore must always consider all bins and is thus slower, but tends to yield better packings.

This procedure has originally been developed and implemented by Mr. Rui ZHAO (赵睿), <zr1329142665@163.com> a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

Dequan Liu and Hongfei Teng. An Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles. European Journal of Operational Research. 112(2):413-420. January (1999). https://doi.org/10.1016/S0377-2217(97)00437-2. http://www.paper.edu.cn/scholar/showpdf/MUT2AN0IOTD0Mxxh.

class moptipyapps.binpacking2d.encodings.ibl_encoding_1.ImprovedBottomLeftEncoding1(instance)[source]¶

Bases: Encoding

An Improved Bottem Left Encoding by Liu and Teng for multiple bins.

decode(x, y)[source]¶

Map a potentially signed permutation to a packing.

Parameters:

x (ndarray) – the array
y (Packing) – the Gantt chart

Return type:

None

log_parameters_to(logger)[source]¶

Log all parameters of this component as key-value pairs.

Parameters:: logger (KeyValueLogSection) – the logger for the parameters
Return type:: None

moptipyapps.binpacking2d.encodings.ibl_encoding_2 module¶

An improved bottom left encoding by Liu and Teng extended to multiple bins.

Here we provide an implementation of the improved bottom left encoding by Liu and Teng [1], but extended to bins with limited height. If the height of the bin is a limiting factor, then our implementation will automatically use multiple bins. Another variant is given in moptipyapps.binpacking2d.encodings.ibl_encoding_1.

An instance instance of the two-dimensional bin packing problem defines a set of objects to be packed and a bin size (width and height). Each object to be packed has itself a width and a height as well as a repetition counter, which is 1 if the object only occurs a single time and larger otherwise (i.e., if the repetition counter is 5, the object needs to be packaged five times).

The encoding receives signed permutations with repetitions as input. Each element of the permutation identifies one object from the bin packing instance. Each such object ID must occur exactly as often as the repetition counter of the object in the instance data suggest. But the ID may also occur negated, in which case the object is supposed to rotated by 90°.

Now our encoding processes such a permutation from beginning to end. It starts with an empty bin 1. Each object is first placed with its right end at the right end of the first bin and with its bottom line exactly at the top of the bin, i.e., outside of the bin. Then, in each step, we move the object as far down as possible. Then, we move it to the left as far as possible, but we immediately stop if there was another chance to move the object down. In other words, downward movements are preferred over left movements. This is repeated until no movement of the object is possible anymore.

Once the object cannot be moved anymore, we check if it is fully inside the bin. If yes, then the object is included in the bin and we continue with the next object. If not, it does not fit into the bin.

This is the “Improved Bottom Left” heuristic by Liu and Teng [1].

If the object does not fit into the first bin and we already “opened” a second bin, then we try to place it into the second bin using the same procedure. And then into the third bin if that does not work out, and so on. Until we have tried unsuccessfully all the bins that we have opened.

In this case, we “open” the next bin and we place the object at the bottom-left corner of a new bin. Then we continue with the next object, again trying to put it into the first bin, then the second bin, and so on.

This is different from the first variant of this encoding implemented in file moptipyapps.binpacking2d.encodings.ibl_encoding_2, which always and only tries to put objects into the last bin that was opened (and moves to a new bin if that does not work out). That variant of the encoding is therefore faster than the one here, but the one here tends to yield better packings.

The problem with this is that we need to basically first try to put the object into the first bin. For this we need to look at all the objects that we have already placed, because it could be that we already have one object in the first bin, then one in the second bin that did not fit into the first bin, then one smaller object in the first bin again, and so on. If our new object does not fit into the first bin, then we need to do the same with the second bin, and so on. So for every bin we try, we need to look at all objects already placed. And the number of bins we could try could be equal to the number of objects that we have already placed (if each object occupies one bin alone). So we have a worst case complexity of O(n ** 2) for placing one object. And we do this for all objects, so we would have a O(n ** 3) overall complexity. Well, actually, it is worse: Because we repeat the process of looking at all the objects several times while moving our new item to the left and down and to the left and down. So I suspect that we actually have O(n ** 4). That is annoying.

We try to alleviate this a little bit by remembering, for each bin, the index of the first object that we put in there and the index of the last object we put in there. Now within these two indices, there also might be objects that we placed into other bins. But for a very little overhead (remembering two values per bin), we have a certain chance to speed up the process in several situations. For instance, the worst case from above, that each object occupies exactly one bin by itself becomes easier because we would only look at one already placed object per bin.

This procedure has originally been developed and implemented by Mr. Rui ZHAO (赵睿), <zr1329142665@163.com>, a Master’s student at the Institute of Applied Optimization (应用优化研究所, http://iao.hfuu.edu.cn) of the School of Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University (合肥学院) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of Prof. Dr. Thomas Weise (汤卫思教授).

Dequan Liu and Hongfei Teng. An Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles. European Journal of Operational Research. 112(2):413-420. January (1999). https://doi.org/10.1016/S0377-2217(97)00437-2. http://www.paper.edu.cn/scholar/showpdf/MUT2AN0IOTD0Mxxh.

class moptipyapps.binpacking2d.encodings.ibl_encoding_2.ImprovedBottomLeftEncoding2(instance)[source]¶