Coverage for moptipyapps / binpacking2d / objectives / bin_count_and_last_empty.py: 63%
30 statements
« prev ^ index » next coverage.py v7.13.0, created at 2025-12-11 04:40 +0000
1"""
2An objective function indirectly minimizing the number of bins in packings.
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)) + number_of_items_in_last_bin`,
9where `number_of_items_in_last_bin` is, well, the number of items in the
10very last bin.
12The idea behind this is: If one of two packings has the smaller number of
13bins, then this one will always have the smaller objective value. If two
14packings have the same number of bins, but one has fewer items in the very
15last bin, then that one is better. With this mechanism, we drive the search
16towards "emptying" the last bin. If the number of items in the last bin would
17reach `0`, that last bin would disappear - and we have one bin less.
18"""
19from typing import Final
21import numba # type: ignore
22import numpy as np
23from pycommons.math.int_math import ceil_div
25from moptipyapps.binpacking2d.objectives.bin_count import BinCount
26from moptipyapps.binpacking2d.packing import IDX_BIN
29@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
30def bin_count_and_last_empty(y: np.ndarray) -> int:
31 """
32 Compute the number of bins and the emptiness of the last bin.
34 We compute the total number of bins minus 1 and multiply it with the
35 number of items. We then add the number of items in the last bin.
37 :param y: the packing
38 :return: the objective value
40 >>> bin_count_and_last_empty(np.array([[1, 1, 10, 10, 20, 20],
41 ... [1, 1, 30, 30, 40, 40],
42 ... [1, 1, 20, 20, 30, 30]], int))
43 3
44 >>> bin_count_and_last_empty(np.array([[1, 1, 10, 10, 20, 20],
45 ... [1, 2, 30, 30, 40, 40], # bin 2!
46 ... [1, 1, 20, 20, 30, 30]], int))
47 4
48 >>> bin_count_and_last_empty(np.array([[1, 2, 10, 10, 20, 20], # bin 2!
49 ... [1, 2, 30, 30, 40, 40], # bin 2!
50 ... [1, 1, 20, 20, 30, 30]], int))
51 5
52 >>> bin_count_and_last_empty(np.array([[1, 3, 10, 10, 20, 20], # bin 3!
53 ... [1, 2, 30, 30, 40, 40], # bin 2!
54 ... [1, 1, 20, 20, 30, 30]], int))
55 7
56 """
57 current_bin: int = -1 # the current idea of what the last bin is
58 current_size: int = -1 # the number of items already in that bin
59 n_items: Final[int] = len(y) # the number of rows in the matrix
61 for i in range(n_items): # iterate over all packed items
62 bin_idx: int = int(y[i, IDX_BIN]) # get the bin index of the item
63 if bin_idx > current_bin: # it's a new biggest bin = new last bin?
64 current_size = 1 # then there is 1 object in it for now
65 current_bin = bin_idx # and we remember it
66 elif bin_idx == current_bin: # did item go into the current last bin?
67 current_size += 1 # then increase size
68 return (n_items * (current_bin - 1)) + current_size # return objective
71class BinCountAndLastEmpty(BinCount):
72 """Compute the number of bins and the emptiness of the last one."""
74 def evaluate(self, x) -> int:
75 """
76 Evaluate the objective function.
78 :param x: the solution
79 :return: the bin size and emptyness factor
80 """
81 return bin_count_and_last_empty(x)
83 def lower_bound(self) -> int:
84 """
85 Get the lower bound of the number of bins and emptiness objective.
87 We know from the instance (:attr:`~moptipyapps.binpacking2d\
88.instance.Instance.lower_bound_bins`) that we require at least as many bins
89 such that they can accommodate the total area of all items together.
90 Let's call this number `lb`. Now if `lb` is one, then all objects could
91 be in the first bin, in which case the objective value would equal to
92 :attr:`~moptipyapps.binpacking2d.instance.Instance.n_items`,
93 i.e., the total number of items in the first = last bin.
94 If it is `lb=2`, then we know that we will need at least two bins. The
95 best case would be that `n_items - 1` items are in the first bin and
96 one is in the last bin. This means that we would get `1 * n_items + 1`
97 as objective value. If we have `lb=3` bins, then we could have
98 `n_items - 1` items distributed over the first two bins with one item
99 left over in the last bin, i.e., would get `(2 * n_items) + 1`. And so
100 on.
102 :return: `max(n_items, (lb - 1) * n_items + 1)`
104 >>> from moptipyapps.binpacking2d.instance import Instance
105 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
106 >>> ins.n_items
107 3
108 >>> ins.lower_bound_bins
109 1
110 >>> BinCountAndLastEmpty(ins).lower_bound()
111 3
113 >>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
114 >>> ins.n_items
115 12
116 >>> ins.lower_bound_bins
117 2
118 >>> BinCountAndLastEmpty(ins).lower_bound()
119 13
121 >>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
122 >>> ins.n_items
123 31
124 >>> ins.lower_bound_bins
125 4
126 >>> BinCountAndLastEmpty(ins).lower_bound()
127 94
128 """
129 return max(self._instance.n_items,
130 ((self._instance.lower_bound_bins - 1)
131 * self._instance.n_items) + 1)
133 def upper_bound(self) -> int:
134 """
135 Get the upper bound of the number of bins plus emptiness.
137 :return: the number of items in the instance to the square
139 >>> from moptipyapps.binpacking2d.instance import Instance
140 >>> ins = Instance("a", 100, 50, [[10, 5, 1], [3, 3, 1], [5, 5, 1]])
141 >>> ins.n_items
142 3
143 >>> BinCountAndLastEmpty(ins).upper_bound()
144 9
146 >>> ins = Instance("b", 10, 50, [[10, 5, 10], [3, 3, 1], [5, 5, 1]])
147 >>> ins.n_items
148 12
149 >>> BinCountAndLastEmpty(ins).upper_bound()
150 144
152 >>> ins = Instance("c", 10, 50, [[10, 5, 20], [30, 3, 10], [5, 5, 1]])
153 >>> ins.n_items
154 31
155 >>> BinCountAndLastEmpty(ins).upper_bound()
156 961
157 """
158 return self._instance.n_items * self._instance.n_items
160 def to_bin_count(self, z: int) -> int:
161 """
162 Convert an objective value to a bin count.
164 :param z: the objective value
165 :return: the bin count
166 """
167 return ceil_div(z, self._instance.n_items)
169 def __str__(self) -> str:
170 """
171 Get the name of the bins objective function.
173 :return: `binCountAndLastEmpty`
174 :retval "binCountAndLastEmpty": always
175 """
176 return "binCountAndLastEmpty"