Coverage for moptipyapps / binpacking2d / objectives / bin_count_and_small.py: 67%

1""" 

2An objective function indirectly minimizing the number of bins in packings. 

3 

4This objective function computes the number of bins used. Let's call it 

5`n_bins`. We know the area `bin_area` of a bin as well. We then compute the 

6minimum area occupied in any bin, `min_area`. Now we return 

7`(bin_area * (n_bins - 1)) + min_area`. 

8 

9This function always prefers a packing that has fewer bins over a packing 

10with more bins duw to the term `bin_area * (n_bins - 1)` and 

11`bin_area >= min_area` (let us ignore the case where `bin_area == min_area`, 

12which does not make practical sense). Since `min_area < bin_area` in all 

13practically relevant cases, the offset `min_area` just distinguishes 

14packings that have same number of bins. Amongst such packings, those whose 

15least-occupied bin is closer to being empty are preferred (regardless where 

16this bin is). The idea is that this will eventually allow us to get rid of 

17that least-occupied bin in subsequent optimization steps, i.e., to reduce 

18the number of bins. 

19 

20This is similar to the :mod:`~moptipyapps.binpacking2d.objectives.\ 

21bin_count_and_small` objective, except that we do not try to expunge the last 

22bin, but any bin. It has the same lower and upper bound, though. 

23""" 

24from typing import Final 

25 

26import numba # type: ignore 

27import numpy as np 

28 

29from moptipyapps.binpacking2d.instance import Instance 

30from moptipyapps.binpacking2d.objectives.bin_count_and_last_small import ( 

31 BinCountAndLastSmall, 

32) 

33from moptipyapps.binpacking2d.packing import ( 

34 IDX_BIN, 

35 IDX_BOTTOM_Y, 

36 IDX_LEFT_X, 

37 IDX_RIGHT_X, 

38 IDX_TOP_Y, 

39) 

40 

41 

42@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False) 

43def bin_count_and_small(y: np.ndarray, bin_area: int, 

44 temp: np.ndarray) -> int: 

45 """ 

46 Compute the number of bins and the smallest occupied area in any bin. 

47 

48 We compute the total number of bins minus 1 and multiply it with the 

49 total area of items. We then add the area of items in the smallest bin. 

50 

51 :param y: the packing 

52 :param bin_area: the area of a single bin 

53 :param temp: a temporary array to hold the current area counters 

54 :return: the objective value 

55 

56 >>> tempa = np.empty(10, int) 

57 >>> bin_count_and_small(np.array([[1, 1, 10, 10, 20, 20], 

58 ... [1, 1, 30, 30, 40, 40], 

59 ... [1, 1, 20, 20, 30, 30]], int), 

60 ... 50*50, tempa) 

61 300 

62 >>> bin_count_and_small(np.array([[1, 1, 10, 10, 20, 20], 

63 ... [1, 2, 30, 30, 40, 40], # bin 2! 

64 ... [1, 1, 20, 20, 30, 30]], int), 

65 ... 50*50, tempa) 

66 2600 

67 >>> bin_count_and_small(np.array([[1, 2, 10, 10, 20, 20], # bin 2! 

68 ... [1, 2, 30, 30, 40, 40], # bin 2! 

69 ... [1, 1, 20, 20, 30, 30]], int), 

70 ... 50*50, tempa) 

71 2600 

72 >>> bin_count_and_small(np.array([[1, 3, 10, 10, 20, 20], # bin 3! 

73 ... [1, 2, 30, 30, 40, 40], # bin 2! 

74 ... [1, 1, 20, 20, 30, 30]], int), 

75 ... 50*50, tempa) 

76 5100 

77 >>> bin_count_and_small(np.array([[1, 3, 10, 10, 50, 50], # bin 3! 

78 ... [1, 2, 30, 30, 60, 60], # bin 2! 

79 ... [1, 1, 20, 20, 30, 30]], np.int8), 

80 ... 50*50, tempa) 

81 5100 

82 """ 

83 total_bins: int = 0 # the current idea of the number of bins 

84 n_items: Final[int] = len(y) # the number of rows in the matrix 

85 temp.fill(0) # fill temp with zeros 

86 

87 for i in range(n_items): # iterate over all packed items 

88 bin_idx: int = int(y[i, IDX_BIN]) - 1 # get the bin index of the item 

89 temp[bin_idx] += ((y[i, IDX_RIGHT_X] - y[i, IDX_LEFT_X]) 

90 * (y[i, IDX_TOP_Y] - y[i, IDX_BOTTOM_Y])) 

91 total_bins = max(total_bins, bin_idx) 

92 return (bin_area * total_bins) + temp[0:total_bins + 1].min() 

93 

94 

95class BinCountAndSmall(BinCountAndLastSmall): 

96 """Compute the number of bins and the area in the smallest one.""" 

97 

98 def __init__(self, instance: Instance) -> None: 

99 """ 

100 Initialize the objective function. 

101 

102 :param instance: the instance to load the bounds from 

103 """ 

104 super().__init__(instance) 

105 #: the internal temporary array 

106 self.__temp: Final[np.ndarray] = np.empty(instance.n_items, int) 

107 

108 def evaluate(self, x) -> int: 

109 """ 

110 Evaluate the objective function. 

111 

112 :param x: the solution 

113 :return: the bin size and smallest-bin-area factor 

114 """ 

115 return bin_count_and_small(x, self._bin_size, self.__temp) 

116 

117 def __str__(self) -> str: 

118 """ 

119 Get the name of the bins objective function. 

120 

121 :return: `binCountAndSmall` 

122 :retval "binCountAndSmall": always 

123 """ 

124 return "binCountAndSmall"