Coverage for moptipyapps / binpacking2d / objectives / bin_count_and_lowest_skyline.py: 40%
43 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"useable" space in any 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. This is done with the objective
22:mod:`~moptipyapps.binpacking2d.objectives.bin_count_and_last_skyline`.
24But we could also minimize the area under the skylines in the other bins.
25Because a) if we can get any skyline in any bin to become 0, then this bin
26disappears and b) if we can free up space in the bins by lowering the
27skylines, then we have a better chance to move an object from the *next* bin
28forward into that bin, which increases the chance to make that bin empty.
30In this objective function, we therefore use the smallest skyline area over
31all bins to distinguish between packings of the same number of bins.
32For all intents and purposes, it has the same lower and upper bound as the
33:mod:`~moptipyapps.binpacking2d.objectives.bin_count_and_last_small`
34objective.
35"""
36from typing import Final
38import numba # type: ignore
39import numpy as np
41from moptipyapps.binpacking2d.instance import Instance
42from moptipyapps.binpacking2d.objectives.bin_count_and_last_small import (
43 BinCountAndLastSmall,
44)
45from moptipyapps.binpacking2d.packing import (
46 IDX_BIN,
47 IDX_LEFT_X,
48 IDX_RIGHT_X,
49 IDX_TOP_Y,
50)
53@numba.njit(cache=True, inline="always", fastmath=True, boundscheck=False)
54def bin_count_and_lowest_skyline(y: np.ndarray, bin_width: int,
55 bin_height: int) -> int:
56 """
57 Compute the bin count-1 times the bin size + the space below the skyline.
59 :param y: the packing
60 :param bin_width: the bin width
61 :param bin_height: the bin height
62 :return: the objective value
64 >>> 10*0 + 10*20 + 10*30 + 10*40 + 10*0
65 900
66 >>> bin_count_and_lowest_skyline(np.array([[1, 1, 10, 10, 20, 20],
67 ... [1, 1, 30, 30, 40, 40],
68 ... [1, 1, 20, 20, 30, 30]], int),
69 ... 50, 50)
70 900
71 >>> 5 * 0 + 5 * 10 + 10 * 20 + 5 * 10 + 25 * 0
72 300
73 >>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
74 ... [1, 1, 10, 10, 20, 20],
75 ... [1, 1, 15, 0, 25, 10]], int),
76 ... 50, 50)
77 300
78 >>> 50*50 + min(5*0 + 10*10 + 10*10 + 25*0, 10*0 + 10*20 + 30*0)
79 2700
80 >>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
81 ... [1, 2, 10, 10, 20, 20],
82 ... [1, 1, 15, 0, 25, 10]], int),
83 ... 50, 50)
84 2700
85 >>> 5 * 0 + 5 * 10 + 3 * 20 + (50 - 13) * 25
86 1035
87 >>> bin_count_and_lowest_skyline(np.array([[1, 1, 5, 0, 15, 10],
88 ... [1, 1, 10, 10, 20, 20],
89 ... [1, 1, 15, 0, 25, 10],
90 ... [2, 1, 13, 20, 50, 25]], int),
91 ... 50, 50)
92 1035
93 >>> 2500*3 + min(10*10, 20*20, 25*10, 50*25)
94 7600
95 >>> bin_count_and_lowest_skyline(np.array([[1, 1, 0, 0, 10, 10],
96 ... [2, 2, 0, 0, 20, 20],
97 ... [3, 3, 0, 0, 25, 10],
98 ... [4, 4, 0, 0, 50, 25]], int),
99 ... 50, 50)
100 7600
101 """
102 bins: Final[int] = int(y[:, IDX_BIN].max())
103 len_y: Final[int] = len(y)
104 bin_size: Final[int] = bin_height * bin_width
105 min_area_under_skyline: int = bin_size
107 for use_bin in range(1, bins + 1):
108 cur_left: int = 0
109 area_under_skyline: int = 0
110 while cur_left < bin_width:
111 use_right = next_left = bin_width
112 use_top: int = 0
113 for i in range(len_y):
114 if y[i, IDX_BIN] != use_bin:
115 continue
116 left: int = int(y[i, IDX_LEFT_X])
117 right: int = int(y[i, IDX_RIGHT_X])
118 top: int = int(y[i, IDX_TOP_Y])
119 if left <= cur_left < right and top > use_top:
120 use_top = top
121 use_right = right
122 if cur_left < left < next_left:
123 next_left = left
125 use_right = min(use_right, next_left)
126 area_under_skyline += (use_right - cur_left) * use_top
127 cur_left = use_right
128 min_area_under_skyline = min(min_area_under_skyline,
129 area_under_skyline)
130 return ((bins - 1) * bin_size) + min_area_under_skyline
133class BinCountAndLowestSkyline(BinCountAndLastSmall):
134 """Compute the number of bins and the largest useful area."""
136 def __init__(self, instance: Instance) -> None:
137 """
138 Initialize the objective function.
140 :param instance: the instance to load the bounds from
141 """
142 super().__init__(instance)
143 #: the bin width
144 self.__bin_width: Final[int] = instance.bin_width
145 #: the bin height
146 self.__bin_height: Final[int] = instance.bin_height
148 def evaluate(self, x) -> int:
149 """
150 Evaluate the objective function.
152 :param x: the solution
153 :return: the bin size and last-bin-small-area factor
154 """
155 return bin_count_and_lowest_skyline(
156 x, self.__bin_width, self.__bin_height)
158 def __str__(self) -> str:
159 """
160 Get the name of the bins objective function.
162 :return: `binCountAndLowestSkyline`
163 :retval "binCountAndLowestSkyline": always
164 """
165 return "binCountAndLowestSkyline"