Coverage for moptipyapps / binpacking2d / encodings / ibl_encoding_1.py: 31%
87 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 implementation is given in
8:mod:`moptipyapps.binpacking2d.encodings.ibl_encoding_2`.
10An :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 bin and with its bottom line exactly at the top of the bin,
26i.e., outside of the bin. Then, in each step, we move the object as far down
27as 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 current bin, we place it at the
39bottom-left corner of a new bin. We therefore increase the bin counter.
40From now on, all the following objects will be placed into this bin until
41the bin is full as well, in which case we move to the next bin again.
42This means that the current bin is closed at the same moment the first
43object is encountered that does not fit into it anymore. Therefore,
44the objects in a closed bin do no longer need to be considered when packing
45subsequent objects.
47This is different from the second variant of this encoding implemented in file
48:mod:`moptipyapps.binpacking2d.encodings.ibl_encoding_2`, which always checks
49all the bins, starting at bin `1`, when placing any object. That other
50encoding variant therefore must always consider all bins and is thus slower,
51but tends to yield better packings.
53This procedure has originally been developed and implemented by Mr. Rui ZHAO
54(赵睿), <zr1329142665@163.com> a Master's student at the Institute of Applied
55Optimization (应用优化研究所) of the School of
56Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University
57(合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of
58Prof. Dr. Thomas Weise (汤卫思教授).
601. Dequan Liu and Hongfei Teng. An Improved BL-Algorithm for Genetic Algorithm
61 of the Orthogonal Packing of Rectangles. European Journal of Operational
62 Research. 112(2):413-420. January (1999).
63 https://doi.org/10.1016/S0377-2217(97)00437-2.
64 http://www.paper.edu.cn/scholar/showpdf/MUT2AN0IOTD0Mxxh.
65"""
66from typing import Final
68import numba # type: ignore
69import numpy as np
70from moptipy.api.encoding import Encoding
71from moptipy.utils.logger import KeyValueLogSection
72from pycommons.types import type_error
74from moptipyapps.binpacking2d.instance import (
75 IDX_HEIGHT,
76 IDX_WIDTH,
77 Instance,
78)
79from moptipyapps.binpacking2d.packing import (
80 IDX_BIN,
81 IDX_BOTTOM_Y,
82 IDX_ID,
83 IDX_LEFT_X,
84 IDX_RIGHT_X,
85 IDX_TOP_Y,
86 Packing,
87)
88from moptipyapps.utils.shared import SCOPE_INSTANCE
91@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
92def __move_down(packing: np.ndarray, bin_start: int, i1: int) -> bool:
93 """
94 Move the box at index `i1` down as far as possible in the current bin.
96 `bin_start` is the index of the first object that has already been placed
97 in the current bin. It always holds that `i1 >= bin_start`. In the case
98 that `i1 == bin_start`, then we can move the object directly to the bottom
99 of the bin without any issue.
101 If `i1 > bin_start` we iterate over all objects at indices
102 `bin_start...i1-1`. We first set `min_down` to the bottom-y coordinate of
103 the box, because this is how far down we can move at most. Then, for each
104 of the objects already placed in the bin, we check if there is any
105 intersection of the horizontal with the current box. If there is no
106 intersection *or* if the object is already above the current box, then the
107 object will not influence the downward movement of our object. If there is
108 an intersection, then we cannot move the current box deeper than the top-y
109 coordinate of the other box.
111 *Only* the box at index `i1` is modified and if it is modified, this
112 function will return `True`.
114 :param packing: the packing under construction
115 :param bin_start: the starting index of the current bin
116 :param i1: the index of the current box
117 :return: `True` if the object was moved down, `False` if the object cannot
118 be moved down any further because either it has reached the bottom or
119 because it would intersect with other objects
121 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
122 >>> r = np.array([[1, 1, 10, 20, 30, 40],
123 ... [2, 1, 30, 30, 50, 60],
124 ... [3, 1, 40, 100, 60, 200]])
125 >>> __move_down(r, 0, 2) # try to move down the box at index 2
126 True
127 >>> print(r[2, :])
128 [ 3 1 40 60 60 160]
129 >>> __move_down(r, 0, 2) # try to move down the box at index 2 again
130 False
131 >>> __move_down(r, 0, 1) # try to move down the box at index 1 (ignore 2)
132 True
133 >>> print(r[1, :])
134 [ 2 1 30 0 50 30]
135 >>> __move_down(r, 0, 1) # try to move down the box at index 1 again
136 False
137 >>> __move_down(r, 0, 2) # try to move down the box at index 2 again now
138 True
139 >>> print(r[2, :])
140 [ 3 1 40 30 60 130]
141 >>> __move_down(r, 0, 2) # try to move down the box at index 2 again
142 False
143 >>> __move_down(r, 0, 0)
144 True
145 >>> print(r[0, :])
146 [ 1 1 10 0 30 20]
147 >>> __move_down(r, 0, 0)
148 False
149 """
150 # load the coordinates of i1 into local variables to speed up computation
151 packing_i1_left_x: Final[int] = int(packing[i1, IDX_LEFT_X])
152 packing_i1_bottom_y: Final[int] = int(packing[i1, IDX_BOTTOM_Y])
153 packing_i1_right_x: Final[int] = int(packing[i1, IDX_RIGHT_X])
154 packing_i1_top_y: Final[int] = int(packing[i1, IDX_TOP_Y])
155 min_down: int = packing_i1_bottom_y # maximum move: down to bottom
156 for i0 in range(bin_start, i1): # iterate over all boxes in current bin
157 # An intersection exists if the right-x of an existing box is larger
158 # than the left-x of the new box AND if the left-x of the existing box
159 # is less than the right-x of the new box.
160 # Only intersections matter and only with objects not above us.
161 if (packing[i0, IDX_RIGHT_X] > packing_i1_left_x) and \
162 (packing[i0, IDX_LEFT_X] < packing_i1_right_x) and \
163 (packing[i0, IDX_BOTTOM_Y] < packing_i1_top_y):
164 # The object would horizontally intersect with the current object
165 min_down = min(min_down, int(
166 packing_i1_bottom_y - packing[i0, IDX_TOP_Y]))
167 if min_down > 0: # Can we move down? If yes, update box.
168 packing[i1, IDX_BOTTOM_Y] = packing_i1_bottom_y - min_down
169 packing[i1, IDX_TOP_Y] = packing_i1_top_y - min_down
170 return True
171 return False
174@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
175def __move_left(packing: np.ndarray, bin_start: int, i1: int) -> bool:
176 """
177 Move the box at index `i1` left as far as possible in the current bin.
179 This function moves a box to the left without changing its vertical
180 position. It is slightly more tricky than the downwards moving function,
181 because in the improved bottom left heuristic, downward moves are
182 preferred compared to left moves. This means that the box needs to be
183 stopped when reaching the edge of a box on whose top it sits.
185 This function is to be called *after* `__move_down` and in an alternating
186 fashion.
188 *Only* the box at index `i1` is modified and if it is modified, this
189 function will return `True`.
191 :param packing: the packing under construction
192 :param bin_start: the starting index of the current bin
193 :param i1: the index of the current box
194 :return: `True` if the object was moved down, `False` if the object cannot
195 be moved down any further because either it has reached the bottom or
196 because it would intersect with other objects
198 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
199 >>> r = np.array([[1, 1, 0, 0, 30, 10],
200 ... [2, 1, 35, 0, 45, 30],
201 ... [3, 1, 0, 10, 10, 20],
202 ... [4, 1, 40, 30, 50, 40]])
203 >>> __move_left(r, 0, 3)
204 True
205 >>> print(r[3, :])
206 [ 4 1 25 30 35 40]
207 >>> __move_left(r, 0, 3)
208 True
209 >>> print(r[3, :])
210 [ 4 1 0 30 10 40]
211 >>> r[3, :] = [4, 1, 25, 10, 35, 20]
212 >>> __move_left(r, 0, 3)
213 True
214 >>> print(r[3, :])
215 [ 4 1 10 10 20 20]
216 >>> __move_left(r, 0, 3)
217 False
218 >>> # itemID, binID, left-x, bottom-y, right-x, top-y
219 >>> r = np.array([[1, 1, 0, 0, 10, 2],
220 ... [2, 1, 10, 0, 20, 5],
221 ... [3, 1, 8, 2, 10, 4]])
222 >>> __move_left(r, 0, 2)
223 True
224 >>> print(r[2, :])
225 [3 1 0 2 2 4]
226 """
227 packing_i1_left_x: Final[int] = int(packing[i1, IDX_LEFT_X])
228 packing_i1_bottom_y: Final[int] = int(packing[i1, IDX_BOTTOM_Y])
229 packing_i1_right_x: Final[int] = int(packing[i1, IDX_RIGHT_X])
230 packing_i1_top_y: Final[int] = int(packing[i1, IDX_TOP_Y])
231 min_left: int = packing_i1_left_x
232 for i0 in range(bin_start, i1):
233 if packing[i0, IDX_LEFT_X] >= packing_i1_right_x:
234 continue # the object is already behind us, so it can be ignored
235 if (packing[i0, IDX_RIGHT_X] > packing_i1_left_x) \
236 and (packing[i0, IDX_LEFT_X] < packing_i1_right_x):
237 # we have a horizontal intersection with a box below
238 if packing[i0, IDX_TOP_Y] == packing_i1_bottom_y:
239 # only consider those the box *directly* below and move the
240 # right end of the new box to the left end of that box below
241 min_left = min(min_left, int(
242 packing_i1_right_x - packing[i0, IDX_LEFT_X]))
243 elif (packing_i1_top_y > packing[i0, IDX_BOTTOM_Y]) \
244 and (packing_i1_bottom_y < packing[i0, IDX_TOP_Y]):
245 min_left = min(min_left, int(
246 packing_i1_left_x - packing[i0, IDX_RIGHT_X]))
247 if min_left > 0:
248 # move the box to the left
249 packing[i1, IDX_LEFT_X] = packing_i1_left_x - min_left
250 packing[i1, IDX_RIGHT_X] = packing_i1_right_x - min_left
251 return True
252 return False
255@numba.njit(nogil=True, cache=True, inline="always", boundscheck=False)
256def _decode(x: np.ndarray, y: np.ndarray, instance: np.ndarray,
257 bin_width: int, bin_height: int) -> int:
258 """
259 Decode a (signed) permutation to a packing.
261 The permutation is processed from the beginning to the end.
262 Each element identifies one object by its ID. If the ID is negative,
263 the object will be inserted rotated by 90°. If the ID is positive, the
264 object will be inserted as is.
266 The absolute value of the ID-1 will be used to look up the width and
267 height of the object in the `instance` data. If the object needs to be
268 rotated, width and height will be swapped.
270 Each object is, at the beginning, placed with its right side at the right
271 end of the bin. The bottom line of the object is initially put on top of
272 the bin, i.e., initially the object is outside of the bin.
274 Then, the object is iteratively moved downward as far as possible. Once it
275 reaches another object, we move it to the left until either its right side
276 reaches the left end of the object beneath it or until its left side
277 touches another object. Then we try to move the object down again, and so
278 on.
280 Once the object can no longer be moved down, we check if it is now fully
281 inside of the bin. If yes, then good, the object's bin index is set to the
282 ID of the current bin. If not, then we cannot place the object into this
283 bin. In this case, we increase the bin ID by one. The object is put into
284 a new and empty bin. We move it to the bottom-left corner of this bin. In
285 other words, the left side of the object touches the left side of the bin,
286 i.e., is `0`. The bottom-line of the object is also the bottom of the bin,
287 i.e., has coordinate `0` as well.
289 All objects that are placed from now on will go into this bin until the
290 bin is full. Then we move on to the next bin, and so on. In other words,
291 once a bin is full, we no longer consider it for receiving any further
292 objects.
294 :param x: a possibly signed permutation
295 :param y: the packing object
296 :param instance: the packing instance data
297 :param bin_width: the bin width
298 :param bin_height: the bin height
299 :returns: the number of bins
301 As example, we use a slightly modified version (we add more objects so we
302 get to see the use of a second bin) of Figure 2 of the Liu and Teng paper
303 "An Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing
304 of Rectangles."
306 >>> # [width, height, repetitions]
307 >>> inst = np.array([[10, 20, 5], [5, 5, 5]])
308 >>> # [id = plain, -id = rotated]
309 >>> xx = np.array([1, -1, 2, -2, 1, -2, -2, -1, -1, 2])
310 >>> # [id, bin, left-x, bottom-y, right-x, top-y] ...
311 >>> yy = np.empty((10, 6), int)
312 >>> print(_decode(xx, yy, inst, 30, 30))
313 2
314 >>> print(yy[0, :])
315 [ 1 1 0 0 10 20]
316 >>> print(yy[1, :])
317 [ 1 1 10 0 30 10]
318 >>> print(yy[2, :])
319 [ 2 1 10 10 15 15]
320 >>> print(yy[3, :])
321 [ 2 1 15 10 20 15]
322 >>> print(yy[4, :])
323 [ 1 1 20 10 30 30]
324 >>> print(yy[5, :])
325 [ 2 1 10 15 15 20]
326 >>> print(yy[6, :])
327 [ 2 1 15 15 20 20]
328 >>> print(yy[7, :])
329 [ 1 1 0 20 20 30]
330 >>> print(yy[8, :])
331 [ 1 2 0 0 20 10]
332 >>> print(yy[9, :])
333 [ 2 2 20 0 25 5]
334 """
335 w: int # the width of the current object
336 h: int # the height of the current object
337 use_id: int # the id of the current object
338 bin_start: int = 0 # the index of the first object in the current bin
339 bin_id: int = 1 # the id of the current bin
340 for i, item_id in enumerate(x): # iterate over all objects
341 if item_id < 0: # object should be rotated
342 use_id = -(item_id + 1) # get absolute id - 1
343 w = int(instance[use_id, IDX_HEIGHT]) # width = height (rotated!)
344 h = int(instance[use_id, IDX_WIDTH]) # height = width (rotated!)
345 else: # the object will not be rotated
346 use_id = item_id - 1 # id - 1
347 w = int(instance[use_id, IDX_WIDTH]) # get width
348 h = int(instance[use_id, IDX_HEIGHT]) # get height
350# It could be that an object is too wide or too high for the bin in its
351# current rotation even if the bin was empty entirely. In this case, we simply
352# force-rotate it. A bin packing instance will not permit objects that do not
353# fit into the bin in any rotation. So if the object does not fit in its
354# current rotation, it must fit if we simply rotate it by 90°.
355 if (w > bin_width) or (h > bin_height):
356 w, h = h, w
358# At first, the object's right corner is at the right corner of the bin.
359# The object sits exactly at the top of the bin, i.e., its bottom line
360# is the top line of the bin.
361 y[i, IDX_ID] = use_id + 1 # the id of the object
362 y[i, IDX_LEFT_X] = bin_width - w # the left end
363 y[i, IDX_BOTTOM_Y] = bin_height # object sits on top of bin
364 y[i, IDX_RIGHT_X] = bin_width # object ends at right end of bin
365 y[i, IDX_TOP_Y] = bin_height + h # top of object is outside of bin
367 while __move_down(y, bin_start, i) or __move_left(y, bin_start, i):
368 pass # loop until object can no longer be moved
370# If the object is not fully inside the current bin, we move to a new bin.
371 if (y[i, IDX_RIGHT_X] > bin_width) or (y[i, IDX_TOP_Y] > bin_height):
372 bin_id += 1 # step to the next bin
373 bin_start = i # set the starting index of the bin
374 y[i, IDX_LEFT_X] = 0 # the object goes to the left end of the bin
375 y[i, IDX_BOTTOM_Y] = 0 # the object goes to the bottom of the bin
376 y[i, IDX_RIGHT_X] = w # so its right end is its width
377 y[i, IDX_TOP_Y] = h # and its top end is its height
378 y[i, IDX_BIN] = bin_id # store the bin id
379 return int(bin_id) # return the total number of bins
382class ImprovedBottomLeftEncoding1(Encoding):
383 """An Improved Bottem Left Encoding by Liu and Teng for multiple bins."""
385 def __init__(self, instance: Instance) -> None:
386 """
387 Instantiate the improved best first encoding.
389 :param instance: the packing instance
390 """
391 if not isinstance(instance, Instance):
392 raise type_error(instance, "instance", Instance)
393 #: the internal instance reference
394 self.__instance: Final[Instance] = instance
396 def decode(self, x: np.ndarray, y: Packing) -> None:
397 """
398 Map a potentially signed permutation to a packing.
400 :param x: the array
401 :param y: the Gantt chart
402 """
403 y.n_bins = _decode(x, y, self.__instance, self.__instance.bin_width,
404 self.__instance.bin_height)
406 def __str__(self) -> str:
407 """
408 Get the name of this encoding.
410 :return: `"ibf1"`
411 :rtype: str
412 """
413 return "ibf1"
415 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
416 """
417 Log all parameters of this component as key-value pairs.
419 :param logger: the logger for the parameters
420 """
421 super().log_parameters_to(logger)
422 with logger.scope(SCOPE_INSTANCE) as kv:
423 self.__instance.log_parameters_to(kv)