Coverage for moptipyapps / binpacking2d / encodings / ibl_encoding_2.py: 29%
100 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2An improved bottom left encoding by Liu and Teng extended to multiple bins.
4Here we provide an implementation of the improved bottom left encoding by Liu
5and Teng [1], but extended to bins with limited height. If the height of the
6bin is a limiting factor, then our implementation will automatically use
7multiple bins. Another variant is given in
8:mod:`moptipyapps.binpacking2d.encodings.ibl_encoding_1`.
10An instance :mod:`~moptipyapps.binpacking2d.instance` of the
11two-dimensional bin packing problem defines a set of objects to be packed
12and a bin size (width and height). Each object to be packed has itself a
13width and a height as well as a repetition counter, which is `1` if the object
14only occurs a single time and larger otherwise (i.e., if the repetition
15counter is `5`, the object needs to be packaged five times).
17The encoding receives signed permutations with repetitions as input. Each
18element of the permutation identifies one object from the bin packing
19instance. Each such object ID must occur exactly as often as the repetition
20counter of the object in the instance data suggest. But the ID may also occur
21negated, in which case the object is supposed to rotated by 90°.
23Now our encoding processes such a permutation from beginning to end. It starts
24with an empty bin `1`. Each object is first placed with its right end at the
25right end of the first bin and with its bottom line exactly at the top of the
26bin, i.e., outside of the bin. Then, in each step, we move the object as far
27down as possible. Then, we move it to the left as far as possible, but we
28immediately stop if there was another chance to move the object down. In
29other words, downward movements are preferred over left movements. This is
30repeated until no movement of the object is possible anymore.
32Once the object cannot be moved anymore, we check if it is fully inside the
33bin. If yes, then the object is included in the bin and we continue with the
34next object. If not, it does not fit into the bin.
36This is the "Improved Bottom Left" heuristic by Liu and Teng [1].
38If the object does not fit into the first bin and we already "opened" a second
39bin, then we try to place it into the second bin using the same procedure. And
40then into the third bin if that does not work out, and so on. Until we have
41tried unsuccessfully all the bins that we have opened.
43In this case, we "open" the next bin and we place the object at the
44bottom-left corner of a new bin. Then we continue with the next object, again
45trying to put it into the first bin, then the second bin, and so on.
47This is different from the first variant of this encoding implemented in file
48:mod:`moptipyapps.binpacking2d.encodings.ibl_encoding_2`, which always and
49only tries to put objects into the last bin that was opened (and moves to a
50new bin if that does not work out). That variant of the encoding is therefore
51faster than the one here, but the one here tends to yield better packings.
53The problem with this is that we need to basically first try to put the object
54into the first bin. For this we need to look at *all* the objects that we have
55already placed, because it could be that we already have one object in the
56first bin, then one in the second bin that did not fit into the first bin,
57then one smaller object in the first bin again, and so on. If our new object
58does not fit into the first bin, then we need to do the same with the second
59bin, and so on. So for every bin we try, we need to look at all objects already
60placed. And the number of bins we could try could be equal to the number of
61objects that we have already placed (if each object occupies one bin alone).
62So we have a worst case complexity of O(n ** 2) for placing one object. And we
63do this for all objects, so we would have a O(n ** 3) overall complexity.
64Well, actually, it is worse: Because we repeat the process of looking at all
65the objects several times while moving our new item to the left and down and
66to the left and down. So I suspect that we actually have O(n ** 4).
67That is annoying.
69We try to alleviate this a little bit by remembering, for each bin, the index
70of the first object that we put in there and the index of the last object we
71put in there. Now within these two indices, there also might be objects that
72we placed into other bins. But for a very little overhead (remembering two
73values per bin), we have a certain chance to speed up the process in several
74situations. For instance, the worst case from above, that each object occupies
75exactly one bin by itself becomes easier because we would only look at one
76already placed object per bin.
78This procedure has originally been developed and implemented by Mr. Rui ZHAO
79(赵睿), <zr1329142665@163.com>, a Master's student at the Institute of Applied
80Optimization (应用优化研究所) of the School of
81Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University
82(合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of
83Prof. Dr. Thomas Weise (汤卫思教授).
851. Dequan Liu and Hongfei Teng. An Improved BL-Algorithm for Genetic Algorithm
86 of the Orthogonal Packing of Rectangles. European Journal of Operational
87 Research. 112(2):413-420. January (1999).
88 https://doi.org/10.1016/S0377-2217(97)00437-2.
89 http://www.paper.edu.cn/scholar/showpdf/MUT2AN0IOTD0Mxxh.
90"""
91from typing import Final
93import numba # type: ignore
94import numpy as np
95from moptipy.api.encoding import Encoding
96from moptipy.utils.logger import KeyValueLogSection
97from pycommons.types import type_error
99from moptipyapps.binpacking2d.instance import (
100 IDX_HEIGHT,
101 IDX_WIDTH,
102 Instance,
103)
104from moptipyapps.binpacking2d.packing import (
105 IDX_BIN,
106 IDX_BOTTOM_Y,
107 IDX_ID,
108 IDX_LEFT_X,
109 IDX_RIGHT_X,
110 IDX_TOP_Y,
111 Packing,
112)
113from moptipyapps.utils.shared import SCOPE_INSTANCE
116@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
117def __move_down(packing: np.ndarray, bin_id: int,
118 bin_start: int, bin_end: int, i1: int) -> bool:
119 """
120 Move the box at index `i1` down as far as possible in the current bin.
122 `bin_start` is the index of the first object that has already been placed
123 in the current bin `bin_id`. It always holds that `i1 >= bin_start`. In
124 the case that `i1 == bin_start`, then we can move the object directly to
125 the bottom of the bin without any issue.
126 If `i1 > bin_start` we iterate over all objects at indices
127 `bin_start...bin_end - 1` whose bin equals `bin`. We first set `min_down`
128 to the bottom-y coordinate of the box, because this is how far down we can
129 move at most.
131 Then, for each of the objects already placed in the bin `bin_id`, we check
132 if there is any intersection of the horizontal with the current box. If
133 there is no intersection *or* if the object is not already above the
134 current box, then the object will not influence the downward movement of
135 our object. If there is an intersection, then we cannot move the current
136 box deeper than the top-y coordinate of the other box.
138 *Only* the box at index `i1` is modified and if it is modified, this
139 function will return `True`.
141 :param packing: the packing under construction
142 :param bin_id: the bin ID
143 :param bin_start: the starting index of the current bin
144 :param bin_end: the exclusive end index of the current bin
145 :param i1: the index of the current box
146 :return: `True` if the object was moved down, `False` if the object cannot
147 be moved down any further because either it has reached the bottom or
148 because it would intersect with other objects
150 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
151 >>> r = np.array([[1, 1, 10, 20, 30, 40],
152 ... [2, 1, 30, 30, 50, 60],
153 ... [3, 1, 40, 100, 60, 200]])
154 >>> __move_down(r, 1, 0, 2, 2) # try to move down the box at index 2
155 True
156 >>> print(r[2, :])
157 [ 3 1 40 60 60 160]
158 >>> __move_down(r, 1, 0, 2, 2) # try to move down the box at index 2
159 False
160 >>> __move_down(r, 1, 0, 1, 1) # try to move down the box at index 1
161 True
162 >>> print(r[1, :])
163 [ 2 1 30 0 50 30]
164 >>> __move_down(r, 1, 0, 1, 1) # try to move down the box at index 1
165 False
166 >>> __move_down(r, 1, 0, 2, 2) # try to move down the box at index 2
167 True
168 >>> print(r[2, :])
169 [ 3 1 40 30 60 130]
170 >>> __move_down(r, 1, 0, 2, 2) # try to move down the box at index 2
171 False
172 >>> __move_down(r, 1, 0, 0, 0)
173 True
174 >>> print(r[0, :])
175 [ 1 1 10 0 30 20]
176 >>> __move_down(r, 1, 0, 0, 0)
177 False
178 """
179 # load the coordinates of i1 into local variables to speed up computation
180 packing_i1_left_x: Final[int] = int(packing[i1, IDX_LEFT_X])
181 packing_i1_bottom_y: Final[int] = int(packing[i1, IDX_BOTTOM_Y])
182 packing_i1_right_x: Final[int] = int(packing[i1, IDX_RIGHT_X])
183 packing_i1_top_y: Final[int] = int(packing[i1, IDX_TOP_Y])
184 min_down: int = packing_i1_bottom_y # maximum move: down to bottom
185 for i0 in range(bin_start, bin_end): # iterate over items in current bin
186 # An intersection exists if the right-x of an existing box is larger
187 # than the left-x of the new box AND if the left-x of the existing box
188 # is less than the right-x of the new box.
189 # Only intersections matter and *only* with objects in the same bin
190 # and only if the existing box is not already above the new box.
191 if (packing[i0, IDX_BIN] == bin_id) and \
192 (packing[i0, IDX_RIGHT_X] > packing_i1_left_x) and \
193 (packing[i0, IDX_LEFT_X] < packing_i1_right_x) and \
194 (packing[i0, IDX_BOTTOM_Y] < packing_i1_top_y):
195 # The object would horizontally intersect with the current object
196 min_down = min(min_down, int(
197 packing_i1_bottom_y - packing[i0, IDX_TOP_Y]))
198 if min_down > 0: # Can we move down? If yes, update box.
199 packing[i1, IDX_BOTTOM_Y] = packing_i1_bottom_y - min_down
200 packing[i1, IDX_TOP_Y] = packing_i1_top_y - min_down
201 return True
202 return False
205@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
206def __move_left(packing: np.ndarray, bin_id: int,
207 bin_start: int, bin_end: int, i1: int) -> bool:
208 """
209 Move the box at index `i1` left as far as possible in the current bin.
211 This function moves a box to the left without changing its vertical
212 position. It is slightly more tricky than the downwards moving function,
213 because in the improved bottom left heuristic, downward moves are
214 preferred compared to left moves. This means that the box needs to be
215 stopped when reaching the edge of a box on whose top it sits. Of course,
216 we only consider other objects inside the current bin
217 (with ID `bin_start`).
219 This function is to be called *after* `__move_down` and in an alternating
220 fashion.
222 *Only* the box at index `i1` is modified and if it is modified, this
223 function will return `True`.
225 :param packing: the packing under construction
226 :param bin_id: the bin ID
227 :param bin_start: the starting index of the current bin
228 :param bin_end: the exclusive end index of the current bin
229 :param i1: the index of the current box
230 :return: `True` if the object was moved down, `False` if the object cannot
231 be moved down any further because either it has reached the bottom or
232 because it would intersect with other objects
234 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
235 >>> r = np.array([[1, 1, 0, 0, 30, 10],
236 ... [2, 1, 35, 0, 45, 30],
237 ... [3, 1, 0, 10, 10, 20],
238 ... [4, 1, 40, 30, 50, 40]])
239 >>> __move_left(r, 1, 0, 3, 3)
240 True
241 >>> print(r[3, :])
242 [ 4 1 25 30 35 40]
243 >>> __move_left(r, 1, 0, 3, 3)
244 True
245 >>> print(r[3, :])
246 [ 4 1 0 30 10 40]
247 >>> r[3, :] = [4, 1, 25, 10, 35, 20]
248 >>> __move_left(r, 1, 0, 3, 3)
249 True
250 >>> print(r[3, :])
251 [ 4 1 10 10 20 20]
252 >>> __move_left(r, 1, 0, 3, 3)
253 False
254 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
255 >>> r = np.array([[1, 1, 0, 0, 10, 2],
256 ... [2, 1, 10, 0, 20, 5],
257 ... [3, 1, 8, 2, 10, 4]])
258 >>> __move_left(r, 0, 0, 3, 2)
259 True
260 >>> print(r[2, :])
261 [3 1 0 2 2 4]
262 """
263 packing_i1_left_x: Final[int] = int(packing[i1, IDX_LEFT_X])
264 packing_i1_bottom_y: Final[int] = int(packing[i1, IDX_BOTTOM_Y])
265 packing_i1_right_x: Final[int] = int(packing[i1, IDX_RIGHT_X])
266 packing_i1_top_y: Final[int] = int(packing[i1, IDX_TOP_Y])
267 min_left: int = packing_i1_left_x
268 for i0 in range(bin_start, bin_end):
269 # consider only objects that are not yet behind us and are in
270 # the same bin may intersect
271 if (packing[i0, IDX_BIN] != bin_id) \
272 or (packing[i0, IDX_LEFT_X] >= packing_i1_right_x):
273 continue # the object is already behind us, so it can be ignored
274 if (packing[i0, IDX_RIGHT_X] > packing_i1_left_x) \
275 and (packing[i0, IDX_LEFT_X] < packing_i1_right_x):
276 # we have a horizontal intersection with a box below
277 if packing[i0, IDX_TOP_Y] == packing_i1_bottom_y:
278 # only consider those the box *directly* below and move the
279 # right end of the new box to the left end of that box below
280 min_left = min(min_left, int(
281 packing_i1_right_x - packing[i0, IDX_LEFT_X]))
282 elif (packing_i1_top_y > packing[i0, IDX_BOTTOM_Y]) \
283 and (packing_i1_bottom_y < packing[i0, IDX_TOP_Y]):
284 min_left = min(min_left, int(
285 packing_i1_left_x - packing[i0, IDX_RIGHT_X]))
286 if min_left > 0:
287 # move the box to the left
288 packing[i1, IDX_LEFT_X] = packing_i1_left_x - min_left
289 packing[i1, IDX_RIGHT_X] = packing_i1_right_x - min_left
290 return True
291 return False
294@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
295def _decode(x: np.ndarray, y: np.ndarray, instance: np.ndarray,
296 bin_width: int, bin_height: int, bin_starts: np.ndarray,
297 bin_ends: np.ndarray) -> int:
298 """
299 Decode a (signed) permutation to a packing.
301 The permutation is processed from the beginning to the end.
302 Each element identifies one object by its ID. If the ID is negative,
303 the object will be inserted rotated by 90°. If the ID is positive, the
304 object will be inserted as is.
306 The absolute value of the ID-1 will be used to look up the width and
307 height of the object in the `instance` data. If the object needs to be
308 rotated, width and height will be swapped.
310 Each object is, at the beginning, placed with its right side at the right
311 end of the *first* bin. The bottom line of the object is initially put on
312 top of the bin, i.e., initially the object is outside of the bin.
314 Then, the object is iteratively moved downward *in the bin* as far as
315 possible. Once it reaches another object, we move it to the left until
316 either its right side reaches the left end of the object beneath it or
317 until its left side touches another object. Then we try to move the object
318 down again, and so on.
320 Once the object can no longer be moved down, we check if it is now fully
321 inside of *the bin*. If yes, then good, the object's bin index is set to
322 the ID of the current bin. If not, then we cannot place the object into
323 this bin. In this case, we move to the second bin an repeat the process.
324 If the object fits into the second bin, then it is placed in there and
325 we are finished. If not, we try the third bin, and so on.
327 If we cannot fit the object into any of the bins that already have other
328 objects, then we allocate a new empty bin. We move the object to the
329 bottom-left corner of this bin. In other words, the left side of the
330 object touches the left side of the bin, i.e., is `0`. The bottom-line
331 of the object is also the bottom of the bin, i.e., has coordinate `0` as
332 well.
334 :param x: a possibly signed permutation
335 :param y: the packing object
336 :param instance: the packing instance data
337 :param bin_width: the bin width
338 :param bin_height: the bin height
339 :param bin_starts: a temporary index holder array for bin starts
340 :param bin_ends: a temporary index holder array for bin ends
341 :returns: the number of bins
343 As example, we use a slightly modified version (we add more objects so we
344 get to see the use of a second bin) of Figure 2 of the Liu and Teng paper
345 "An Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing
346 of Rectangles."
348 >>> # [width, height, repetitions]
349 >>> inst = np.array([[10, 20, 5], [5, 5, 5]])
350 >>> # [id = plain, -id = rotated]
351 >>> xx = np.array([1, -1, 2, -2, 1, -2, -2, -1, -1, 2])
352 >>> # [id, bin, left-x, bottom-y, right-x, top-y] ...
353 >>> yy = np.empty((10, 6), int)
354 >>> binstarts = np.empty(10, int)
355 >>> binends = np.empty(10, int)
356 >>> print(_decode(xx, yy, inst, 30, 30, binstarts, binends))
357 2
358 >>> print(yy[0, :])
359 [ 1 1 0 0 10 20]
360 >>> print(yy[1, :])
361 [ 1 1 10 0 30 10]
362 >>> print(yy[2, :])
363 [ 2 1 10 10 15 15]
364 >>> print(yy[3, :])
365 [ 2 1 15 10 20 15]
366 >>> print(yy[4, :])
367 [ 1 1 20 10 30 30]
368 >>> print(yy[5, :])
369 [ 2 1 10 15 15 20]
370 >>> print(yy[6, :])
371 [ 2 1 15 15 20 20]
372 >>> print(yy[7, :])
373 [ 1 1 0 20 20 30]
374 >>> print(yy[8, :])
375 [ 1 2 0 0 20 10]
376 >>> print(yy[9, :])
377 [ 2 2 20 0 25 5]
378 """
379 w: int # the width of the current object
380 h: int # the height of the current object
381 use_id: int # the id of the current object
382 bin_id: int = 1 # the id of the current bin
383 bin_starts[0] = 0
384 bin_ends[0] = 0
385 for i, item_id in enumerate(x): # iterate over all objects
386 if item_id < 0: # object should be rotated
387 use_id = -(item_id + 1) # get absolute id - 1
388 w = int(instance[use_id, IDX_HEIGHT]) # width = height (rotated!)
389 h = int(instance[use_id, IDX_WIDTH]) # height = width (rotated!)
390 else: # the object will not be rotated
391 use_id = item_id - 1 # id - 1
392 w = int(instance[use_id, IDX_WIDTH]) # get width
393 h = int(instance[use_id, IDX_HEIGHT]) # get height
395# It could be that an object is too wide or too high for the bin in its
396# current rotation even if the bin was empty entirely. In this case, we simply
397# force-rotate it. A bin packing instance will not permit objects that do not
398# fit into the bin in any rotation. So if the object does not fit in its
399# current rotation, it must fit if we simply rotate it by 90°.
400 if (w > bin_width) or (h > bin_height):
401 w, h = h, w
403# At first, the object's right corner is at the right corner of the bin.
404# The object sits exactly at the top of the bin, i.e., its bottom line
405# is the top line of the bin.
406 y[i, IDX_ID] = use_id + 1 # the id of the object
408 not_found: bool = True
409 for item_bin in range(1, bin_id + 1): # iterate over all bins in use
410 bin_start = bin_starts[item_bin - 1] # index of first item in bin
411 bin_end = bin_ends[item_bin - 1] # index after last item in bin
412 y[i, IDX_LEFT_X] = bin_width - w # the left end
413 y[i, IDX_BOTTOM_Y] = bin_height # object sits on top of bin
414 y[i, IDX_RIGHT_X] = bin_width # object ends at right end of bin
415 y[i, IDX_TOP_Y] = bin_height + h # top of object is outside of bin
417 while __move_down(y, item_bin, int(bin_start), int(bin_end), i) \
418 or __move_left(y, item_bin, int(bin_start),
419 int(bin_end), i):
420 pass # loop until object can no longer be moved
422# Check if the object is completely inside the bin. If yes, we can put it
423# there and stop searching.
424 if (y[i, IDX_RIGHT_X] <= bin_width) \
425 and (y[i, IDX_TOP_Y] <= bin_height):
426 not_found = False # we found a placement, outer loop can stop
427 y[i, IDX_BIN] = item_bin # set the items bin
428 bin_ends[item_bin - 1] = i + 1 # index after last item in bin
429 break
431# If the object is not fully inside the current bin, we move to a new bin.
432 if not_found: # we did not find a spot in any of the bins
433 bin_starts[bin_id] = i # set the starting index of the new bin
434 bin_ends[bin_id] = i + 1 # set the end index of the new bin
435 bin_id += 1 # step to the next bin
436 y[i, IDX_LEFT_X] = 0 # the object goes to the left end of the bin
437 y[i, IDX_BOTTOM_Y] = 0 # the object goes to the bottom of the bin
438 y[i, IDX_RIGHT_X] = w # so its right end is its width
439 y[i, IDX_TOP_Y] = h # and its top end is its height
440 y[i, IDX_BIN] = bin_id # store the bin id
441 return int(bin_id) # return the total number of bins
444class ImprovedBottomLeftEncoding2(Encoding):
445 """An Improved Bottem Left Encoding by Liu and Teng for multiple bins."""
447 def __init__(self, instance: Instance) -> None:
448 """
449 Instantiate the improved best first encoding.
451 :param instance: the packing instance
452 """
453 if not isinstance(instance, Instance):
454 raise type_error(instance, "instance", Instance)
455 #: the internal instance reference
456 self.__instance: Final[Instance] = instance
457 #: the temporary array for holding bin start indexes
458 self.__bin_starts: Final[np.ndarray] = np.empty(
459 instance.n_items, instance.dtype)
460 #: the temporary array for holding bin end indexes
461 self.__bin_ends: Final[np.ndarray] = np.empty(
462 instance.n_items, instance.dtype)
464 def decode(self, x: np.ndarray, y: Packing) -> None:
465 """
466 Map a potentially signed permutation to a packing.
468 :param x: the array
469 :param y: the Gantt chart
470 """
471 y.n_bins = _decode(x, y, self.__instance, self.__instance.bin_width,
472 self.__instance.bin_height, self.__bin_starts,
473 self.__bin_ends)
475 def __str__(self) -> str:
476 """
477 Get the name of this encoding.
479 :return: `"ibf2"`
480 :rtype: str
481 """
482 return "ibf2"
484 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
485 """
486 Log all parameters of this component as key-value pairs.
488 :param logger: the logger for the parameters
489 """
490 super().log_parameters_to(logger)
491 with logger.scope(SCOPE_INSTANCE) as kv:
492 self.__instance.log_parameters_to(kv)