From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

1 Introduction

When presented with a new combinatorial problem, how do we construct an effective optimization procedure? Korf has demonstrated how to convert approximation algorithms for number partitioning into branching rules within optimization procedures [Korf, 1995]. He con­ cluded that this "presents an example of an approach that may be effective on other combinatorial problems. Namely, we took a good polynomial-time approximation algorithm, and made it complete, so that the first solu­ tion found is the approximation, and then better solu­ tions are found as long as the algorithm continues to run , eventually finding ~he optimal solution" [Korf, 1995]. We test this claim for a closely related problem, bin packing using the Decreasing Best Fit approximation algorithm.

*Supported by EPSRC award GR/K/65706. We thank the members of the APES group, especially Paul Shaw.

value [Slatford and Yeadon, 1970]. Problems such as scheduling, processor allocation, fabric cutting and min­ imization of VLSI circuit size and delay, can be modeled by bin packing problems. Bin packing is NP-complete in the strong sense [Garey and Johnson, 1979].

We consider a general bin packing problem in which the bins can have different capacities. This allows us to reason about the subproblems encountered during search when bins may be partially full. In addition, as we show in Sec. 9, many other problems like number partition­ ing can be seen as instances of such general bin packing problems. A bin packing problem consists of a set of objects Sand a set of bins B. Each object s E S has a weight w 3 , and each bin b E B has a capacity Cb. The difference between the sum of the bin capacities and the sum of the weights is the spare capacity, sc. The aim is to partition the objects between the bins so that the sum of weights in each bin is less than or equal to its capacity. All weights and capacities are integers. If all the bins have the same capacity, this is the NP-complete problem SRI from [Garey and Johnson, 1979].

Decreasing Best Fit (DBF) is one of the best polynomial-time approximation algorithms for bin pack­ ing. Best Fit puts the next object into the fullest bin that will accommodate it without exceeding the capa­ city. DBF simply sorts the objects into decreasing order of their weight before calling Best Fit. Objects with the largest weights are thereby packed first. DBF is guaran­ teed asymptotically to use no more than 11/9 times the optimal number of bins, compared to Best Fit which can use 17/10 times the optimal [Garey and Johnson, 1979] .

3 A branching rule

To develop an optimization procedure for bin packing, we follow Korf's methodology, and convert the Decreas­ ing Best Fit approximation algorithm into a branching rule within the Complete Decreasing Best Fit (CDBF) optimization procedure. CDBF .computes a lower bound on the number of bins required. If all the bins have the same capacity, c then we need at least r u 1 c 1 bins where u is the sum of the weights. Search begins with the num­ ber of available bins equal to this lower bound. If the search tree is exhausted before a packing is found, the number of available bins is incremented. This usually relaxes the constraints sufficiently to make packing easy.

The objects are sorted into decreasing order of their weight and packed into bins by the branching rule. The first choice of the branching rule is that made by the De­ creasing Best Fit approximation algorithm. That is, it packs the next object into the fullest bin that accommod­ ates it . To make the optimization procedure complete, we must decide what the branching rules does on back­ tracking. A natural generalization is to order bins by how full they are. The branching rule thus tries to pack the next object into the fullest bin that accommodates it, and on backtracking, tries bins in increasing order of their unused capacity. A branch terminates successfully if all the objects i!.re packed into bins. A branch terminates unsuccessfully and forces backtracking when the next object cannot be packed into any bin. That is, when the weight of the next object exceeds the largest unused capacity. To avoid duplicating search, the branching rule does not pack an object into more than one bin with the same unused capacity. We therefore never open more than one new bin for any object. As a consequence, the first object is always packed into the first bin, the second object into the first or the second bin, etc. In the worst case, when packing n objects into b bins, CDBF explores all bn jb! different packings.

4 A pruning rule

A bin packing problem imposes constraints on how the weights in the bins add up. We decompose these con­ straints into constraints on how the bit positions add up. To do this, we take the modulus of the weights and ca­ pacities to a set of bases. Often the bases will be all the powers of 2 since, as we show in Sec. 5, we can then use simple logical operations on the binary representation. However, other bases can be used at little extra cost.

The constraint on each bin is that the sum of the weights is no more than the capacity of the bin. To reason about how the spare capacity is distributed across the bins, we construct a set 1 sc containing sc "dummy" objects, each with a weight of 1. We now have to find an exact packing of S U 1 sc so that the sum of the weights in each bin is strictly equal to the capacity of the bin. That is, for each bE B,

To focus on different bit positions, we take the modulus of both sides of this equation to the base m,

And sum over the bins,

Unfortunately, we cannot use this equation directly as we do not know which objects will be put in each bin. We can, however, give an upper bound for the left hand side of (1) assuming the worst possible partition of weights for the mod sum. To derive the bound, we use the fact that for any integers a and b,

Applying this repeatedly to the left hand side of (1) gives

But the nested summation sums over all the weights in all the bins. Hence,

That is,

Now, if s E 1·c then Ws = 1 and (1 mod m) = 1 for all m. Thus,

This is our general pruning bound. The first two terms of the LHS of (2) represents the maximum contributions mod m that we can expect from the spare capacity and S. The third term represents the capacities mod m that we need these contributions to reach. If at any time, the LHS is less than zero, the packing of the bins is impossible. We can then prune search.

As an example, consider again the bin packing prob­ lem from the introduction. This problem has no spare capacity. Mod 2, we have objects with zero weight (i .e. the weights provide no parity bits), and two bins each with a capacity of 1 (i .e. each bin needs a parity bit). The LHS of (2) is 0-2. Since this is less than zero, we cannot pack the objects into the two bins.

As a second example, can objects with weights 650, 540, 390, 260 and 130 be packed into two bins of ca­ pacity 1000? Consider this problem mod 128. The ob­ jects contribute weights mod 128 of 10, 28 , 6, 4 and 2 respectively. In addition , we have 30 units of spare ca­ pacity. However, each bin needs 1000 mod 128 = 104. The objects cannot therefore be packed into the bins . The pruning bound reflects this; the LHS of (2) is 30 + (10 + 28 + 6 + 4 + 2) - (104 + 104) . As this is less than zero, we cannot pack the objects into the bins.

5 Implementation

To implement checking the bound efficiently, we make three critical observations. First, if the moduli used are all powers of a given base (e.g. m, m 2 , m 3 ... ) , many computations from one power of the base can be reused in the next higher power. For example, with powers of 10, (a mod 1000) > (b mod 1000) if either the 100's digit of a is larger than that of b, or if the 100's digits of the numbers are the same and (a mod 100) > (b mod 100) . Similar reuse of calculated values can be made for other operations such as longhand addition and subtraction.

Second, the LHS of (2) changes only slightly when an object is assigned to a bin. In fact, detailed analysis shows that if we put an object s into a bin b, the value of the LHS of (2) does not change at all if ( w, mod m) ~ (cb mod m), and is otherwise simply reduced by m. It is more efficient therefore to initialise the values of the LHS of (2) at the start of search, and merely compute the change to these values at each node. To restore the values on backtracking, we use one bit for each modulus m indicating if the LHS of (2) was decremented.

These two observations combine together. We initially find the base m expansion of the weights and capacities. Then at each node, we perform the subtraction Cb - Ws longhand in base m. In doing this, the values of the LHS of (2) in each power of m are decremented when there is a borrow in that digit position , since a borrow is necessary when (w, mod m) > (cb mod m). The com­ plexity of the operations performed at each node is thus the same as that of the subtraction Cb - w, , which has to be performed in any case. The only other operation is that of decrementing the LHS of (2) and incrementing it on backtracking. The LHS of (2) is always a multiple of m so we store the value divided by m and decrement it and increment it by 1 instead of m. Since this value is a number bounded above by n, these decrements and increments take less than O(log n) time. In practice n is small and it may take just a single machine opera­ tion. We can thus implement checking the bound in all powers of a given base with a constant factor overhead compared to CDBF without modular pruning. Our ex­ periments support this observation.

Our third observation does not affect the theoretical complexity but does make a practical implementation more efficient. A natural set of bases to use is all powers of 2. This is the set of bases used in the experiments reported here. This choice allows us to take advantage of the binary representation of numbers in computers. For example, finding the value of an integer modulus a power of 2 is very cheap. In addition, we do not need to perform the subtraction longhand since the bits of (a xor b xor a - b) indicate whether a borrow was ne­ cessary into a given bit position when computing a -b.

6 Experiments

As in previous experimental studies [McGeoch, 1986], we pack objects with pseudo-random integer weights into bins that are twice their maximum size. We generate n objects each with a weight drawn uniformly and ran­ domly from (0, l] and pack into bins of capacity 21. Ex­ ploratory tests with this model show large variation in problem difficulty. For example, the worst case for a sample of 1,000 bin packing problems with 20 objects of size 2 11 took 3,522,573 nodes whereas 90% of problems needed just 1 branch. The data suggests that problem difficulty is very dependent on the spare capacity.

We therefore modify the model to generate problems with a predetermined spare capacity. We use two addi­ tional parameters: a lower bound on the number of bins, d, and a spare capacity, sc. The new model constructs bin packing problems which, if they pack into d bins of capacity 2/, leave a spare capacity of sc. We generate n- 1 objects with weights randomly and uniformly dis­ tributed on (0, l]. Let w be 2ld- sc- cr. This is the weight the nth and final object would need to have to give the required spare capacity. If w E (0, l] then we assign the nth object this weight. If not, we throw away then -1 objects and start again. We experimented with a variety of spare capacities, but found that performance was broadly similar with weights in the range (0, l] and spare capacity sc as with weights i11 the range (0, ljsc] and spare capacity 0. In the rest of the paper we restrict attention to problems with no spare capacity.

To determine the overhead modular pruning adds to CDBF in practice, Fig. 1 gives a scatter plot of nodes searched to find the optimal packing against CPU time with and without modular pruning. We use 100 prob­ lems at each value of n from 8 to 20 and random 10-bit weights which leave no spare capacity when packed into n/4 bins. In this and subsequent experiments, we prune with bases that are powers of 2. CDBF was coded into Common Lisp and run on a network of identical DEC Alpha 300LX's with 125MHz processors. This graph supports our claim that pruning adds a constant factor overhead to runtime. Regression for cpu seconds per node suggests that the overhead is about a factor of 5.4 for n = 8 but declines to 2.4 at n = 20. The nearly linear nature of this graph also supports the practice of using nodes searched as a proxy for cpu time.

The pruning rule can reduce search significantly. Fig. 2 shows the mean nodes searched to find the optimal packing against log 2 (/). We again generate bin pack­ ing problems with 8 to 20 objects which have no spare capacity when packed into n/4 bins. We use 1,000 prob­ lems at each value of n and /. As in other NP-complete problem classes [Cheeseman eta/., 1991], there is a phase transition as the constrainedness varies. At smalllog2 (/), almost all problems pack into n/4 bins easily. At large log 2 (/) , almost all problems require an extra bin. The hardest bin packing problems tend to occur in the phase transition inbetween. We see similar behavior to Fig. 2 in the median and other percentiles of performance.

As was exp~cted, the effectiveness of the pruning rule increases as log 2 (1) increases and we have more bits with which to prune. For example at n = 20 and log2(l) = 45 mean cpu time was reduced from 274 to 246 seconds with mod pruning, despite the overhead. The effectiveness of the pruning rule also increases as the number of ob­ jects being packed increases. Fig. 2 supports our claim that modular pruning reduces search significantly. On the harder problems, runtimes can reduce by an order of magnitude even in the phase transition region. For example, at n = 20 and log2(/) = 10, one problem took

1,258 cpu seconds without modular pruning but only 80 seconds with it. The pruning rule cannot increase the number of nodes searched, so where cpu time is greater it is by no more than the implementation overhead.

In conclusion, the pruning rule adds essentially a con­ stant factor overhead to but reduces search significantly. On the hardest problems, runtime can be reduced by an order of magnitude. For problems larger than considered here, the search tree may become too large to explore exhaustively. On such problems, we might consider a search strategy like ILDs [Korf, 1996). This systematic­ ally explores decisions made against the branching heur­ istic. Unlike depth-first search, ILDS can undo branching mistakes high in the search tree at little cost, as well as taking advantage of pruning and propagation rules.

7 Multiple mod pruning

If we multiply the weights and capacities by some con­ stant then we get an equivalent bin packing problem. However, the modulus of the numbers may now offer new pruning opportunities. To test this hypothesis, Fig. 3 plots median and 99th percentile in nodes searched with pruning bounds derived by multiplying the weights and capacities by 1, 3, 5, and 7. We use 100 problems n = 20 for varying/. Fig. 3 shows that multiple modular prun­ ing offers further reductions in search over the regular bound. By adding pruning possibilities we can only re­ duce the number of nodes searched. These reductions in search can result in shorter runtimes on harder problems than single modular pruning or no modular pruning.

8 A propagation rule

Propagation rules determine when branching decisions are forced. For example, the Davis Putnam satisfiab­ ility procedure [Davis and Putnam, 1960) has the unit propagation rule. This assigns truth values to variables in unit clauses as these values are forced. This rule con­ tributes significantly to the effectiveness of the Davis Putnam procedure. Propagation rules can often be con­ structed by adding look-ahead to a suitable pruning rule.

For instance, the Davis Putnam procedure also has an empty clause pruning rule. This prunes search when an empty clause is generated. The unit propagation rule is merely a one-step look-ahead on top of the empty clause pruning rule. Suppose we have a unit clause, /. Look­ ing ahead, if we instantiate I to False, then the empty clause pruning rule would fire. We therefore assign l to True. But this is precisely the unit clause propagation rule: if we have a unit clause, I then we assign I to True.

We can construct a propagation rule based on the pruning rule for bin packing in an identical fashion. In each base, the propagation rule packs the object with largest weight in that modulus into one of the bins, and tests the pruning bound. If the bound rejects every bin, we prune search. If the bound rejects all but one bin, we pack the object into the relevant bin. This adds an inter-node cost of O((n +d) log(/) 2 ) if we use all powers of 2 as bases, as we do here. Fig. 4 shows the median and 99th percentile in nodes searched with and without this propagation rule. We again use 100 problems at n = 20. Despite the larger overheads, the reductions in search can result in shorter runtimes on the harder prob­ lems compared to CDBF either with or without modular pruning.

-i. -

9 Other applications

We now describe some other application domains.

9.1 Subset sum

Given a set S, is there a subset whose weights have a given target sum t? Subset sum is problem SP13 in [Garey and Johnson, 1979]. It is equivalent to bin pack­ ing into two bins with capacities t and (T- t where (T is the sum of the weights. The pruning bound becomes,

For example, is there a subset of 17, 12, 9 and 4 with sum 23? Consider the numbers mod 4. We have 1, 0, 1 and 0 with which to meet the target sums of 23 mod 4 and 19 mod 4 (that is, 3 and 3). It is therefore impossible to find a subset with the required sum. This is confirmed by the bound, with the LHS being less than zero.

9.2 Number partitioning

Given a set S is there a partition of S into k sets whose weights have an equal sum? For k = 2 this is SP12 in [Garey and Johnson, 1979]. Number partitioning is equivalent to bin packing into k equal bins with capa­ cities (Tik, where (Tis the sum of the weights, assumed to be a multiple of k. To construct a pruning bound that applies in the middle of search, we assume that we have constructed a partial partition of S, that the partial partitions have weights with sums s;, and that s; ~ (T I k. Let S' be the numbers still to be partitioned. The re­ maining problem is equivalent to bin packing into k bins with capacities (T I k- s;. This gives the pruning boumd,

Note that the first term is less than JSJ.m and the second is less than k .m. For a fixed number of objects, we are therefore more likely to break the bound for large k. This agrees with our intuitions. The more bins we have, the more likely we will be able to deduce using modular arithmetic that we cannot fill one of the bins . A similar bound can be derived for inexact number partitioning problems in which the sum of the weights is not neces­ sarily a multiple of k, and the sums of the partitions is within some Ll > 0. To construct a bound here, we add to S an extra set of "dummy" objects with unit weight .

9.3 Knapsack problems

In the 011 knapsack problem, we have a set of objects S, each object s E S has a weight w, and a value v,. We also have a target value v and a knapsack which can contain a weight w. Is it possible to put objects in the knapsack to reach the target value without exceeding the weight? This is problem MP9 in [Garey and Johnson, 1979]. For simplicity, consider the special case where the weights of the objects equal their values . Let (T be the sum of the weights. Then we wish to find a subset of S with weight at least v but no more than w. This is equivalent to packing into two bins, with capacities w and u- w, and with a spare capacity of w- v.

10 Related Work

Korf converted the Greedy and the Karmarkar-Karp approximation algorithms for number partitioning into branching rules for optimization procedures [Korf, 1995]. The pruning rules Korf used are the analogues of the simple pruning rule in CDBF without modular pruning.

McGeoch has performed extensive experiments on the First Fit, Best Fit, Decreasing First Fit and Decreas­ ing Best Fit approximation algorithms [McGeoch, 1986], using objects with integer weights and bins of capacity 2 30 -1. She observed a 'critical region' in which Decreas­ ing First Fit gave packings with a large amount of empty space. As these packings tended to occur when there was a statistical excess of objects with large weights, this re­ gion may become less important as n increases and the distribution of weights tends to become more uniform.

Bin packing has a polynomial-time asymptotic ap­ proximation scheme [Papadimitriou, 1994]. This uses modular arithmetic to reduce the grain size of the weights ~ To approximate within f, each weight w is re­ placed by r w 1 q 1 where q is the quantum size of weights, lfcj and cis the bin capacity. Knapsack problems have been proposed as the basis of a public-key cryptosystem [Merkle and Hellman, 1978]. The receiver deciphers the encoded message by multiplying the weights of the knap­ sack problem by a secret key and taking the modulus us­ ing a second secret key. This gives a knapsack instance that can be rapidly solved. Brickell (personal commu­ nication cited in [Lagarias and Odlyzko, 1985]) sugges­ ted that difficult and 'dense' cryptographic knapsack problems with many objects and small weights might be solved by converting them to 'low-density' problems through one or more modular multiplications. [Bright et al. , 1994] describes a parallel method for solving knap­ sack problems . Modular arithmetic may still be of use in such methods for eliminating parts of the search space.

11 Conclusions

The main contributions of this paper are new pruning and propagation rules for bin packing and some closely related problems. The pruning rule uses a bound con­ structed by decomposing the numerical constraints with modular arithmetic. We incorporated this rule into a new optimization procedure, Complete Decreasing Best Fit. We showed that the pruning rule adds essentially a constant factor overhead to runtime whilst reducing search significantly. On the hardest problems, runtime can be reduced by an order of magnitude. Finally, we demonstrated how propagation rules can be built by adding lookahead to pruning rules. There are many dir­ ections for future research. For example, how do we identify good sets of bases and multiples for pruning?

What contributions might this research make beyond bin packing? First , the pruning bound can be applied to many other partition problems like subset sum, number partitioning, and knapsack problems. Second, modular arithmetic may be useful in constructing pruning bounds and propagation rules in other combinatorial problems involving numerical constraints. Third, new propagation rules may be developed by adding lookahead to existing pruning rules. Fourth, this paper presents an example of a general methodology for building optimization pro­ cedures in new domains. That is, we construct a branch­ ing rule based on a good approximation algorithm, and pruning and propagation rules derived from a bound on the solution to the remaining subproblem. This ap­ proach may be effective on other NP-complete problems.