Coverage for moptipyapps / binpacking2d / packing_space.py: 89%
100 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2Here we provide a :class:`~moptipy.api.space.Space` of bin packings.
4The bin packing object is defined in module
5:mod:`~moptipyapps.binpacking2d.packing`. Basically, it is a
6two-dimensional numpy array holding, for each item, its ID, its bin ID, as
7well as its location defined by four coordinates.
91. Dequan Liu and Hongfei Teng. An Improved BL-Algorithm for Genetic Algorithm
10 of the Orthogonal Packing of Rectangles. European Journal of Operational
11 Research. 112(2):413-420. January (1999).
12 https://doi.org/10.1016/S0377-2217(97)00437-2.
13 http://www.paper.edu.cn/scholar/showpdf/MUT2AN0IOTD0Mxxh.
14"""
15from collections import Counter
16from math import factorial
17from typing import Final
19import numpy as np
20from moptipy.api.space import Space
21from moptipy.utils.logger import CSV_SEPARATOR, KeyValueLogSection
22from pycommons.types import check_int_range, type_error
24from moptipyapps.binpacking2d.instance import (
25 IDX_HEIGHT,
26 IDX_REPETITION,
27 IDX_WIDTH,
28 Instance,
29)
30from moptipyapps.binpacking2d.packing import (
31 IDX_BIN,
32 IDX_BOTTOM_Y,
33 IDX_ID,
34 IDX_LEFT_X,
35 IDX_RIGHT_X,
36 IDX_TOP_Y,
37 Packing,
38)
39from moptipyapps.utils.shared import SCOPE_INSTANCE
42class PackingSpace(Space):
43 """An implementation of the `Space` API of for 2D bin packings charts."""
45 def __init__(self, instance: Instance) -> None:
46 """
47 Create a 2D packing space.
49 :param instance: the 2d bin packing instance
51 >>> inst = Instance.from_resource("a01")
52 >>> space = PackingSpace(inst)
53 >>> space.instance is inst
54 True
55 """
56 if not isinstance(instance, Instance):
57 raise type_error(instance, "instance", Instance)
58 #: The instance to which the packings apply.
59 self.instance: Final[Instance] = instance
61 def copy(self, dest: Packing, source: Packing) -> None:
62 """
63 Copy one packing to another one.
65 :param dest: the destination packing
66 :param source: the source packing
67 """
68 np.copyto(dest, source)
69 dest.n_bins = source.n_bins
71 def create(self) -> Packing:
72 """
73 Create a packing object without assigning items to locations.
75 :return: the (empty, uninitialized) packing object
77 >>> inst = Instance.from_resource("a01")
78 >>> space = PackingSpace(inst)
79 >>> x = space.create()
80 >>> x.shape
81 (24, 6)
82 >>> x.instance is inst
83 True
84 >>> type(x)
85 <class 'moptipyapps.binpacking2d.packing.Packing'>
86 """
87 return Packing(self.instance)
89 def to_str(self, x: Packing) -> str:
90 """
91 Convert a packing to a string.
93 :param x: the packing
94 :return: a string corresponding to the flattened packing array
96 >>> inst = Instance.from_resource("a01")
97 >>> space = PackingSpace(inst)
98 >>> y = space.create()
99 >>> xx = np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
100 ... 1, 2, 2, 2, 2, 2, 2])
101 >>> import moptipyapps.binpacking2d.encodings.ibl_encoding_1 as e
102 >>> e._decode(xx, y, inst, inst.bin_width, inst.bin_height)
103 5
104 >>> space.to_str(y)
105 '1;1;0;0;463;386;1;1;463;0;926;386;1;1;926;0;1389;386;\
1061;1;1389;0;1852;386;1;1;1852;0;2315;386;1;1;0;386;463;772;\
1071;1;463;386;926;772;1;1;926;386;1389;772;1;1;1389;386;1852;772;\
1081;1;1852;386;2315;772;1;1;0;772;463;1158;1;1;463;772;926;1158;\
1091;1;926;772;1389;1158;1;1;1389;772;1852;1158;1;1;1852;772;2315;1158;\
1101;2;0;0;463;386;1;2;463;0;926;386;1;2;926;0;1389;386;2;2;0;386;1680;806;\
1112;3;0;0;1680;420;2;3;0;420;1680;840;2;4;0;0;1680;420;2;4;0;420;1680;840;\
1122;5;0;0;1680;420'
113 """
114 return CSV_SEPARATOR.join([str(xx) for xx in np.nditer(x)])
116 def is_equal(self, x1: Packing, x2: Packing) -> bool:
117 """
118 Check if two bin packings have the same contents.
120 :param x1: the first packing
121 :param x2: the second packing
122 :return: `True` if both packings are for the same instance and have the
123 same structure
125 >>> inst = Instance.from_resource("a01")
126 >>> space = PackingSpace(inst)
127 >>> y1 = space.create()
128 >>> y1.fill(0)
129 >>> y2 = space.create()
130 >>> y2.fill(0)
131 >>> space.is_equal(y1, y2)
132 True
133 >>> y1 is y2
134 False
135 >>> y1[0, 0] = 1
136 >>> space.is_equal(y1, y2)
137 False
138 """
139 return (x1.instance is x2.instance) and np.array_equal(x1, x2)
141 def from_str(self, text: str) -> Packing:
142 """
143 Convert a string to a packing.
145 :param text: the string
146 :return: the packing
148 >>> inst = Instance.from_resource("a01")
149 >>> space = PackingSpace(inst)
150 >>> y1 = space.create()
151 >>> xx = np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
152 ... 1, 2, 2, 2, 2, 2, 2])
153 >>> import moptipyapps.binpacking2d.encodings.ibl_encoding_1 as e
154 >>> y1.n_bins = e._decode(
155 ... xx, y1, inst, inst.bin_width, inst.bin_height)
156 >>> y2 = space.from_str(space.to_str(y1))
157 >>> space.is_equal(y1, y2)
158 True
159 >>> y1 is y2
160 False
161 """
162 if not isinstance(text, str):
163 raise type_error(text, "packing text", str)
164 x: Final[Packing] = self.create()
165 np.copyto(x, np.fromstring(text, dtype=x.dtype, sep=CSV_SEPARATOR)
166 .reshape(x.shape))
167 x.n_bins = int(x[:, IDX_BIN].max())
168 self.validate(x)
169 return x
171 def validate(self, x: Packing) -> None:
172 """
173 Check if a packing is valid and feasible.
175 This method performs a comprehensive feasibility and sanity check of
176 a packing. It ensures that the packing could be implemented in the
177 real world exactly as it is given here and that all data are valid and
178 that it matches to the bin packing instance. This includes:
180 - checking that all data types, numpy `dtypes`, and matrix shapes are
181 correct
182 - checking that the packing belongs to the same instance as this space
183 - checking that no objects in the same bin overlap
184 - checking that all objects occur exactly as often as prescribed by
185 the instance
186 - checking that no object extends outside of its bin
187 - checking that all objects have the same width/height as prescribed
188 in the instance (with possible rotations)
189 - check that bin ids are assigned starting at `1` and incrementing in
190 steps of `1`
192 :param x: the packing
193 :raises TypeError: if any component of the packing is of the wrong
194 type
195 :raises ValueError: if the packing is not feasible
196 """
197 if not isinstance(x, Packing):
198 raise type_error(x, "x", Packing)
199 inst: Final[Instance] = self.instance
200 if inst is not x.instance:
201 raise ValueError(
202 f"x.instance must be {inst} but is {x.instance}.")
203 if inst.dtype is not x.dtype:
204 raise ValueError(
205 f"inst.dtype = {inst.dtype} but x.dtype={x.dtype}")
206 needed_shape: Final[tuple[int, int]] = (inst.n_items, 6)
207 if x.shape != needed_shape:
208 raise ValueError(f"x.shape={x.shape}, but must be {needed_shape}.")
210 bin_width: Final[int] = check_int_range(
211 inst.bin_width, "bin_width", 1, 1_000_000_000)
212 bin_height: Final[int] = check_int_range(
213 inst.bin_height, "bin_height", 1, 1_000_000_000)
215 bins: Final[set[int]] = set()
216 items: Final[Counter[int]] = Counter()
218 for i in range(inst.n_items):
219 item_id: int = int(x[i, IDX_ID])
220 if (item_id <= 0) or (item_id > inst.n_different_items):
221 raise ValueError(
222 f"Encountered invalid id={item_id} for object at index "
223 f"{i}, must be in 1..{inst.n_different_items}.")
225 bin_id: int = int(x[i, IDX_BIN])
226 if (bin_id <= 0) or (bin_id > inst.n_items):
227 raise ValueError(
228 f"Encountered invalid bin-id={bin_id} for object at index"
229 f" {i}, must be in 1..{inst.n_items}.")
230 bins.add(bin_id)
232 items[item_id] += 1
233 x_left: int = int(x[i, IDX_LEFT_X])
234 y_bottom: int = int(x[i, IDX_BOTTOM_Y])
235 x_right: int = int(x[i, IDX_RIGHT_X])
236 y_top: int = int(x[i, IDX_TOP_Y])
238 if (x_left >= x_right) or (y_bottom >= y_top):
239 raise ValueError(
240 f"Invalid item coordinates ({x_left}, {y_bottom}, "
241 f"{x_right}, {y_top}) for item of id {item_id} at index"
242 f" {i}.")
243 if (x_left < 0) or (y_bottom < 0) or (x_right > bin_width) \
244 or (y_top > bin_height):
245 raise ValueError(
246 f"Item coordinates ({x_left}, {y_bottom}, {x_right}, "
247 f"{y_top}) for item of id {item_id} at index {i} extend "
248 f"outside of the bin ({bin_width}, {bin_height}).")
250 real_width: int = x_right - x_left
251 real_height: int = y_top - y_bottom
252 width: int = int(inst[item_id - 1, IDX_WIDTH])
253 height: int = int(inst[item_id - 1, IDX_HEIGHT])
255 if ((real_width != width) or (real_height != height)) \
256 and ((real_width != height) and (real_height != width)):
257 raise ValueError(
258 f"Item coordinates ({x_left}, {y_bottom}, {x_right}, "
259 f"{y_top}) mean width={real_width} and height="
260 f"{real_height} for item of id {item_id} at index {i}, "
261 f"which should have width={width} and height={height}.")
263 for j in range(inst.n_items):
264 if (int(x[j, IDX_BIN]) != bin_id) or (i == j):
265 continue
266 x_left_2: int = int(x[j, IDX_LEFT_X])
267 y_bottom_2: int = int(x[j, IDX_BOTTOM_Y])
268 x_right_2: int = int(x[j, IDX_RIGHT_X])
269 y_top_2: int = int(x[j, IDX_TOP_Y])
270 if (x_left_2 < x_right) and (x_right_2 > x_left) \
271 and (y_bottom_2 < y_top) and (y_top_2 > y_bottom):
272 raise ValueError(
273 f"Item {x[j, IDX_ID]} in bin {bin_id} and at index "
274 f"{j} is ({x_left_2}, {y_bottom_2}, {x_right_2}, "
275 f"{y_top_2}) and thus intersects with item {item_id} "
276 f"at index {i} which is in the same bin at ({x_left},"
277 f" {y_bottom}, {x_right}, {y_top}).")
279 for item_id, count in items.items():
280 should: int = int(inst[item_id - 1, IDX_REPETITION])
281 if should != count:
282 raise ValueError(
283 f"Item {item_id} should occur {should} times, but occurs"
284 f" {count} times instead.")
286 max_bin: Final[int] = max(bins)
287 min_bin: Final[int] = min(bins)
288 bin_count: Final[int] = len(bins)
290 if (min_bin != 1) or ((max_bin - min_bin + 1) != bin_count):
291 raise ValueError(
292 f"Inconsistent use of bins. Found bins {sorted(bins)}.")
294 if not isinstance(x.n_bins, int):
295 raise type_error(x.n_bins, "x.n_bins", int)
296 if x.n_bins != bin_count:
297 raise ValueError(f"x.n_bins={x.n_bins}, but must be {bin_count}.")
299 def n_points(self) -> int:
300 """
301 Get the number of possible packings.
303 If we indeed consider that any object could be at any place, then
304 there would be an incomprehensibly large number of possible packings.
305 Here, we consider the bottom-left condition and the idea of encoding
306 packings as signed permutations, as in the Liu and Teng paper "An
307 Improved BL-Algorithm for Genetic Algorithm of the Orthogonal Packing
308 of Rectangles." In this case, if `n` items are to be packed, the
309 number of possible packings won't exceed `2^n * n!`.
311 :return: the approximate number of packings
313 >>> inst = Instance.from_resource("a01")
314 >>> inst.n_items
315 24
316 >>> space = PackingSpace(inst)
317 >>> space.n_points()
318 10409396852733332453861621760000
319 >>> from math import factorial
320 >>> (2 ** 24) * factorial(24)
321 10409396852733332453861621760000
322 """
323 return (2 ** self.instance.n_items) * factorial(self.instance.n_items)
325 def __str__(self) -> str:
326 """
327 Get the name of the packing space.
329 :return: the name
331 >>> print(PackingSpace(Instance.from_resource("a10")))
332 pack_a10
333 """
334 return f"pack_{self.instance}"
336 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
337 """
338 Log the parameters of the space to the given logger.
340 :param logger: the logger for the parameters
341 """
342 super().log_parameters_to(logger)
343 with logger.scope(SCOPE_INSTANCE) as kv:
344 self.instance.log_parameters_to(kv)