Coverage for moptipyapps / binpacking2d / objectives / bin_count_and_last_small.py: 68%
44 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2An objective function indirectly minimizing the number of bins in packings.
4This objective function computes the number of bins used. Let's call it
5`n_bins`. We know the area `bin_area` of a bin as well. Now we return
6`(bin_area * (n_bins - 1)) + area_of_items_in_last_bin`, where
7`area_of_items_in_last_bin` is, well, the area covered by items in the
8very last bin.
10The idea behind this is: If one of two packings has the smaller number of
11bins, then this one will always have the smaller objective value. If two
12packings have the same number of bins, but one requires less space in the very
13last bin, then that one is better. With this mechanism, we drive the search
14towards "emptying" the last bin. If the number of items in the last bin would
15reach `0`, that last bin would disappear - and we have one bin less.
17This objective is similar to :mod:`~moptipyapps.binpacking2d.objectives.\
18bin_count_and_small`, with the difference that it focuses on the *last* bin
19whereas :mod:`~moptipyapps.binpacking2d.objectives.bin_count_and_small` tries
20to minimize the area in *any* bin.
21"""
22from typing import Final
24import numba # type: ignore
25import numpy as np
26from pycommons.math.int_math import ceil_div
28from moptipyapps.binpacking2d.instance import Instance
29from moptipyapps.binpacking2d.objectives.bin_count import BinCount
30from moptipyapps.binpacking2d.packing import (
31 IDX_BIN,
32 IDX_BOTTOM_Y,
33 IDX_LEFT_X,
34 IDX_RIGHT_X,
35 IDX_TOP_Y,
36)
39@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
40def bin_count_and_last_small(y: np.ndarray, bin_area: int) -> int:
41 """
42 Compute the number of bins and the occupied area in the last bin.
44 We compute the total number of bins minus 1 and multiply it with the
45 total area of items. We then add the area of items in the last bin.
47 :param y: the packing
48 :param bin_area: the area of a single bin
49 :return: the objective value
51 >>> bin_count_and_last_small(np.array([[1, 1, 10, 10, 20, 20],
52 ... [1, 1, 30, 30, 40, 40],
53 ... [1, 1, 20, 20, 30, 30]], int),
54 ... 50*50)
55 300
56 >>> bin_count_and_last_small(np.array([[1, 1, 10, 10, 20, 20],
57 ... [1, 2, 30, 30, 40, 40], # bin 2!
58 ... [1, 1, 20, 20, 30, 30]], int),
59 ... 50*50)
60 2600
61 >>> bin_count_and_last_small(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
62 ... [1, 2, 30, 30, 40, 40], # bin 2!
63 ... [1, 1, 20, 20, 30, 30]], int),
64 ... 50*50)
65 2700
66 >>> bin_count_and_last_small(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
67 ... [1, 2, 30, 30, 40, 40], # bin 2!
68 ... [1, 1, 20, 20, 30, 30]], int),
69 ... 50*50)
70 5100
71 >>> bin_count_and_last_small(np.array([[1, 3, 10, 10, 50, 50], # bin 3!
72 ... [1, 2, 30, 30, 60, 60], # bin 2!
73 ... [1, 1, 20, 20, 30, 30]], np.int8),
74 ... 50*50)
75 6600
76 """
77 current_bin: int = -1 # the current idea of what the last bin is
78 current_area: int = 0 # the area of items already in that bin
79 n_items: Final[int] = len(y) # the number of rows in the matrix
81 for i in range(n_items): # iterate over all packed items
82 bin_idx: int = int(y[i, IDX_BIN]) # get the bin index of the item
83 if bin_idx < current_bin:
84 continue
85 area: int = int(y[i, IDX_RIGHT_X] - y[i, IDX_LEFT_X]) \
86 * int(y[i, IDX_TOP_Y] - y[i, IDX_BOTTOM_Y])
87 if bin_idx > current_bin: # it's a new biggest bin = new last bin?
88 current_area = area # then the current area is this
89 current_bin = bin_idx # and we remember it
90 elif bin_idx == current_bin: # did item go into the current last bin?
91 current_area += area # then increase size
92 return (bin_area * (current_bin - 1)) + current_area # return objective
95class BinCountAndLastSmall(BinCount):
96 """Compute the number of bins and the area in the last one."""
98 def __init__(self, instance: Instance) -> None:
99 """
100 Initialize the objective function.
102 :param instance: the instance to load the bounds from
103 """
104 super().__init__(instance)
105 #: the bin size
106 self._bin_size: Final[int] = instance.bin_width * instance.bin_height
108 def evaluate(self, x) -> int:
109 """
110 Evaluate the objective function.
112 :param x: the solution
113 :return: the bin size and last-bin-small-area factor
114 """
115 return bin_count_and_last_small(x, self._bin_size)
117 def to_bin_count(self, z: int) -> int:
118 """
119 Convert an objective value to a bin count.
121 :param z: the objective value
122 :return: the bin count
123 """
124 return ceil_div(z, self._bin_size)
126 def lower_bound(self) -> int:
127 """
128 Get the lower bound of the number of bins and small-size objective.
130 We know from the instance (:attr:`~moptipyapps.binpacking2d\
131.instance.Instance.lower_bound_bins`) that we require at least as many bins
132 such that they can accommodate the total area of all items together.
133 Let's call this number `lb`. Now if `lb` is one, then all objects could
134 be in the first bin, in which case the objective value would equal to
135 the total area of all items (:attr:`~moptipyapps.binpacking2d\
136.instance.Instance.total_item_area`).
137 If it is `lb=2`, then we know that we will need at least two bins. The
138 best case would be that almost all items are in the first bin and
139 only the smallest object is in the last bin. This means that we would
140 get `1 * bin_area + smallest_area` as objective value. If we have
141 `lb=3` bins, then we could again have all but the smallest items
142 distributed over the first two bins and only the smallest one in the
143 last bin, i.e., would get `(2 * bin_area) + smallest_area`. And so on.
145 :return: `total_item_area` if the lower bound `lb` of the number of
146 bins is `1`, else `(lb - 1) * bin_area + smallest_area`, where
147 `bin_area` is the area of a bin, `total_item_area` is the area of
148 all items added up, and `smallest_area` is the area of the
149 smallest item
151 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
152 >>> ins.total_item_area
153 84
154 >>> ins.lower_bound_bins
155 1
156 >>> BinCountAndLastSmall(ins).lower_bound()
157 84
159 >>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
160 >>> ins.total_item_area
161 534
162 >>> ins.lower_bound_bins
163 2
164 >>> BinCountAndLastSmall(ins).lower_bound()
165 509
167 >>> ins = Instance("c", 10, 50, [[10, 5, 10], [30, 3, 1], [5, 5, 1]])
168 >>> ins.total_item_area
169 615
170 >>> ins.lower_bound_bins
171 2
172 >>> BinCountAndLastSmall(ins).lower_bound()
173 525
174 """
175 if self._instance.lower_bound_bins == 1:
176 return self._instance.total_item_area
177 smallest_area: int = -1
178 for row in self._instance:
179 area: int = int(row[0]) * int(row[1])
180 if (smallest_area < 0) or (area < smallest_area):
181 smallest_area = area
182 return int(((self._instance.lower_bound_bins - 1)
183 * self._instance.bin_height
184 * self._instance.bin_width) + smallest_area)
186 def upper_bound(self) -> int:
187 """
188 Get the upper bound of this objective function.
190 :return: a very coarse estimate of the upper bound
192 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
193 >>> ins.n_items
194 3
195 >>> BinCountAndLastSmall(ins).upper_bound()
196 15000
198 >>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
199 >>> ins.n_items
200 12
201 >>> BinCountAndLastSmall(ins).upper_bound()
202 6000
204 >>> ins = Instance("c", 10, 50, [[10, 5, 10], [30, 3, 1], [5, 5, 10]])
205 >>> ins.n_items
206 21
207 >>> BinCountAndLastSmall(ins).upper_bound()
208 10500
209 """
210 return self._instance.n_items * self._instance.bin_height \
211 * self._instance.bin_width
213 def __str__(self) -> str:
214 """
215 Get the name of the bins objective function.
217 :return: `binCountAndLastSmall`
218 :retval "binCountAndLastSmall": always
219 """
220 return "binCountAndLastSmall"