Coverage for moptipyapps / binpacking2d / instgen / errors.py: 95%
88 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2An objective function counting deviations from the instance definition.
4This objective function will be the smaller, the closer the structure
5of an instance is to the original instance.
6Due to our encoding, we create instances whose bin width, bin height,
7and the number of items is the same as in an existing instance. The
8lower bound for the required number of bins is also the same.
10This objective function here also incorporates some additional features, such
11as:
131. Is the number of different items similar to those in the original instance?
14 In an existing instance, some items of same width and height could be
15 grouped together. We may have 10 items to pack, but only 3 different item
16 sizes exist. We here compare the number of different item sizes of a
17 generated instance with the number in the instance definition.
182. In a given instance, we can observe the minimum and maximum width and
19 height of any item. If an item in the generated instance is smaller than
20 the minimum or larger than the maximum permitted value in one dimension,
21 this will increase the error count.
223. Additionally, we want the actual minimum and maximum width and height of
23 any item in the generated instance is the same as in the original instance.
244. Finally, we want that the total area covered by all items is the same in
25 the generated instance as in the original instance.
27All of these potential violations are counted and added up. Using this
28objective function should drive the search towards generating instances that
29are structurally similar to an existing instance, at least in some parameters.
31We could push this arbitrarily further, trying to emulate the exact
32distribution of the item sizes, etc. But this may just lead to the
33reproduction of the original instance by the search and not add anything
34interesting.
36>>> orig = Instance.from_resource("a04")
37>>> space = InstanceSpace(orig)
38>>> print(f"{space.inst_name!r} with {space.n_different_items}/"
39... f"{space.n_items} items with area {space.total_item_area} "
40... f"in {space.min_bins} bins of "
41... f"size {space.bin_width}*{space.bin_height}.")
42'a04n' with 2/16 items with area 7305688 in 3 bins of size 2750*1220.
44>>> from moptipyapps.binpacking2d.instgen.inst_decoding import InstanceDecoder
45>>> decoder = InstanceDecoder(space)
46>>> import numpy as np
47>>> x = np.array([ 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,
48... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,
49... 0.0, 0.2, -0.1, 0.3, 0.5, -0.6, -0.7, 0.9,
50... 0.0, 0.2, ])
51>>> y = space.create()
52>>> decoder.decode(x, y)
53>>> space.validate(y)
54>>> res: Instance = y[0]
55>>> print(f"{res.name!r} with {res.n_different_items}/"
56... f"{res.n_items} items with area {res.total_item_area} "
57... f"in {res.lower_bound_bins} bins of "
58... f"size {res.bin_width}*{res.bin_height}.")
59'a04n' with 15/16 items with area 10065000 in 3 bins of size 2750*1220.
61>>> print(space.to_str(y))
62a04n;15;2750;1220;1101,1098;2750,244;2750,98;1101,171;1649,171;2750,976;\
63441,122;1649,122;2750,10;2750,1,2;2750,3;1649,1098;2750,878;2750,58;660,122
65>>> errors = Errors(space)
66>>> errors.lower_bound()
670.0
68>>> errors.upper_bound()
691.0
70>>> errors.evaluate(y)
710.614714632631273
73>>> y[0] = orig
74>>> errors.evaluate(y)
750.0
76"""
77from math import sqrt
78from typing import Final
80from moptipy.api.objective import Objective
81from moptipy.utils.logger import KeyValueLogSection
82from pycommons.types import type_error
84from moptipyapps.binpacking2d.instance import (
85 IDX_HEIGHT,
86 IDX_REPETITION,
87 IDX_WIDTH,
88 Instance,
89)
90from moptipyapps.binpacking2d.instgen.instance_space import InstanceSpace
93class Errors(Objective):
94 """Compute the deviation of an instance from the definition."""
96 def __init__(self, space: InstanceSpace) -> None:
97 """
98 Initialize the errors objective function.
100 :param instance: the instance to load the bounds from
101 """
102 super().__init__()
103 if not isinstance(space, InstanceSpace):
104 raise type_error(space, "space", InstanceSpace)
105 #: the instance description
106 self.space: Final[InstanceSpace] = space
108 # These errors are permitted.
109 max_errors: int = max(
110 space.n_different_items - 1,
111 space.n_items - space.n_different_items - 1)
113 goal_min_width: Final[int] = space.item_width_min
114 goal_max_width: Final[int] = space.item_width_max
115 goal_min_height: Final[int] = space.item_height_min
116 goal_max_height: Final[int] = space.item_height_max
117 bin_width: Final[int] = space.bin_width
118 bin_height: Final[int] = space.bin_height
120 n_items: Final[int] = space.n_items
121 max_errors += n_items * max(
122 goal_min_width - 1, bin_width - goal_max_width)
123 max_errors += n_items * max(
124 goal_min_height - 1, bin_height - goal_max_height)
125 max_errors += max(goal_min_width, bin_width - goal_min_width)
126 max_errors += max(goal_max_width, bin_width - goal_max_width)
127 max_errors += max(goal_min_height, bin_height - goal_min_height)
128 max_errors += max(goal_max_height, bin_height - goal_max_height)
130 alt_area: Final[int] = (space.min_bins * bin_width * bin_height
131 - space.total_item_area)
132 if alt_area < 0:
133 raise ValueError("Invalid item area in space?")
134 max_errors += max(space.total_item_area, alt_area)
136 #: the maximum number of errors
137 self.__max_errors: Final[int] = max_errors
139 def evaluate(self, x: list[Instance] | Instance) -> float:
140 """
141 Compute the deviations from the instance definition.
143 :param x: the instance
144 :return: the number of deviations divided by the maximum of
145 the deviations
146 """
147 errors: int = 0
148 inst: Final[Instance] = x[0] if isinstance(x, list) else x
149 space: Final[InstanceSpace] = self.space
151 # Some errors are not permitted.
152 errors += abs(inst.bin_width - space.bin_width) # should be 0!
153 errors += abs(inst.bin_height - space.bin_height) # should be 0!
154 errors += abs(inst.n_items - space.n_items) # should be 0!
155 if errors > 0:
156 raise ValueError(
157 f"Instance {inst} is inconsistent with space {space}.")
159 # These errors are permitted.
160 n_different: Final[int] = inst.n_different_items
161 errors += abs(n_different - space.n_different_items) # > 0
162 goal_min_width: Final[int] = space.item_width_min
163 goal_max_width: Final[int] = space.item_width_max
164 goal_min_height: Final[int] = space.item_height_min
165 goal_max_height: Final[int] = space.item_height_max
167 actual_min_width: int = space.bin_width
168 actual_max_width: int = 0
169 actual_min_height: int = space.bin_height
170 actual_max_height: int = 0
171 total_area: int = 0
173 for row in range(n_different):
174 width: int = int(inst[row, IDX_WIDTH])
175 height: int = int(inst[row, IDX_HEIGHT])
176 actual_min_width = min(actual_min_width, width)
177 actual_max_width = max(actual_max_width, width)
178 actual_min_height = min(actual_min_height, height)
179 actual_max_height = max(actual_max_height, height)
181 n: int = int(inst[row, IDX_REPETITION])
182 total_area += n * width * height
183 if width < goal_min_width:
184 errors += n * (goal_min_width - width)
185 elif width > goal_max_width:
186 errors += n * (width - goal_max_width)
187 if height < goal_min_height:
188 errors += n * (goal_min_height - height)
189 elif height > goal_max_height:
190 errors += n * (height - goal_max_height)
192 errors += abs(actual_min_width - goal_min_width)
193 errors += abs(actual_max_width - goal_max_width)
194 errors += abs(actual_min_height - goal_min_height)
195 errors += abs(actual_max_height - goal_max_height)
197 if total_area != inst.total_item_area:
198 raise ValueError("Invalid total area?")
199 errors += abs(total_area - space.total_item_area)
201 return max(0.0, min(1.0, sqrt(errors / self.__max_errors)))
203 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
204 """
205 Log the parameters of this instance.
207 :param logger: the logger
208 """
209 super().log_parameters_to(logger)
210 logger.key_value("maxErrors", self.__max_errors)
212 def lower_bound(self) -> float:
213 """
214 Get the lower bound of the instance template deviations.
216 :returs 0.0: always
217 """
218 return 0.0
220 def is_always_integer(self) -> bool:
221 """
222 Return `True` because there are only integer errors.
224 :retval False: always
225 """
226 return False
228 def upper_bound(self) -> float:
229 """
230 Get the upper bound of the number of deviations.
232 :returs 1.0: always
233 """
234 return 1.0
236 def __str__(self) -> str:
237 """
238 Get the name of the errors objective function.
240 :return: `errors`
241 :retval "errors": always
242 """
243 return "errors"