Coverage for moptipyapps / binpacking2d / objectives / bin_count_and_last_skyline.py: 41%
41 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 minimizes the number of bins and maximizes the
5"usable" space in the last bin.
7Which space is actually useful for our encodings? Let's say we have filled
8a bin to a certain degree and somewhere there is a "hole" in the filled area,
9but this hole is covered by another object. The area of the hole is not used,
10but it also cannot be used anymore. The area that we can definitely use is the
11area above the "skyline" of the objects in the bin. The skyline at any
12horizontal `x` coordinate be the highest border of any object that intersects
13with `x` horizontally. In other words, it is the `y` value at and above which
14no other object is located at this `x` coordinate. The area below the skyline
15cannot be used anymore. The area above the skyline can.
17If we minimize the area below the skyline in the very last bin, then this will
18a similar impact as minimizing the overall object area in the last bin (see
19:mod:`~moptipyapps.binpacking2d.objectives.bin_count_and_last_small`). We push
20the skyline lower and lower and, if we are lucky, the last bin eventually
21becomes empty.
23The objective
24:mod:`~moptipyapps.binpacking2d.objectives.bin_count_and_lowest_skyline`
25works quite similarly to this one, but minimizes the lowest skyline over any
26bin.
27"""
28from typing import Final
30import numba # type: ignore
31import numpy as np
33from moptipyapps.binpacking2d.instance import Instance
34from moptipyapps.binpacking2d.objectives.bin_count_and_last_small import (
35 BinCountAndLastSmall,
36)
37from moptipyapps.binpacking2d.packing import (
38 IDX_BIN,
39 IDX_LEFT_X,
40 IDX_RIGHT_X,
41 IDX_TOP_Y,
42)
45@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
46def bin_count_and_last_skyline(y: np.ndarray, bin_width: int,
47 bin_height: int) -> int:
48 """
49 Compute the bin count-1 times the bin size + the space below the skyline.
51 :param y: the packing
52 :param bin_width: the bin width
53 :param bin_height: the bin height
54 :return: the objective value
56 >>> 10*0 + 10*20 + 10*30 + 10*40 + 10*0
57 900
58 >>> bin_count_and_last_skyline(np.array([[1, 1, 10, 10, 20, 20],
59 ... [1, 1, 30, 30, 40, 40],
60 ... [1, 1, 20, 20, 30, 30]], int),
61 ... 50, 50)
62 900
63 >>> 5 * 0 + 5 * 10 + 10 * 20 + 5 * 10 + 25 * 0
64 300
65 >>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
66 ... [1, 1, 10, 10, 20, 20],
67 ... [1, 1, 15, 0, 25, 10]], int),
68 ... 50, 50)
69 300
70 >>> 50*50 + 0*10 + 10*20 + 30*0
71 2700
72 >>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
73 ... [1, 2, 10, 10, 20, 20],
74 ... [1, 1, 15, 0, 25, 10]], int),
75 ... 50, 50)
76 2700
77 >>> 5 * 0 + 5 * 10 + 3 * 20 + (50 - 13) * 25
78 1035
79 >>> bin_count_and_last_skyline(np.array([[1, 1, 5, 0, 15, 10],
80 ... [1, 1, 10, 10, 20, 20],
81 ... [1, 1, 15, 0, 25, 10],
82 ... [2, 1, 13, 20, 50, 25]], int),
83 ... 50, 50)
84 1035
85 >>> 50*50*3 + 25*50
86 8750
87 >>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
88 ... [2, 2, 0, 0, 20, 20],
89 ... [3, 3, 0, 0, 25, 10],
90 ... [4, 4, 0, 0, 50, 25]], int),
91 ... 50, 50)
92 8750
93 >>> 50*50*3 + 25*10 + 25*0
94 7750
95 >>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
96 ... [2, 2, 0, 0, 20, 20],
97 ... [3, 4, 0, 0, 25, 10],
98 ... [4, 3, 0, 0, 50, 25]], int),
99 ... 50, 50)
100 7750
101 >>> 50*50*3 + 20*20 + 30*0
102 7900
103 >>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
104 ... [2, 4, 0, 0, 20, 20],
105 ... [3, 2, 0, 0, 25, 10],
106 ... [4, 3, 0, 0, 50, 25]], int),
107 ... 50, 50)
108 7900
109 >>> 50*50*3 + 20*10 + 30*20 + 20*0
110 8300
111 >>> bin_count_and_last_skyline(np.array([[1, 1, 0, 0, 10, 10],
112 ... [2, 4, 0, 0, 20, 20],
113 ... [3, 2, 0, 0, 25, 10],
114 ... [2, 4, 10, 20, 30, 30],
115 ... [4, 3, 0, 0, 50, 25]], int),
116 ... 50, 50)
117 8300
118 """
119 bins: Final[int] = int(y[:, IDX_BIN].max())
120 len_y: Final[int] = len(y)
121 bin_size: Final[int] = bin_height * bin_width
122 area_under_skyline: int = 0
124 cur_left: int = 0
125 use_bin: int = max(y[:, IDX_BIN]) # the bin to use
126 while cur_left < bin_width:
127 use_right = next_left = bin_width
128 use_top: int = 0
129 for i in range(len_y):
130 if y[i, IDX_BIN] != use_bin:
131 continue
132 left: int = int(y[i, IDX_LEFT_X])
133 right: int = int(y[i, IDX_RIGHT_X])
134 top: int = int(y[i, IDX_TOP_Y])
135 if left <= cur_left < right and top > use_top:
136 use_top = top
137 use_right = right
138 if cur_left < left < next_left:
139 next_left = left
141 use_right = min(use_right, next_left)
142 area_under_skyline += (use_right - cur_left) * use_top
143 cur_left = use_right
144 return ((bins - 1) * bin_size) + area_under_skyline
147class BinCountAndLastSkyline(BinCountAndLastSmall):
148 """Compute the number of bins and the useful area in the last bin."""
150 def __init__(self, instance: Instance) -> None:
151 """
152 Initialize the objective function.
154 :param instance: the instance to load the bounds from
155 """
156 super().__init__(instance)
157 #: the bin width
158 self.__bin_width: Final[int] = instance.bin_width
159 #: the bin height
160 self.__bin_height: Final[int] = instance.bin_height
162 def evaluate(self, x) -> int:
163 """
164 Evaluate the objective function.
166 :param x: the solution
167 :return: the bin size and last-bin-small-area factor
168 """
169 return bin_count_and_last_skyline(
170 x, self.__bin_width, self.__bin_height)
172 def __str__(self) -> str:
173 """
174 Get the name of the bins objective function.
176 :return: `binCountAndLowestSkyline`
177 :retval "binCountAndLowestSkyline": always
178 """
179 return "binCountAndLastSkyline"