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

1""" 

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

3 

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

5`n_bins`. We know the total number of items, 

6:attr:`~moptipyapps.binpacking2d.instance.Instance.n_items`, as 

7well (because this is also the number of rows in the packing). 

8Now we return `(n_items * (n_bins - 1)) + min_items`, 

9where `min_items` is the number of items in the bin with the fewest items. 

10 

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

12bin_count_and_last_small`, but instead of focussing on the very last bin, it 

13uses the minimum element count over all bins. It has the same lower- and upper 

14bound, though. 

15""" 

16from typing import Final 

17 

18import numba # type: ignore 

19import numpy as np 

20 

21from moptipyapps.binpacking2d.instance import Instance 

22from moptipyapps.binpacking2d.objectives.bin_count_and_last_empty import ( 

23 BinCountAndLastEmpty, 

24) 

25from moptipyapps.binpacking2d.packing import IDX_BIN 

26 

27 

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

29def bin_count_and_empty(y: np.ndarray, temp: np.ndarray) -> int: 

30 """ 

31 Get the number of bins and number of elements in the emptiest one. 

32 

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

34 number of items. We then add the smallest number of elements in any 

35 bin. 

36 

37 :param y: the packing 

38 :param temp: the temporary array 

39 :return: the objective value 

40 

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

42 >>> bin_count_and_empty(np.array([[1, 1, 10, 10, 20, 20], 

43 ... [1, 1, 30, 30, 40, 40], 

44 ... [1, 1, 20, 20, 30, 30]], int), tempa) 

45 3 

46 >>> bin_count_and_empty(np.array([[1, 1, 10, 10, 20, 20], 

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

48 ... [1, 1, 20, 20, 30, 30]], int), tempa) 

49 4 

50 >>> bin_count_and_empty(np.array([[1, 2, 10, 10, 20, 20], # bin 2! 

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

52 ... [1, 1, 20, 20, 30, 30]], int), tempa) 

53 4 

54 >>> bin_count_and_empty(np.array([[1, 3, 10, 10, 20, 20], # bin 3! 

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

56 ... [1, 1, 20, 20, 30, 30]], int), tempa) 

57 7 

58 """ 

59 total_bins: int = -1 # the current idea of what the last bin is 

60 temp.fill(0) # empty all temporary values 

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

62 

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

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

65 temp[bin_idx] += 1 # increase number of items 

66 total_bins = max(total_bins, bin_idx) 

67 return (n_items * total_bins) + temp[0:total_bins + 1].min() 

68 

69 

70class BinCountAndEmpty(BinCountAndLastEmpty): 

71 """Get the number of bins and number of elements in the emptiest one.""" 

72 

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

74 """ 

75 Initialize the objective function. 

76 

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

78 """ 

79 super().__init__(instance) 

80 #: the internal temporary array 

81 self.__temp: Final[np.ndarray] = np.empty( 

82 instance.n_items, instance.dtype) 

83 

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

85 """ 

86 Evaluate the objective function. 

87 

88 :param x: the solution 

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

90 """ 

91 return bin_count_and_empty(x, self.__temp) 

92 

93 def __str__(self) -> str: 

94 """ 

95 Get the name of the bins objective function. 

96 

97 :return: `binCountAndEmpty` 

98 :retval "binCountAndEmpty": always 

99 """ 

100 return "binCountAndEmpty"