Coverage for moptipyapps / tests / on_binpacking2d.py: 73%

1"""Perform tests on the Two-Dimensional Bin Packing Problem.""" 

2 

3from time import monotonic_ns 

4from typing import Callable, Final, Iterable, cast 

5 

6import numpy as np 

7import numpy.random as rnd 

8from moptipy.api.algorithm import Algorithm 

9from moptipy.api.encoding import Encoding 

10from moptipy.api.objective import Objective 

11from moptipy.operators.signed_permutations.op0_shuffle_and_flip import ( 

12 Op0ShuffleAndFlip, 

13) 

14from moptipy.spaces.signed_permutations import SignedPermutations 

15from moptipy.tests.algorithm import validate_algorithm 

16from moptipy.tests.encoding import validate_encoding 

17from moptipy.tests.objective import validate_objective 

18from moptipy.tests.space import validate_space 

19from numpy.random import Generator, default_rng 

20from pycommons.types import type_error 

21 

22from moptipyapps.binpacking2d.encodings.ibl_encoding_1 import ( 

23 ImprovedBottomLeftEncoding1, 

24) 

25from moptipyapps.binpacking2d.encodings.ibl_encoding_2 import ( 

26 ImprovedBottomLeftEncoding2, 

27) 

28from moptipyapps.binpacking2d.instance import Instance 

29from moptipyapps.binpacking2d.objectives.bin_count_and_last_empty import ( 

30 BinCountAndLastEmpty, 

31) 

32from moptipyapps.binpacking2d.packing import Packing 

33from moptipyapps.binpacking2d.packing_space import PackingSpace 

34 

35#: the internal random number generator 

36__RANDOM: Final[Generator] = default_rng() 

37 

38 

39def binpacking_instances_for_tests( 

40 random: Generator = __RANDOM) -> Iterable[str]: 

41 """ 

42 Get a sequence of 2D Bin Packing instances to test on. 

43 

44 :param random: the random number generator to use 

45 :returns: an iterable of 2D Bin Packing instance names 

46 """ 

47 ri = random.integers 

48 insts: set[str] = { 

49 "a04", "a08", "beng10", f"a0{ri(1, 10)}", f"a1{ri(1, 10)}", 

50 f"a2{ri(1, 10)}", f"a3{ri(1, 10)}", f"a4{ri(1, 4)}", 

51 f"beng0{ri(1, 10)}", f"cl01_080_0{ri(1, 10)}", 

52 f"cl06_020_0{ri(1, 10)}", f"cl09_040_0{ri(1, 10)}", 

53 f"cl10_100_0{ri(1, 10)}"} 

54 insn: list[str] = list(Instance.list_resources()) 

55 while len(insts) < 16: 

56 insts.add(insn.pop(ri(len(insn)))) 

57 use_insts: list[str] = list(insts) 

58 random.shuffle(cast("list", use_insts)) 

59 return use_insts 

60 

61 

62def make_packing_valid(inst: Instance, 

63 random: Generator = __RANDOM) \ 

64 -> Callable[[Generator, Packing], Packing]: 

65 """ 

66 Make a function that creates valid packings. 

67 

68 :param inst: the two-dimensional bin packing instance 

69 :param random: the random number generator to use 

70 :returns: a function that can make packings valid 

71 """ 

72 search_space = SignedPermutations(inst.get_standard_item_sequence()) 

73 encoding = (ImprovedBottomLeftEncoding1 if random.integers(2) == 0 

74 else ImprovedBottomLeftEncoding2)(inst) 

75 op0 = Op0ShuffleAndFlip(search_space) 

76 

77 def __make_valid(ra: rnd.Generator, 

78 y: Packing, ss=search_space, 

79 en=encoding, o0=op0) -> Packing: 

80 x = ss.create() 

81 o0.op0(ra, x) 

82 en.decode(x, y) 

83 return y 

84 

85 return __make_valid 

86 

87 

88def make_packing_invalid(random: Generator = __RANDOM) \ 

89 -> Callable[[Packing], Packing]: 

90 """ 

91 Make a function that creates invalid packings. 

92 

93 :param random: the random number generator to use 

94 :returns: a function that can make packings invalid 

95 """ 

96 

97 def __make_invalid(x: Packing, ri=random.integers) -> Packing: 

98 not_finished: bool = True 

99 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

100 while not_finished: 

101 while ri(2) == 0: 

102 if monotonic_ns() >= end_time: 

103 x[0, 0] = -1 

104 return x 

105 x[ri(len(x)), ri(6)] = -1 

106 not_finished = False 

107 while ri(2) == 0: 

108 second = first = ri(len(x)) 

109 while second == first: 

110 if monotonic_ns() >= end_time: 

111 x[0, 0] = -1 

112 return x 

113 second = ri(len(x)) 

114 x[first, 1] = x[second, 1] 

115 x[first, 2] = x[second, 2] - 1 

116 x[first, 3] = x[second, 3] - 1 

117 x[first, 4] = x[second, 4] + 1 

118 x[first, 5] = x[second, 5] + 1 

119 return x 

120 

121 return __make_invalid 

122 

123 

124def validate_algorithm_on_1_2dbinpacking( 

125 algorithm: Algorithm | Callable[ 

126 [Instance, SignedPermutations, Objective], Algorithm], 

127 instance: str | None = None, max_fes: int = 100, 

128 random: Generator = __RANDOM) -> None: 

129 """ 

130 Check the validity of a black-box algorithm on the 2d bin packing. 

131 

132 :param algorithm: the algorithm or algorithm factory 

133 :param instance: the instance name, or `None` to randomly pick one 

134 :param max_fes: the maximum number of FEs 

135 :param random: the default random generator to use 

136 """ 

137 if not (isinstance(algorithm, Algorithm) or callable(algorithm)): 

138 raise type_error(algorithm, "algorithm", Algorithm, True) 

139 if instance is None: 

140 instance = str(random.choice(Instance.list_resources())) 

141 if not isinstance(instance, str): 

142 raise type_error(instance, "bin packing instance name", (str, None)) 

143 inst = Instance.from_resource(instance) 

144 if not isinstance(inst, Instance): 

145 raise type_error(inst, f"loaded bin packing instance {instance!r}", 

146 Instance) 

147 

148 search_space = SignedPermutations(inst.get_standard_item_sequence()) 

149 solution_space = PackingSpace(inst) 

150 encoding = (ImprovedBottomLeftEncoding1 if random.integers(2) == 0 

151 else ImprovedBottomLeftEncoding2)(inst) 

152 objective = BinCountAndLastEmpty(inst) 

153 if callable(algorithm): 

154 algorithm = algorithm(inst, search_space, objective) 

155 if not isinstance(algorithm, Algorithm): 

156 raise type_error(algorithm, "algorithm", Algorithm, call=True) 

157 

158 validate_algorithm(algorithm=algorithm, 

159 solution_space=solution_space, 

160 objective=objective, 

161 search_space=search_space, 

162 encoding=encoding, 

163 max_fes=max_fes) 

164 

165 

166def validate_algorithm_on_2dbinpacking( 

167 algorithm: Callable[[Instance, SignedPermutations, 

168 Objective], Algorithm], 

169 max_fes: int = 100, random: Generator = __RANDOM) -> None: 

170 """ 

171 Validate an algorithm on a set of bin packing instances. 

172 

173 :param algorithm: the algorithm factory 

174 :param max_fes: the maximum FEs 

175 :param random: the random number generator 

176 """ 

177 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

178 for i in binpacking_instances_for_tests(random): 

179 if monotonic_ns() >= end_time: 

180 break 

181 validate_algorithm_on_1_2dbinpacking(algorithm, i, max_fes, random) 

182 

183 

184def validate_objective_on_1_2dbinpacking( 

185 objective: Objective | Callable[[Instance], Objective], 

186 instance: str | None = None, 

187 random: Generator = __RANDOM) -> None: 

188 """ 

189 Validate an objective function on 1 2D bin packing instance. 

190 

191 :param objective: the objective function or a factory creating it 

192 :param instance: the instance name 

193 :param random: the random number generator 

194 """ 

195 if instance is None: 

196 instance = str(random.choice(Instance.list_resources())) 

197 if not isinstance(instance, str): 

198 raise type_error(instance, "bin packing instance name", (str, None)) 

199 inst = Instance.from_resource(instance) 

200 if not isinstance(inst, Instance): 

201 raise type_error(inst, f"loaded bin packing instance {instance!r}", 

202 Instance) 

203 

204 if callable(objective): 

205 objective = objective(inst) 

206 

207 validate_objective( 

208 objective=objective, 

209 solution_space=PackingSpace(inst), 

210 make_solution_space_element_valid=make_packing_valid(inst), 

211 is_deterministic=True) 

212 

213 

214def validate_objective_on_2dbinpacking( 

215 objective: Objective | Callable[[Instance], Objective], 

216 random: Generator = __RANDOM) -> None: 

217 """ 

218 Validate an objective function on bin packing instances. 

219 

220 :param objective: the objective function or a factory creating it 

221 :param random: the random number generator 

222 """ 

223 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

224 for i in binpacking_instances_for_tests(random): 

225 if monotonic_ns() >= end_time: 

226 break 

227 validate_objective_on_1_2dbinpacking(objective, i, random) 

228 

229 

230def validate_signed_permutation_encoding_on_1_2dbinpacking( 

231 encoding: Encoding | Callable[[Instance], Encoding], 

232 instance: str | None = None, 

233 random: Generator = __RANDOM) -> None: 

234 """ 

235 Validate a signed permutation encoding on one 2D bin packing instance. 

236 

237 :param encoding: the encoding or a factory creating it 

238 :param instance: the instance name 

239 :param random: the random number generator 

240 """ 

241 if instance is None: 

242 instance = str(random.choice(Instance.list_resources())) 

243 if not isinstance(instance, str): 

244 raise type_error(instance, "bin packing instance name", (str, None)) 

245 inst = Instance.from_resource(instance) 

246 if not isinstance(inst, Instance): 

247 raise type_error(inst, f"loaded bin packing instance {instance!r}", 

248 Instance) 

249 

250 if callable(encoding): 

251 encoding = encoding(inst) 

252 inst = Instance.from_resource(instance) 

253 

254 x_space = SignedPermutations(inst.get_standard_item_sequence()) 

255 validate_space(x_space) 

256 

257 y_space = PackingSpace(inst) 

258 validate_space(y_space, make_element_valid=None) 

259 

260 validate_encoding(encoding, x_space, y_space) 

261 

262 x = x_space.create() 

263 x_space.validate(x) 

264 

265 y = y_space.create() 

266 encoding.decode(x, y) 

267 y_space.validate(y) 

268 

269 random.shuffle(x) 

270 ri = random.integers 

271 for i, xx in enumerate(x): 

272 if ri(2) == 0: 

273 x[i] = -xx 

274 encoding.decode(x, y) 

275 y_space.validate(y) 

276 

277 x_str = x_space.to_str(x) 

278 x_2 = x_space.from_str(x_str) 

279 if not x_space.is_equal(x, x_2): 

280 raise ValueError("error in space to/from_str") 

281 if not np.array_equal(x, x_2): 

282 raise ValueError("error in space to/from_str and is_equal") 

283 

284 y_2 = y_space.create() 

285 encoding.decode(x_2, y_2) 

286 if not y_space.is_equal(y, y_2): 

287 raise ValueError("encoding is not deterministic") 

288 if not np.array_equal(y, y_2): 

289 raise ValueError( 

290 "encoding is not deterministic and error in space.is_equal") 

291 

292 

293def validate_signed_permutation_encoding_on_2dbinpacking( 

294 encoding: Encoding | Callable[[Instance], Encoding], 

295 random: Generator = __RANDOM) -> None: 

296 """ 

297 Validate a signed permutation encoding function on bin packing instances. 

298 

299 :param encoding: the encoding or a factory creating it 

300 :param random: the random number generator 

301 """ 

302 end_time: Final[int] = monotonic_ns() + 20_000_000_000 

303 for i in binpacking_instances_for_tests(random): 

304 if monotonic_ns() >= end_time: 

305 break 

306 validate_signed_permutation_encoding_on_1_2dbinpacking( 

307 encoding, i, random)