Bin Packing for Pattern Selection Clause Samples

Bin Packing for Pattern Selection. ‌ The bin packing problem (BPP) is one of the first problems shown to be NP-hard [45]. Given objects of integer size a1, . . . , an and maximum bin size C, the problem is to find the minimum number of bins k so that the established mapping f : {1,..., n} → {1,..., k} of objects to bins (a) =i a ≤ C for all i ≤ k. The problem is NP-hard in general, but there are known approximation strategies such as first-fit and best-fit decreasing (being at most 11/9 off the optimal solution [24]. The NP reduction is from number partitioning (where objects have to be i=1 split into two equally sized parts): if ∑n ai is odd, then number partitioning is not solvable; if ∑ n i =1 ai is even, then the objects have a perfect fit into two bins of size ∑n ai/2. 3 ∗ 3 = 9 2 ∗ 4 = 8 2 ∗ 3 = 6 1 ∗ 5 = 5 1 ∗ 3 = 3 3 ∗ 3 = 9 1 ∗ 3 = 3 2 ∗ 3 = 6 3 ∗ 3 = 9 2 ∗ 4 = 8 1 ∗ 3 = 3 2 ∗ 3 = 6 2 ∗ 4 = 8 3 ∗ 3 = 9 1 ∗ 3 = 3 1 ∗ 5 = 5 no space 1 ∗ 5 = 5 1 ∗ 5 = 5 2 ∗ 4 = 8 2 ∗ 3 = 6 Fig. 3.2 Example of a two-dimensional bin packing problem, with three different methods of solving it: one by using the largest size first, one by ordering in function of the largest side, and the last by an optimal planner. In the PDBs selection, the BPP is slightly different. In this situation, we will be using bins as PDBs (the term pattern is also used), and we think of variables or smaller previously computed PDBs as items we will try to fit in the bin. We estimate the expected size of the PDB by computing the product (not the sum) of the domain sizes, so that for a maximum bin capacity M imposed by the available memory, we find the minimum number of bins k so that the established mapping f of objects to bins maintains ∏ f (a)=i a ≤ M for all i ≤ k. By taking the logs of both sides, we are back to sums, but the sizes become fractional. In this case, ∏ f (a)=i is an upper bound on the number of abstract states needed. Taking the product of variable domains is a coarse upper bound. In some domains, the abstract state spaces are much smaller. Bin packing chooses the memory bound on each individual PDB, instead of limiting their sum. Moreover, for symbolic search, the correlation between the cross product of the domains and the memory needs is weak. As bin packing is pseudo-polynomial, small integers in the input lead to a polynomial-time dynamic programming algorithm [45]. There is a bin completion strategy that is featured in depth-first branch-and-bound algorithms for bin packing described in [85] and [86]. The ...