Coverage for moptipyapps / binpacking2d / instance.py: 94%

1""" 

2A Two-Dimensional Bin Packing instance. 

3 

4This module provides an instance of the two-dimensional bin packing problem 

5as defined in 2DPackLib [1, 2] as well as the four non-trivial 'Almost Squares 

6in Almost Squares' instances [6, 7]. 

7 

8All instances of :class:`~moptipyapps.binpacking2d.instance.Instance` 

9are two-dimensional numpy `ndarrays` with additional attributes. 

10Each instance has a :attr:`~Instance.name`. Instances also specify a 

11:attr:`~Instance.bin_width` and :attr:`~Instance.bin_height`. 

12They define the number :attr:`~Instance.n_different_items` of items with 

13*different* IDs. Notice that in the 2DPackLib dataset, a benchmark instance 

14may contain the same item multiple times. Obviously, all items of the same 

15ID have the exact same width and height, meaning that we only need to store 

16them once and remember how often they occur. (Notice that the opposite is not 

17true, i.e., not all items with the same width and height do have the same ID.) 

18Anyway, the total number :attr:`~Instance.n_items` of items, i.e., the sum of 

19all the repetitions of all items, is also stored. 

20 

21The matrix data of the instance class is laid out as follows: There is one row 

22for each item. The row contains the width of the item, the height of the item, 

23and the number of times the item will occur. The row at index `i` stands for 

24the item with ID `i+1`. 

25 

26Instances can be loaded directly from a 2DPackLib file via 

27:meth:`Instance.from_2dpacklib`. They can also be loaded from a compact string 

28representation (via :meth:`Instance.from_compact_str`) and can also be 

29converted to such a compact representation 

30(via :meth:`Instance.to_compact_str`). This library ships with a set of 

31pre-defined instances as resource which can be obtained via 

32:meth:`Instance.from_resource` and listed via 

33:meth:`Instance.list_resources`. 

34 

35We provide the instances of the sets `A` [3], `BENG` [4], and `CLASS` [5] 

36from 2DPackLib. Additionally, we include the four non-trivial 'Almost Squares 

37in Almost Squares' instances [6,7]. 

38 

39Initial work on this code has been contributed by Mr. Rui ZHAO (赵睿), 

40<zr1329142665@163.com> a Master's student at the Institute of Applied 

41Optimization (应用优化研究所) of the School of 

42Artificial Intelligence and Big Data (人工智能与大数据学院) at Hefei University 

43(合肥大学) in Hefei, Anhui, China (中国安徽省合肥市) under the supervision of 

44Prof. Dr. Thomas Weise (汤卫思教授). 

45 

461. Manuel Iori, Vinícius Loti de Lima, Silvano Martello, and Michele Monaci. 

47 *2DPackLib*. 

48 https://site.unibo.it/operations-research/en/research/2dpacklib 

492. Manuel Iori, Vinícius Loti de Lima, Silvano Martello, and Michele 

50 Monaci. 2DPackLib: A Two-Dimensional Cutting and Packing Library. 

51 *Optimization Letters* 16(2):471-480. March 2022. 

52 https://doi.org/10.1007/s11590-021-01808-y 

533. Rita Macedo, Cláudio Alves, and José M. Valério de Carvalho. Arc-Flow 

54 Model for the Two-Dimensional Guillotine Cutting Stock Problem. 

55 *Computers & Operations Research* 37(6):991-1001. June 2010. 

56 https://doi.org/10.1016/j.cor.2009.08.005. 

574. Bengt-Erik Bengtsson. Packing Rectangular Pieces - A Heuristic Approach. 

58 *The Computer Journal* 25(3):353-357, August 1982. 

59 https://doi.org/10.1093/comjnl/25.3.353 

605. J.O. Berkey and P.Y. Wang. Two Dimensional Finite Bin Packing Algorithms. 

61 *Journal of the Operational Research Society* 38(5):423-429. May 1987. 

62 https://doi.org/10.1057/jors.1987.70 

636. Daan van den Berg, Florian Braam, Mark Moes, Emiel Suilen, and 

64 Sandjai Bhulai. Almost Squares in Almost Squares: Solving the Final 

65 Instance. In *The Fifth International Conference on Data Analytics 

66 (DATA ANALYTICS'16)* October 9-13, 2016, Venice, Italy, pages 69-74. 

67 IARIA. ISBN: 9781612085104. https://hdl.handle.net/11245/1.545914. 

68 https://math.vu.nl/~sbhulai/publications/data_analytics2016b.pdf. 

697. H. Simonis and B. O'Sullivan. Almost Square Packing in *8th International 

70 Conference on Integration of AI and OR Techniques in Constraint Programming 

71 for Combinatorial Optimization Problems* (CPAIOR'11), May 23-27, 2011, 

72 Berlin, Germany, pages 196-209. Berlin, Germany: Springer-Verlag. 

73 doi:10.1007/978-3-642-21311-3_19. 

74 

75>>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]]) 

76>>> ins.name 

77'a' 

78>>> ins.bin_width 

79100 

80>>> ins.bin_height 

8150 

82>>> ins.dtype 

83dtype('int8') 

84>>> ins.n_different_items 

853 

86>>> ins.to_compact_str() 

87'a;3;100;50;10,5;3,3;5,5' 

88>>> ins = Instance("b", 100, 50, np.array([[10, 5, 1], [3, 3, 1], [3, 3, 1]])) 

89>>> ins.name 

90'b' 

91>>> ins.bin_width 

92100 

93>>> ins.bin_height 

9450 

95>>> ins.dtype 

96dtype('int8') 

97>>> ins.to_compact_str() 

98'b;3;100;50;10,5;3,3;3,3' 

99>>> ins = Instance.from_resource("cl02_020_06") 

100>>> ins.dtype 

101dtype('int8') 

102>>> ins.n_different_items 

10320 

104>>> ins.n_items 

10520 

106>>> ins = Instance.from_resource("a25") 

107>>> ins.dtype 

108dtype('int16') 

109>>> ins.n_different_items 

11075 

111>>> ins.n_items 

112156 

113""" 

114 

115from importlib import resources # nosem 

116from os.path import basename 

117from statistics import quantiles 

118from typing import Final, Iterable, cast 

119 

120import moptipy.utils.nputils as npu 

121import numpy as np 

122from moptipy.api.component import Component 

123from moptipy.utils.logger import CSV_SEPARATOR, KeyValueLogSection 

124from moptipy.utils.nputils import int_range_to_dtype 

125from moptipy.utils.strings import sanitize_name 

126from pycommons.io.path import UTF8, Path, file_path 

127from pycommons.types import check_int_range, check_to_int_range, type_error 

128 

129#: the instances resource name 

130INSTANCES_RESOURCE: Final[str] = "instances.txt" 

131 

132#: the total number of items 

133N_ITEMS: Final[str] = "nItems" 

134#: the number of different items. 

135N_DIFFERENT_ITEMS: Final[str] = "nDifferentItems" 

136#: the bin width 

137BIN_WIDTH: Final[str] = "binWidth" 

138#: the bin height 

139BIN_HEIGHT: Final[str] = "binHeight" 

140#: The internal item separator 

141INTERNAL_SEP: Final[str] = "," if CSV_SEPARATOR == ";" else ";" 

142 

143#: the index of the width element in an item of an instance 

144IDX_WIDTH: Final[int] = 0 

145#: the index of the height element in an item of an instance 

146IDX_HEIGHT: Final[int] = 1 

147#: the index of the repetitions element in an item of an instance 

148IDX_REPETITION: Final[int] = 2 

149 

150#: the list of instance names of the 2DPackLib bin packing set downloaded 

151#: from https://site.unibo.it/operations-research/en/research/2dpacklib 

152#: ('a*','beng*', 'cl*') as well as the four non-trivial 'Almost Squares in 

153#: Almost Squares' instances ('asqas*'). 

154_INSTANCES: Final[tuple[str, ...]] = ( 

155 "a01", "a02", "a03", "a04", "a05", "a06", "a07", "a08", "a09", "a10", 

156 "a11", "a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", 

157 "a21", "a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30", 

158 "a31", "a32", "a33", "a34", "a35", "a36", "a37", "a38", "a39", "a40", 

159 "a41", "a42", "a43", "asqas03", "asqas08", "asqas20", "asqas34", "beng01", 

160 "beng02", "beng03", "beng04", "beng05", "beng06", "beng07", "beng08", 

161 "beng09", "beng10", "cl01_020_01", "cl01_020_02", "cl01_020_03", 

162 "cl01_020_04", "cl01_020_05", "cl01_020_06", "cl01_020_07", "cl01_020_08", 

163 "cl01_020_09", "cl01_020_10", "cl01_040_01", "cl01_040_02", "cl01_040_03", 

164 "cl01_040_04", "cl01_040_05", "cl01_040_06", "cl01_040_07", "cl01_040_08", 

165 "cl01_040_09", "cl01_040_10", "cl01_060_01", "cl01_060_02", "cl01_060_03", 

166 "cl01_060_04", "cl01_060_05", "cl01_060_06", "cl01_060_07", "cl01_060_08", 

167 "cl01_060_09", "cl01_060_10", "cl01_080_01", "cl01_080_02", "cl01_080_03", 

168 "cl01_080_04", "cl01_080_05", "cl01_080_06", "cl01_080_07", "cl01_080_08", 

169 "cl01_080_09", "cl01_080_10", "cl01_100_01", "cl01_100_02", "cl01_100_03", 

170 "cl01_100_04", "cl01_100_05", "cl01_100_06", "cl01_100_07", "cl01_100_08", 

171 "cl01_100_09", "cl01_100_10", "cl02_020_01", "cl02_020_02", "cl02_020_03", 

172 "cl02_020_04", "cl02_020_05", "cl02_020_06", "cl02_020_07", "cl02_020_08", 

173 "cl02_020_09", "cl02_020_10", "cl02_040_01", "cl02_040_02", "cl02_040_03", 

174 "cl02_040_04", "cl02_040_05", "cl02_040_06", "cl02_040_07", "cl02_040_08", 

175 "cl02_040_09", "cl02_040_10", "cl02_060_01", "cl02_060_02", "cl02_060_03", 

176 "cl02_060_04", "cl02_060_05", "cl02_060_06", "cl02_060_07", "cl02_060_08", 

177 "cl02_060_09", "cl02_060_10", "cl02_080_01", "cl02_080_02", "cl02_080_03", 

178 "cl02_080_04", "cl02_080_05", "cl02_080_06", "cl02_080_07", "cl02_080_08", 

179 "cl02_080_09", "cl02_080_10", "cl02_100_01", "cl02_100_02", "cl02_100_03", 

180 "cl02_100_04", "cl02_100_05", "cl02_100_06", "cl02_100_07", "cl02_100_08", 

181 "cl02_100_09", "cl02_100_10", "cl03_020_01", "cl03_020_02", "cl03_020_03", 

182 "cl03_020_04", "cl03_020_05", "cl03_020_06", "cl03_020_07", "cl03_020_08", 

183 "cl03_020_09", "cl03_020_10", "cl03_040_01", "cl03_040_02", "cl03_040_03", 

184 "cl03_040_04", "cl03_040_05", "cl03_040_06", "cl03_040_07", "cl03_040_08", 

185 "cl03_040_09", "cl03_040_10", "cl03_060_01", "cl03_060_02", "cl03_060_03", 

186 "cl03_060_04", "cl03_060_05", "cl03_060_06", "cl03_060_07", "cl03_060_08", 

187 "cl03_060_09", "cl03_060_10", "cl03_080_01", "cl03_080_02", "cl03_080_03", 

188 "cl03_080_04", "cl03_080_05", "cl03_080_06", "cl03_080_07", "cl03_080_08", 

189 "cl03_080_09", "cl03_080_10", "cl03_100_01", "cl03_100_02", "cl03_100_03", 

190 "cl03_100_04", "cl03_100_05", "cl03_100_06", "cl03_100_07", "cl03_100_08", 

191 "cl03_100_09", "cl03_100_10", "cl04_020_01", "cl04_020_02", "cl04_020_03", 

192 "cl04_020_04", "cl04_020_05", "cl04_020_06", "cl04_020_07", "cl04_020_08", 

193 "cl04_020_09", "cl04_020_10", "cl04_040_01", "cl04_040_02", "cl04_040_03", 

194 "cl04_040_04", "cl04_040_05", "cl04_040_06", "cl04_040_07", "cl04_040_08", 

195 "cl04_040_09", "cl04_040_10", "cl04_060_01", "cl04_060_02", "cl04_060_03", 

196 "cl04_060_04", "cl04_060_05", "cl04_060_06", "cl04_060_07", "cl04_060_08", 

197 "cl04_060_09", "cl04_060_10", "cl04_080_01", "cl04_080_02", "cl04_080_03", 

198 "cl04_080_04", "cl04_080_05", "cl04_080_06", "cl04_080_07", "cl04_080_08", 

199 "cl04_080_09", "cl04_080_10", "cl04_100_01", "cl04_100_02", "cl04_100_03", 

200 "cl04_100_04", "cl04_100_05", "cl04_100_06", "cl04_100_07", "cl04_100_08", 

201 "cl04_100_09", "cl04_100_10", "cl05_020_01", "cl05_020_02", "cl05_020_03", 

202 "cl05_020_04", "cl05_020_05", "cl05_020_06", "cl05_020_07", "cl05_020_08", 

203 "cl05_020_09", "cl05_020_10", "cl05_040_01", "cl05_040_02", "cl05_040_03", 

204 "cl05_040_04", "cl05_040_05", "cl05_040_06", "cl05_040_07", "cl05_040_08", 

205 "cl05_040_09", "cl05_040_10", "cl05_060_01", "cl05_060_02", "cl05_060_03", 

206 "cl05_060_04", "cl05_060_05", "cl05_060_06", "cl05_060_07", "cl05_060_08", 

207 "cl05_060_09", "cl05_060_10", "cl05_080_01", "cl05_080_02", "cl05_080_03", 

208 "cl05_080_04", "cl05_080_05", "cl05_080_06", "cl05_080_07", "cl05_080_08", 

209 "cl05_080_09", "cl05_080_10", "cl05_100_01", "cl05_100_02", "cl05_100_03", 

210 "cl05_100_04", "cl05_100_05", "cl05_100_06", "cl05_100_07", "cl05_100_08", 

211 "cl05_100_09", "cl05_100_10", "cl06_020_01", "cl06_020_02", "cl06_020_03", 

212 "cl06_020_04", "cl06_020_05", "cl06_020_06", "cl06_020_07", "cl06_020_08", 

213 "cl06_020_09", "cl06_020_10", "cl06_040_01", "cl06_040_02", "cl06_040_03", 

214 "cl06_040_04", "cl06_040_05", "cl06_040_06", "cl06_040_07", "cl06_040_08", 

215 "cl06_040_09", "cl06_040_10", "cl06_060_01", "cl06_060_02", "cl06_060_03", 

216 "cl06_060_04", "cl06_060_05", "cl06_060_06", "cl06_060_07", "cl06_060_08", 

217 "cl06_060_09", "cl06_060_10", "cl06_080_01", "cl06_080_02", "cl06_080_03", 

218 "cl06_080_04", "cl06_080_05", "cl06_080_06", "cl06_080_07", "cl06_080_08", 

219 "cl06_080_09", "cl06_080_10", "cl06_100_01", "cl06_100_02", "cl06_100_03", 

220 "cl06_100_04", "cl06_100_05", "cl06_100_06", "cl06_100_07", "cl06_100_08", 

221 "cl06_100_09", "cl06_100_10", "cl07_020_01", "cl07_020_02", "cl07_020_03", 

222 "cl07_020_04", "cl07_020_05", "cl07_020_06", "cl07_020_07", "cl07_020_08", 

223 "cl07_020_09", "cl07_020_10", "cl07_040_01", "cl07_040_02", "cl07_040_03", 

224 "cl07_040_04", "cl07_040_05", "cl07_040_06", "cl07_040_07", "cl07_040_08", 

225 "cl07_040_09", "cl07_040_10", "cl07_060_01", "cl07_060_02", "cl07_060_03", 

226 "cl07_060_04", "cl07_060_05", "cl07_060_06", "cl07_060_07", "cl07_060_08", 

227 "cl07_060_09", "cl07_060_10", "cl07_080_01", "cl07_080_02", "cl07_080_03", 

228 "cl07_080_04", "cl07_080_05", "cl07_080_06", "cl07_080_07", "cl07_080_08", 

229 "cl07_080_09", "cl07_080_10", "cl07_100_01", "cl07_100_02", "cl07_100_03", 

230 "cl07_100_04", "cl07_100_05", "cl07_100_06", "cl07_100_07", "cl07_100_08", 

231 "cl07_100_09", "cl07_100_10", "cl08_020_01", "cl08_020_02", "cl08_020_03", 

232 "cl08_020_04", "cl08_020_05", "cl08_020_06", "cl08_020_07", "cl08_020_08", 

233 "cl08_020_09", "cl08_020_10", "cl08_040_01", "cl08_040_02", "cl08_040_03", 

234 "cl08_040_04", "cl08_040_05", "cl08_040_06", "cl08_040_07", "cl08_040_08", 

235 "cl08_040_09", "cl08_040_10", "cl08_060_01", "cl08_060_02", "cl08_060_03", 

236 "cl08_060_04", "cl08_060_05", "cl08_060_06", "cl08_060_07", "cl08_060_08", 

237 "cl08_060_09", "cl08_060_10", "cl08_080_01", "cl08_080_02", "cl08_080_03", 

238 "cl08_080_04", "cl08_080_05", "cl08_080_06", "cl08_080_07", "cl08_080_08", 

239 "cl08_080_09", "cl08_080_10", "cl08_100_01", "cl08_100_02", "cl08_100_03", 

240 "cl08_100_04", "cl08_100_05", "cl08_100_06", "cl08_100_07", "cl08_100_08", 

241 "cl08_100_09", "cl08_100_10", "cl09_020_01", "cl09_020_02", "cl09_020_03", 

242 "cl09_020_04", "cl09_020_05", "cl09_020_06", "cl09_020_07", "cl09_020_08", 

243 "cl09_020_09", "cl09_020_10", "cl09_040_01", "cl09_040_02", "cl09_040_03", 

244 "cl09_040_04", "cl09_040_05", "cl09_040_06", "cl09_040_07", "cl09_040_08", 

245 "cl09_040_09", "cl09_040_10", "cl09_060_01", "cl09_060_02", "cl09_060_03", 

246 "cl09_060_04", "cl09_060_05", "cl09_060_06", "cl09_060_07", "cl09_060_08", 

247 "cl09_060_09", "cl09_060_10", "cl09_080_01", "cl09_080_02", "cl09_080_03", 

248 "cl09_080_04", "cl09_080_05", "cl09_080_06", "cl09_080_07", "cl09_080_08", 

249 "cl09_080_09", "cl09_080_10", "cl09_100_01", "cl09_100_02", "cl09_100_03", 

250 "cl09_100_04", "cl09_100_05", "cl09_100_06", "cl09_100_07", "cl09_100_08", 

251 "cl09_100_09", "cl09_100_10", "cl10_020_01", "cl10_020_02", "cl10_020_03", 

252 "cl10_020_04", "cl10_020_05", "cl10_020_06", "cl10_020_07", "cl10_020_08", 

253 "cl10_020_09", "cl10_020_10", "cl10_040_01", "cl10_040_02", "cl10_040_03", 

254 "cl10_040_04", "cl10_040_05", "cl10_040_06", "cl10_040_07", "cl10_040_08", 

255 "cl10_040_09", "cl10_040_10", "cl10_060_01", "cl10_060_02", "cl10_060_03", 

256 "cl10_060_04", "cl10_060_05", "cl10_060_06", "cl10_060_07", "cl10_060_08", 

257 "cl10_060_09", "cl10_060_10", "cl10_080_01", "cl10_080_02", "cl10_080_03", 

258 "cl10_080_04", "cl10_080_05", "cl10_080_06", "cl10_080_07", "cl10_080_08", 

259 "cl10_080_09", "cl10_080_10", "cl10_100_01", "cl10_100_02", "cl10_100_03", 

260 "cl10_100_04", "cl10_100_05", "cl10_100_06", "cl10_100_07", "cl10_100_08", 

261 "cl10_100_09", "cl10_100_10") 

262 

263 

264def __divide_based_on_size(instances: Iterable[str], 

265 divisions: int) -> list[list[str]]: 

266 """ 

267 Divide the instances based on their size. 

268 

269 :param instances: the instances 

270 :param divisions: the number of divisions 

271 :return: the divided instances 

272 """ 

273 insts: list[str] = list(instances) 

274 if len(insts) <= 0: 

275 return [insts] 

276 

277 try: 

278 loaded: list[Instance] = [Instance.from_resource(n) for n in insts] 

279 except (OSError, ValueError): 

280 return [insts] 

281 

282 # get the quantiles = group divisions 

283 qants: list[float | int] = quantiles(( 

284 inst.n_items for inst in loaded), n=divisions, method="inclusive") 

285 

286 # now put the instances into the groups 

287 groups: list[list[str]] = [] 

288 for inst in loaded: 

289 inst_size = inst.n_items 

290 idx: int = 0 

291 for q in qants: 

292 if q > inst_size: 

293 break 

294 idx += 1 

295 while idx >= len(groups): 

296 groups.append([]) 

297 groups[idx].append(str(inst)) 

298 

299 # remove useless groups 

300 for idx in range(len(groups) - 1, -1, -1): 

301 if len(groups[idx]) <= 0: 

302 del groups[idx] 

303 return groups 

304 

305 

306def _make_instance_groups(instances: Iterable[str]) \ 

307 -> "tuple[tuple[str, str | None, tuple[str, ...]], ...]": 

308 """ 

309 Make the standard instance groups from an instance name list. 

310 

311 :return: the instance groups 

312 """ 

313 groups: list[tuple[str, str | None, tuple[str, ...]]] = [] 

314 

315 a_divided: list[list[str]] = __divide_based_on_size(sorted( 

316 b for b in instances if b.startswith("a") 

317 and (len(b) == 3) and b[-1].isdigit() 

318 and b[-2].isdigit()), 3) 

319 if len(a_divided) > 0: 

320 subnames: list[str | None] = [None] if (len(a_divided) <= 1) else ( 

321 ["small", "large"] if (len(a_divided) <= 2) else 

322 ["small", "med", "large"]) 

323 for a_idx, a_group in enumerate(a_divided): 

324 v: tuple[str, str | None, tuple[str, ...]] = ( 

325 "a", subnames[a_idx], tuple(a_group)) 

326 if len(v[2]) > 0: 

327 groups.append(v) 

328 

329 v = ("beng", "1-8", tuple(sorted( 

330 b for b in instances if b.startswith("beng") 

331 and (int(b[-2:]) < 9)))) 

332 if len(v[2]) > 0: 

333 groups.append(v) 

334 

335 v = ("beng", "9-10", tuple(sorted( 

336 b for b in instances if b.startswith("beng") 

337 and (int(b[-2:]) >= 9)))) 

338 if len(v[2]) > 0: 

339 groups.append(v) 

340 

341 for i in range(1, 11): 

342 name: str = f"class {i}" 

343 preprefix: str = f"cl0{i}" if i < 10 else f"cl{i}" 

344 for n in (20, 40, 60, 80, 100): 

345 prefix: str = f"{preprefix}_0{n}_" \ 

346 if n < 100 else f"{preprefix}_{n}_" 

347 v = (name, str(n), tuple(sorted( 

348 b for b in _INSTANCES if b.startswith(prefix)))) 

349 if len(v[2]) > 0: 

350 groups.append(v) 

351 

352 v = ("asqas", None, tuple(sorted( 

353 b for b in _INSTANCES if b.startswith("asqas")))) 

354 if len(v[2]) > 0: 

355 groups.append(v) 

356 

357 all_set: set[str] = set() 

358 for g in groups: 

359 all_set.update(g[2]) 

360 inst_set: set[str] = set(instances) 

361 if all_set != inst_set: 

362 raise ValueError(f"group instances is {all_set!r} but " 

363 f"instance set is {inst_set!r}!") 

364 return tuple(groups) 

365 

366 

367def __cutsq(matrix: np.ndarray) -> list[int]: 

368 """ 

369 Cut all items into squares via the CUTSQ procedure. 

370 

371 :param matrix: the item matrix 

372 :return: the list of squares 

373 

374 >>> __cutsq(np.array([[14, 12, 1]], int)) 

375 [12, 2, 2, 2, 2, 2, 2] 

376 

377 >>> __cutsq(np.array([[14, 12, 2]], int)) 

378 [12, 12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] 

379 """ 

380 # create list of items in horizontal orientation 

381 j_sq: Final[list[int]] = [] # the list of squares (width = height) 

382 s: Final[list[int]] = [] # a temporary list 

383 for row in matrix: 

384 w: int = int(row[0]) 

385 h: int = int(row[1]) 

386 if h > w: 

387 w, h = h, w 

388 while h > 1: 

389 k: int = w // h 

390 for _ in range(k): 

391 s.append(h) 

392 w, h = h, w - (k * h) 

393 times: int = int(row[2]) 

394 j_sq.extend(s * times if times > 1 else s) 

395 s.clear() 

396 

397 j_sq.sort(reverse=True) # sort the squares in decreasing size 

398 return j_sq 

399 

400 

401def __lb_q(bin_width: int, bin_height: int, q: int, j_js: list[int]) -> int: 

402 """ 

403 Compute the lower bound for a given q. 

404 

405 :param bin_width: the bin width 

406 :param bin_height: the bin height 

407 :param q: the parameter q 

408 :param j_js: the sorted square list 

409 :return: the lower bound 

410 

411 >>> jj = [18, 18, 12, 12, 11, 11, 11, 11, 11, 7, 7, 7, 7, 7, 7] 

412 >>> len(jj) 

413 15 

414 >>> __lb_q(23, 20, 6, jj) 

415 6 

416 """ 

417 m: Final[int] = len(j_js) 

418 half_width: Final[float] = bin_width / 2 

419 half_height: Final[float] = bin_height / 2 

420 width_m_q: Final[int] = bin_width - q 

421 

422 # First we compute sets S1 to S4. 

423 s1: list[int] = [] # S1 from Equation 2 

424 s2: list[int] = [] # S2 from Equation 3 

425 s3: list[int] = [] # S2 from Equation 4 

426 s4: list[int] = [] # S2 from Equation 5 

427 

428 for i in range(m): 

429 l_i: int = j_js[i] 

430 if l_i > width_m_q: 

431 s1.append(i) # Equation 2 

432 elif l_i > half_width: 

433 s2.append(i) # Equation 3 

434 elif l_i > half_height: 

435 s3.append(i) # Equation 4 

436 elif l_i >= q: 

437 s4.append(i) # Equation 5 

438 else: 

439 break 

440 

441 # compute set S23 as in Theorem 3 under Equation 7 

442 height_m_q: Final[int] = bin_height - q 

443 s23: Final[list[int]] = [j for j in (s2 + s3) if j_js[j] > height_m_q] 

444 

445 # Now we sort S2 by non-increasing value of residual space. 

446 s2.reverse() # = .sort(key=lambda i: bin_width - j_js[i], reverse=True) 

447 

448 # Now we compute S3 - ^S3^ 

449 s3_minus_s3d: list[int] = s3.copy() 

450 for i in s2: 

451 residual: int = bin_width - j_js[i] 

452 not_found: bool = True 

453 for j, idx in enumerate(s3_minus_s3d): 

454 needs: int = j_js[idx] 

455 if needs <= residual: 

456 del s3_minus_s3d[j] 

457 not_found = False 

458 break 

459 if not_found: 

460 break 

461 

462 sum_s3_l: int = sum(j_js[i] for i in s3_minus_s3d) 

463 b1 = sum_s3_l // bin_width 

464 if (b1 * bin_width) < sum_s3_l: 

465 b1 += 1 

466 

467 len_s3: int = len(s3_minus_s3d) 

468 div: int = bin_width // ((bin_height // 2) + 1) 

469 b2 = len_s3 // div 

470 if (b2 * div) < len_s3: 

471 b2 += 1 

472 

473 l_tilde: Final[int] = len(s2) + max(b1, b2) # Equation 6. 

474 bound: int = len(s1) + l_tilde 

475 

476 # Now compute the final bound based on Theorem 3 / Equation 7. 

477 bin_size: Final[int] = bin_width * bin_height 

478 denom: int = sum(j_js[i] ** 2 for i in (s2 + s3 + s4)) \ 

479 - ((bin_size * l_tilde) - sum(j_js[i] * ( 

480 bin_height - j_js[i]) for i in s23)) 

481 if denom > 0: 

482 b = denom // bin_size 

483 if (b * bin_size) < denom: 

484 b += 1 

485 bound += b 

486 

487 return bound 

488 

489 

490def _lower_bound_damv(bin_width: int, bin_height: int, 

491 matrix: np.ndarray) -> int: 

492 """ 

493 Compute the lower bound as defined by Dell'Amico et al. 

494 

495 :param bin_width: the bin width 

496 :param bin_height: the bin height 

497 :param matrix: the item matrix 

498 :return: the lower bound 

499 

500 >>> mat = np.array([[10, 5, 1], [3, 3, 1], [3, 3, 1]]) 

501 >>> _lower_bound_damv(23, 20, mat) 

502 1 

503 

504 >>> mat = np.array([[20, 5, 3], [13, 23, 1], [13, 9, 3]]) 

505 >>> _lower_bound_damv(23, 20, mat) 

506 3 

507 """ 

508 # ensure horizontal orientation (width >= height) 

509 if bin_height > bin_width: 

510 bin_width, bin_height = bin_height, bin_width 

511 j_sq: Final[list[int]] = __cutsq(matrix) 

512 res: Final[int] = max(__lb_q(bin_width, bin_height, q, j_sq) 

513 for q in range((bin_height // 2) + 1)) 

514 return max(1, res) 

515 

516 

517class Instance(Component, np.ndarray): 

518 """ 

519 An instance of the 2D Bin Packing Problem. 

520 

521 Each row of the matrix contains three values: 1. the item's width, 2. the 

522 item's height, 3. how often the item occurs. 

523 """ 

524 

525 #: the name of the instance 

526 name: str 

527 #: the total number of items (including repetitions) 

528 n_items: int 

529 #: the number of different items 

530 n_different_items: int 

531 #: the total area occupied by all items 

532 total_item_area: int 

533 #: the bin width 

534 bin_width: int 

535 #: the bin height 

536 bin_height: int 

537 #: the minimum number of bins that this instance requires 

538 lower_bound_bins: int 

539 

540 def __new__(cls, name: str, 

541 bin_width: int, bin_height: int, 

542 matrix: np.ndarray | list[list[int]]) -> "Instance": 

543 """ 

544 Create an instance of the 2D bin packing problem. 

545 

546 :param cls: the class 

547 :param name: the name of the instance 

548 :param bin_width: the bin width 

549 :param bin_height: the bin height 

550 :param matrix: the matrix with the data (will be copied); rows have 

551 the form `(width, height, repetitions)` 

552 """ 

553 use_name: Final[str] = sanitize_name(name) 

554 if name != use_name: 

555 raise ValueError(f"Name {name!r} is not a valid name.") 

556 

557 check_int_range(bin_width, "bin_width", 1, 1_000_000_000_000) 

558 check_int_range(bin_height, "bin_height", 1, 1_000_000_000_000) 

559 max_dim: Final[int] = max(bin_width, bin_height) 

560 min_dim: Final[int] = min(bin_width, bin_height) 

561 

562 n_different_items: Final[int] = check_int_range( 

563 len(matrix), "n_different_items", 1, 100_000_000) 

564 use_shape: Final[tuple[int, int]] = (n_different_items, 3) 

565 

566 if isinstance(matrix, np.ndarray): 

567 if not npu.is_np_int(matrix.dtype): 

568 raise ValueError( 

569 "Matrix must have an integer type, but is of type " 

570 f"{str(matrix.dtype)!r} in instance {name!r}.") 

571 if matrix.shape != use_shape: 

572 raise ValueError( 

573 f"Invalid shape {str(matrix.shape)!r} of matrix: " 

574 "must have three columns and two dimensions, must be " 

575 f"equal to {use_shape} in instance {name!r}.") 

576 elif not isinstance(matrix, list): 

577 raise type_error(matrix, "matrix", np.ndarray) 

578 

579 n_items: int = 0 

580 max_size: int = -1 

581 item_area: int = 0 

582 for i in range(n_different_items): 

583 row = matrix[i] 

584 if not isinstance(row, list | np.ndarray): 

585 raise type_error( 

586 row, f"{row} at index {i} in {use_name!r}", 

587 (list, np.ndarray)) 

588 if len(row) != 3: 

589 raise ValueError( 

590 f"invalid row {row} at index {i} in {use_name!r}.") 

591 width, height, repetitions = row 

592 width = check_int_range(int(width), "width", 1, max_dim) 

593 height = check_int_range(int(height), "height", 1, max_dim) 

594 repetitions = check_int_range(int(repetitions), "repetitions", 

595 1, 100_000_000) 

596 item_area += (width * height * repetitions) 

597 max_size = max(max_size, width, height) 

598 if (width > min_dim) and (height > min_dim): 

599 raise ValueError( 

600 f"object with width={width} and height={height} does " 

601 f"not fit into bin with width={width} and " 

602 f"height={height}.") 

603 n_items += repetitions 

604 

605 obj: Final[Instance] = super().__new__( 

606 cls, use_shape, int_range_to_dtype( 

607 min_value=0, max_value=max( 

608 max_dim + max_size + 1, n_items + 1), force_signed=True)) 

609 for i in range(n_different_items): 

610 obj[i, :] = matrix[i] 

611 

612 #: the name of the instance 

613 obj.name = use_name 

614 #: the number of different items 

615 obj.n_different_items = n_different_items 

616 #: the total number of items, i.e., the number of different items 

617 #: multiplied with their repetition counts 

618 obj.n_items = check_int_range( 

619 n_items, "n_items", n_different_items, 1_000_000_000_000) 

620 #: the height of the bins 

621 obj.bin_height = bin_height 

622 #: the width of the bins 

623 obj.bin_width = bin_width 

624 #: the total area occupied by all items 

625 obj.total_item_area = item_area 

626 

627# We need at least as many bins such that their area is big enough 

628# for the total area of the items. 

629 bin_area: int = bin_height * bin_width 

630 lower_bound_geo: int = item_area // bin_area 

631 if (lower_bound_geo * bin_area) < item_area: 

632 lower_bound_geo += 1 

633 lower_bound_geo = check_int_range( 

634 lower_bound_geo, "lower_bound_bins_geometric", 

635 1, 1_000_000_000_000) 

636 

637# We now compute the lower bound by Dell'Amico et al. 

638 lower_bound_damv = check_int_range(_lower_bound_damv( 

639 bin_width, bin_height, obj), "lower_bound_bins_damv", 

640 1, 1_000_000_000_000) 

641 

642# The overall computed lower bound is the maximum of the geometric and the 

643# Dell'Amico lower bound. 

644 obj.lower_bound_bins = max(lower_bound_damv, lower_bound_geo) 

645 return obj 

646 

647 def __str__(self): 

648 """ 

649 Get the name of this instance. 

650 

651 :return: the name of this instance 

652 """ 

653 return self.name 

654 

655 def get_standard_item_sequence(self) -> list[int]: 

656 """ 

657 Get the standardized item sequence. 

658 

659 :return: the standardized item sequence 

660 

661 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]]) 

662 >>> ins.get_standard_item_sequence() 

663 [1, 2, 3] 

664 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 2]]) 

665 >>> ins.get_standard_item_sequence() 

666 [1, 2, 3, 3] 

667 >>> ins = Instance("a", 100, 50, [[10, 5, 2], [3, 3, 3], [5, 5, 4]]) 

668 >>> ins.get_standard_item_sequence() 

669 [1, 1, 2, 2, 2, 3, 3, 3, 3] 

670 """ 

671 base_string: Final[list[int]] = [] 

672 for i in range(1, self.n_different_items + 1): 

673 for _ in range(self[i - 1, IDX_REPETITION]): 

674 base_string.append(int(i)) 

675 return base_string 

676 

677 @staticmethod 

678 def from_2dpacklib(file: str) -> "Instance": 

679 """ 

680 Load a problem instance from the 2dpacklib format. 

681 

682 :param file: the file path 

683 :return: the instance 

684 """ 

685 path: Final[Path] = file_path(file) 

686 name: str = basename(path).lower() 

687 if name.endswith(".ins2d"): 

688 name = sanitize_name(name[:-6]) 

689 

690 lines: Final[list[str]] = str.splitlines(path.read_all_str()) 

691 n_different_items: Final[int] = check_to_int_range( 

692 lines[0], "n_different_items", 1, 100_000_000) 

693 

694 wh: Final[str] = lines[1] 

695 spaceidx: Final[int] = wh.index(" ") 

696 if spaceidx <= 0: 

697 raise ValueError("Did not find space in second line.") 

698 bin_width: Final[int] = check_to_int_range( 

699 wh[:spaceidx], "bin_width", 1, 1_000_000_000_000) 

700 bin_height: Final[int] = check_to_int_range( 

701 wh[spaceidx + 1:], "bin_height", 1, 1_000_000_000_000) 

702 del lines[0:2] 

703 

704 max_dim: Final[int] = max(bin_width, bin_height) 

705 data: Final[list[list[int]]] = [] 

706 old_item_id: int = 0 

707 for line in lines: 

708 text: list[str] = line.split(" ") 

709 itemid: int = check_to_int_range( 

710 text[0], "item-id", 1, n_different_items) 

711 if itemid != (old_item_id + 1): 

712 raise ValueError( 

713 f"non-sequential item id {itemid} after {old_item_id}!") 

714 old_item_id = itemid 

715 width: int = check_to_int_range(text[1], "width", 1, max_dim) 

716 height: int = check_to_int_range(text[2], "height", 1, max_dim) 

717 count: int = 1 if len(text) <= 3 else \ 

718 check_to_int_range(text[3], "count", 1, 1_000_000) 

719 data.append([width, height, count]) 

720 data.sort() 

721 return Instance(name, bin_width, bin_height, data) 

722 

723 def to_compact_str(self) -> str: 

724 """ 

725 Convert the instance to a compact string. 

726 

727 The format of the string is a single line of semi-colon separated 

728 values. The values are: `name;n_items;bin_width;bin_height`, 

729 followed by the sequence of items, each in the form of 

730 `;width,heigh[,times]`, where `times` is optional and only added 

731 if the item occurs more than once. 

732 

733 :return: a single line string with all the instance data 

734 

735 >>> ins = Instance("x", 500, 50, [[3, 5, 1], [2, 5, 2]]) 

736 >>> ins.to_compact_str() 

737 'x;2;500;50;3,5;2,5,2' 

738 >>> ins.n_different_items 

739 2 

740 """ 

741 lst: Final[list[str]] = [self.name, str(self.n_different_items), 

742 str(self.bin_width), str(self.bin_height)] 

743 for i in range(self.n_different_items): 

744 width: int = self[i, IDX_WIDTH] 

745 height: int = self[i, IDX_HEIGHT] 

746 repetitions: int = self[i, IDX_REPETITION] 

747 lst.append( 

748 f"{width}{INTERNAL_SEP}{height}" if repetitions == 1 else 

749 f"{width}{INTERNAL_SEP}{height}{INTERNAL_SEP}{repetitions}")