moptipyapps.binpacking2d.objectives package¶
Different objective functions for two-dimensional bin packing.
The following objective functions are implemented:
bin_countreturns the number of bins occupied by a given packing.bin_count_and_emptyreturns a combination of the number of bins occupied by a given packing and the fewest number of objects located in any bin.bin_count_and_last_emptyreturns a combination of the number of bins occupied by a given packing and the number of objects located in the last bin.bin_count_and_smallreturns a combination of the number of bins occupied by a given packing and the smallest area occupied by objects in any bin.bin_count_and_last_smallreturns a combination of the number of bins occupied by a given packing and the area occupied by the objects in the last bin.bin_count_and_lowest_skylinereturns a combination of the number of bins occupied by a given packing and the smallest area under the skyline in any bin, where the “skyline” is the upper border of the space occupied by objects.bin_count_and_last_skylinereturns a combination of the number of bins occupied by a given packing and the smallest area under the skyline in the last bin, where the “skyline” is the upper border of the space occupied by objects.
Important initial work on this code has been contributed 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 (汤卫思教授). An objective function for minimizing the number of bins in packings. This function returns the number of bins. the name of the bin count objective function Bases: Compute the number of bins. Get the number of bins. x – the packing the number of bins used Return True because there are only integer bins. always Get the lower bound of the number of bins objective. the lower bound for the number of required bins, i.e., Get the upper bound of the number of bins. An objective function indirectly minimizing the number of bins in packings. This objective function first computes the number of bins used. Let’s call it n_bins. We know the total number of items, This is similar to Bases: Get the number of bins and number of elements in the emptiest one. Get the number of bins and number of elements in the emptiest one. We compute the total number of bins minus 1 and multiply it with the number of items. We then add the smallest number of elements in any bin. the objective value An objective function indirectly minimizing the number of bins in packings. This objective function first computes the number of bins used. Let’s call it n_bins. We know the total number of items, The idea behind this is: If one of two packings has the smaller number of bins, then this one will always have the smaller objective value. If two packings have the same number of bins, but one has fewer items in the very last bin, then that one is better. With this mechanism, we drive the search towards “emptying” the last bin. If the number of items in the last bin would reach 0, that last bin would disappear - and we have one bin less. Bases: Compute the number of bins and the emptiness of the last one. Evaluate the objective function. x – the solution the bin size and emptyness factor Get the lower bound of the number of bins and emptiness objective. We know from the instance ( max(n_items, (lb - 1) * n_items + 1) Get the upper bound of the number of bins plus emptiness. the number of items in the instance to the square Compute the number of bins and the emptiness of the last bin. We compute the total number of bins minus 1 and multiply it with the number of items. We then add the number of items in the last bin. An objective function indirectly minimizing the number of bins in packings. This objective function minimizes the number of bins and maximizes the “usable” space in the last bin. Which space is actually useful for our encodings? Let’s say we have filled a bin to a certain degree and somewhere there is a “hole” in the filled area, but this hole is covered by another object. The area of the hole is not used, but it also cannot be used anymore. The area that we can definitely use is the area above the “skyline” of the objects in the bin. The skyline at any horizontal x coordinate be the highest border of any object that intersects with x horizontally. In other words, it is the y value at and above which no other object is located at this x coordinate. The area below the skyline cannot be used anymore. The area above the skyline can. If we minimize the area below the skyline in the very last bin, then this will a similar impact as minimizing the overall object area in the last bin (see The objective Bases: Compute the number of bins and the useful area in the last bin. Compute the bin count-1 times the bin size + the space below the skyline. the objective value An objective function indirectly minimizing the number of bins in packings. This objective function computes the number of bins used. Let’s call it n_bins. We know the area bin_area of a bin as well. Now we return (bin_area * (n_bins - 1)) + area_of_items_in_last_bin, where area_of_items_in_last_bin is, well, the area covered by items in the very last bin. The idea behind this is: If one of two packings has the smaller number of bins, then this one will always have the smaller objective value. If two packings have the same number of bins, but one requires less space in the very last bin, then that one is better. With this mechanism, we drive the search towards “emptying” the last bin. If the number of items in the last bin would reach 0, that last bin would disappear - and we have one bin less. This objective is similar to Bases: Compute the number of bins and the area in the last one. Evaluate the objective function. x – the solution the bin size and last-bin-small-area factor Get the lower bound of the number of bins and small-size objective. We know from the instance ( total_item_area if the lower bound lb of the number of bins is 1, else (lb - 1) * bin_area + smallest_area, where bin_area is the area of a bin, total_item_area is the area of all items added up, and smallest_area is the area of the smallest item Get the upper bound of this objective function. a very coarse estimate of the upper bound Compute the number of bins and the occupied area in the last bin. We compute the total number of bins minus 1 and multiply it with the total area of items. We then add the area of items in the last bin. the objective value An objective function indirectly minimizing the number of bins in packings. This objective function minimizes the number of bins and maximizes the “useable” space in any bin. Which space is actually useful for our encodings? Let’s say we have filled a bin to a certain degree and somewhere there is a “hole” in the filled area, but this hole is covered by another object. The area of the hole is not used, but it also cannot be used anymore. The area that we can definitely use is the area above the “skyline” of the objects in the bin. The skyline at any horizontal x coordinate be the highest border of any object that intersects with x horizontally. In other words, it is the y value at and above which no other object is located at this x coordinate. The area below the skyline cannot be used anymore. The area above the skyline can. If we minimize the area below the skyline in the very last bin, then this will a similar impact as minimizing the overall object area in the last bin (see But we could also minimize the area under the skylines in the other bins. Because a) if we can get any skyline in any bin to become 0, then this bin disappears and b) if we can free up space in the bins by lowering the skylines, then we have a better chance to move an object from the next bin forward into that bin, which increases the chance to make that bin empty. In this objective function, we therefore use the smallest skyline area over all bins to distinguish between packings of the same number of bins. For all intents and purposes, it has the same lower and upper bound as the Bases: Compute the number of bins and the largest useful area. Compute the bin count-1 times the bin size + the space below the skyline. the objective value An objective function indirectly minimizing the number of bins in packings. This objective function computes the number of bins used. Let’s call it n_bins. We know the area bin_area of a bin as well. We then compute the minimum area occupied in any bin, min_area. Now we return (bin_area * (n_bins - 1)) + min_area. This function always prefers a packing that has fewer bins over a packing with more bins duw to the term bin_area * (n_bins - 1) and bin_area >= min_area (let us ignore the case where bin_area == min_area, which does not make practical sense). Since min_area < bin_area in all practically relevant cases, the offset min_area just distinguishes packings that have same number of bins. Amongst such packings, those whose least-occupied bin is closer to being empty are preferred (regardless where this bin is). The idea is that this will eventually allow us to get rid of that least-occupied bin in subsequent optimization steps, i.e., to reduce the number of bins. This is similar to the Bases: Compute the number of bins and the area in the smallest one. Compute the number of bins and the smallest occupied area in any bin. We compute the total number of bins minus 1 and multiply it with the total area of items. We then add the area of items in the smallest bin. the objective valueSubmodules¶
moptipyapps.binpacking2d.objectives.bin_count module¶
Objectivelower_bound_bins>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.lower_bound_bins
1
>>> BinCount(ins).lower_bound()
1
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.lower_bound_bins
2
>>> BinCount(ins).lower_bound()
2
>>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
>>> ins.lower_bound_bins
4
>>> BinCount(ins).lower_bound()
4
>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
3
>>> BinCount(ins).upper_bound()
3
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
12
>>> BinCount(ins).upper_bound()
12
>>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
>>> ins.n_items
31
>>> BinCount(ins).upper_bound()
31
moptipyapps.binpacking2d.objectives.bin_count_and_empty module¶
n_items, as well (because this is also the number of rows in the packing). Now we return (n_items * (n_bins - 1)) + min_items, where min_items is the number of items in the bin with the fewest items.bin_count_and_last_small, but instead of focussing on the very last bin, it uses the minimum element count over all bins. It has the same lower- and upper bound, though.BinCountAndLastEmpty>>> tempa = np.empty(10, int)
>>> bin_count_and_empty(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int), tempa)
3
>>> bin_count_and_empty(np.array([[1, 1, 10, 10, 20, 20],
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int), tempa)
4
>>> bin_count_and_empty(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int), tempa)
4
>>> bin_count_and_empty(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int), tempa)
7
moptipyapps.binpacking2d.objectives.bin_count_and_last_empty module¶
n_items, as well (because this is also the number of rows in the packing). Now we return (n_items * (n_bins - 1)) + number_of_items_in_last_bin, where number_of_items_in_last_bin is, well, the number of items in the very last bin.BinCountlower_bound_bins) that we require at least as many bins such that they can accommodate the total area of all items together. Let’s call this number lb. Now if lb is one, then all objects could be in the first bin, in which case the objective value would equal to n_items, i.e., the total number of items in the first = last bin. If it is lb=2, then we know that we will need at least two bins. The best case would be that n_items - 1 items are in the first bin and one is in the last bin. This means that we would get 1 * n_items + 1 as objective value. If we have lb=3 bins, then we could have n_items - 1 items distributed over the first two bins with one item left over in the last bin, i.e., would get (2 * n_items) + 1. And so on.>>> from moptipyapps.binpacking2d.instance import Instance
>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
3
>>> ins.lower_bound_bins
1
>>> BinCountAndLastEmpty(ins).lower_bound()
3
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
12
>>> ins.lower_bound_bins
2
>>> BinCountAndLastEmpty(ins).lower_bound()
13
>>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
>>> ins.n_items
31
>>> ins.lower_bound_bins
4
>>> BinCountAndLastEmpty(ins).lower_bound()
94
>>> from moptipyapps.binpacking2d.instance import Instance
>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
3
>>> BinCountAndLastEmpty(ins).upper_bound()
9
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
12
>>> BinCountAndLastEmpty(ins).upper_bound()
144
>>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
>>> ins.n_items
31
>>> BinCountAndLastEmpty(ins).upper_bound()
961
>>> bin_count_and_last_empty(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int))
3
>>> bin_count_and_last_empty(np.array([[1, 1, 10, 10, 20, 20],
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int))
4
>>> bin_count_and_last_empty(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int))
5
>>> bin_count_and_last_empty(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int))
7
moptipyapps.binpacking2d.objectives.bin_count_and_last_skyline module¶
bin_count_and_last_small). We push the skyline lower and lower and, if we are lucky, the last bin eventually becomes empty.bin_count_and_lowest_skyline works quite similarly to this one, but minimizes the lowest skyline over any bin.BinCountAndLastSmall>>> 10*0 + 10*20 + 10*30 + 10*40 + 10*0
900
>>> bin_count_and_last_skyline(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int),
... 50, 50)
900
>>> 5 * 0 + 5 * 10 + 10 * 20 + 5 * 10 + 25 * 0
300
>>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 1, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10]], int),
... 50, 50)
300
>>> 50*50 + 0*10 + 10*20 + 30*0
2700
>>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 2, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10]], int),
... 50, 50)
2700
>>> 5 * 0 + 5 * 10 + 3 * 20 + (50 - 13) * 25
1035
>>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 1, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10],
... [2, 1, 13, 20, 50, 25]], int),
... 50, 50)
1035
>>> 50*50*3 + 25*50
8750
>>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
... [2, 2, 0, 0, 20, 20],
... [3, 3, 0, 0, 25, 10],
... [4, 4, 0, 0, 50, 25]], int),
... 50, 50)
8750
>>> 50*50*3 + 25*10 + 25*0
7750
>>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
... [2, 2, 0, 0, 20, 20],
... [3, 4, 0, 0, 25, 10],
... [4, 3, 0, 0, 50, 25]], int),
... 50, 50)
7750
>>> 50*50*3 + 20*20 + 30*0
7900
>>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
... [2, 4, 0, 0, 20, 20],
... [3, 2, 0, 0, 25, 10],
... [4, 3, 0, 0, 50, 25]], int),
... 50, 50)
7900
>>> 50*50*3 + 20*10 + 30*20 + 20*0
8300
>>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
... [2, 4, 0, 0, 20, 20],
... [3, 2, 0, 0, 25, 10],
... [2, 4, 10, 20, 30, 30],
... [4, 3, 0, 0, 50, 25]], int),
... 50, 50)
8300
moptipyapps.binpacking2d.objectives.bin_count_and_last_small module¶
bin_count_and_small, with the difference that it focuses on the last bin whereas bin_count_and_small tries to minimize the area in any bin.BinCountlower_bound_bins) that we require at least as many bins such that they can accommodate the total area of all items together. Let’s call this number lb. Now if lb is one, then all objects could be in the first bin, in which case the objective value would equal to the total area of all items (total_item_area). If it is lb=2, then we know that we will need at least two bins. The best case would be that almost all items are in the first bin and only the smallest object is in the last bin. This means that we would get 1 * bin_area + smallest_area as objective value. If we have lb=3 bins, then we could again have all but the smallest items distributed over the first two bins and only the smallest one in the last bin, i.e., would get (2 * bin_area) + smallest_area. And so on.>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.total_item_area
84
>>> ins.lower_bound_bins
1
>>> BinCountAndLastSmall(ins).lower_bound()
84
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.total_item_area
534
>>> ins.lower_bound_bins
2
>>> BinCountAndLastSmall(ins).lower_bound()
509
>>> ins = Instance("c", 10, 50, [[10, 5, 10], [30, 3, 1], [5, 5, 1]])
>>> ins.total_item_area
615
>>> ins.lower_bound_bins
2
>>> BinCountAndLastSmall(ins).lower_bound()
525
>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
3
>>> BinCountAndLastSmall(ins).upper_bound()
15000
>>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
>>> ins.n_items
12
>>> BinCountAndLastSmall(ins).upper_bound()
6000
>>> ins = Instance("c", 10, 50, [[10, 5, 10], [30, 3, 1], [5, 5, 10]])
>>> ins.n_items
21
>>> BinCountAndLastSmall(ins).upper_bound()
10500
>>> bin_count_and_last_small(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int),
... 50*50)
300
>>> bin_count_and_last_small(np.array([[1, 1, 10, 10, 20, 20],
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50)
2600
>>> bin_count_and_last_small(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50)
2700
>>> bin_count_and_last_small(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50)
5100
>>> bin_count_and_last_small(np.array([[1, 3, 10, 10, 50, 50], # bin 3!
... [1, 2, 30, 30, 60, 60], # bin 2!
... [1, 1, 20, 20, 30, 30]], np.int8),
... 50*50)
6600
moptipyapps.binpacking2d.objectives.bin_count_and_lowest_skyline module¶
bin_count_and_last_small). We push the skyline lower and lower and, if we are lucky, the last bin eventually becomes empty. This is done with the objective bin_count_and_last_skyline.bin_count_and_last_small objective.BinCountAndLastSmall>>> 10*0 + 10*20 + 10*30 + 10*40 + 10*0
900
>>> bin_count_and_lowest_skyline(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int),
... 50, 50)
900
>>> 5 * 0 + 5 * 10 + 10 * 20 + 5 * 10 + 25 * 0
300
>>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 1, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10]], int),
... 50, 50)
300
>>> 50*50 + min(5*0 + 10*10 + 10*10 + 25*0, 10*0 + 10*20 + 30*0)
2700
>>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 2, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10]], int),
... 50, 50)
2700
>>> 5 * 0 + 5 * 10 + 3 * 20 + (50 - 13) * 25
1035
>>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
... [1, 1, 10, 10, 20, 20],
... [1, 1, 15, 0, 25, 10],
... [2, 1, 13, 20, 50, 25]], int),
... 50, 50)
1035
>>> 2500*3 + min(10*10, 20*20, 25*10, 50*25)
7600
>>> bin_count_and_lowest_skyline(np.array([[1, 1, 0, 0, 10, 10],
... [2, 2, 0, 0, 20, 20],
... [3, 3, 0, 0, 25, 10],
... [4, 4, 0, 0, 50, 25]], int),
... 50, 50)
7600
moptipyapps.binpacking2d.objectives.bin_count_and_small module¶
bin_count_and_small objective, except that we do not try to expunge the last bin, but any bin. It has the same lower and upper bound, though.BinCountAndLastSmall>>> tempa = np.empty(10, int)
>>> bin_count_and_small(np.array([[1, 1, 10, 10, 20, 20],
... [1, 1, 30, 30, 40, 40],
... [1, 1, 20, 20, 30, 30]], int),
... 50*50, tempa)
300
>>> bin_count_and_small(np.array([[1, 1, 10, 10, 20, 20],
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50, tempa)
2600
>>> bin_count_and_small(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50, tempa)
2600
>>> bin_count_and_small(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
... [1, 2, 30, 30, 40, 40], # bin 2!
... [1, 1, 20, 20, 30, 30]], int),
... 50*50, tempa)
5100
>>> bin_count_and_small(np.array([[1, 3, 10, 10, 50, 50], # bin 3!
... [1, 2, 30, 30, 60, 60], # bin 2!
... [1, 1, 20, 20, 30, 30]], np.int8),
... 50*50, tempa)
5100