Search Strategies for Optimal Multi-Way Number Partitioning

1 Introduction

Number partitioning is one of the simplest problems in combinational optimization: it seeks to divide n positive integers across k mutually exclusive and collectively exhaustive subsets 〈S1, S2, ..., Sk〉 so as to minimize the sum of the largest set. For instance, given the integers {1, 2, 3, 4, 5}, the 3-way partitioning 〈{1, 4}, {2, 3}, {5}〉 is an optimal solution that perfectly balances all subsets to an equal sum of 5. Despite its simplicity, number partitioning is nevertheless NP-complete [Garey and Johnson, 1979] and often used to prove the NP-completeness of other quantitative reasoning problems (e.g., bin packing, knapsack, etc.). Real-world applications and extensions of number partitioning are numerous, including multi-processor scheduling [Sarkar, 1989; Pinedo, 2008], machine reassignment [Mehta et al., 2012], and voting manipulation [Walsh, 2011]. Hence, efficient methods to determine optimal solutions are particularly relevant in the broader scope of combinatorial search.

Although number partitioning has served as a case study of optimal search techniques for nearly two decades, a renewed interest has emerged in recent years. In contrast to earlier approaches that recursively assign individual numbers to subsets [Korf, 1995], these new algorithms explore the space of potential pairwise decompositions in which entire subsets of numbers are generated in their entirety and partitioned independently [Korf, 2009]. Enhancements to this approach have considered more efficient means of iterating through viable subsets, as well as hybrid schemes that invoke different solving strategies depending on the values n and k [Korf, 2011]. A key insight shared by each of these previous algorithms is a principle of optimality, in which the optimality of the global solution is ensured by exploring only the space of optimal solutions to the elements in each decomposition.

While this divide-and-conquer strategy reduces the joint search space of subproblems, the cost of evaluating intermediate solutions remains high: there are exponentially-many decompositions, and the effort to resolve each one to optimality imposes a significant burden on the core optimization engine. Since successive decompositions are solved independently, a high degree of similar state is searched between repeated invocations of the subproblem solver. These deficiencies limit the efficacy of prior algorithms, especially for large k values that require many nested levels of bisection.

In this paper, we propose a new approach to multi-way number partitioning. Unlike previous algorithms, we consider the construction of potentially suboptimal decompositions, a task that is much easier to achieve and less time consuming. Under certain conditions, our approach may even neglect to produce solutions to subproblems if they exist. Yet, surprisingly, we are still able to provide the same properties as earlier works, including completeness, anytime behavior, and (most importantly) a guarantee of global optimality. To achieve this, we exploit a specific property of the objective function and develop a principle of weakest-link optimality that eliminates the need to consider purely optimal decompositions. We use this principle to strengthen the relationship between sequential decompositions by enforcing tighter bounds on partial assignments, and also to detect and remove dominated solutions from consideration. The efficiency of our algorithm is extremely competitive, outperforming the previous state-of-the-art by orders of magnitude and reducing average runtime on the largest benchmarks from several hours to less than a second. Empirical data also suggest that the performance of our algorithm is nearly independent of k.

2 Background

Exact approaches to number partitioning vary widely in how they model and explore the space of possible partitions. Here, we present an overview of prior approaches to this problem.

2.1 Complete Greedy Algorithm (CGA)

A simple greedy heuristic that produces high-quality (albeit suboptimal) solutions is to sort the numbers by size in decreasing order, and incrementally assign each one to the partition whose size is smallest [Graham, 1969]. This simple approach can be modified to compute optimal solutions by incorporating backtracking: each assignment of a number to a partition creates a different branch in search, and all possible combinations of assignments are attempted in order to produce the one with minimal cost (see Figure 1). By extending this depth-first framework with branch-andbound pruning techniques and symmetry breaking, one arrives at the Complete Greedy Algorithm (CGA) [Korf, 1995; 1998]. CGA is thus a direct approach to combinatorial optimization, in which each number Si corresponds to a decision variable vi whose domain D(vi) is the set of possible subsets {S1, S2, ..., Sk} that participate in the partition. All fullyinstantiated complete assignments to these variables correspond to legal partitioning solutions.

2.2 Complete Karmarkar-Karp Algorithm (CKK)

An alternative greedy heuristic (named KK) constructs solutions in an entirely different way. Rather than committing each number to a specific partition, it instead considers potential pairings based on set difference [Karmarkar and Karp, 1982]. In each iteration of the algorithm, the two largest numbers are extracted from the set, and replaced by their absolute difference. In doing so, the numbers (or more generally, the subsets containing them) are ensured to be assigned to different partitions. The ultimate arrangement of these subsets is not finalized until the list is fully processed. A complete extension to this heuristic exists as well (the Complete Karmarkar-Karp algorithm, or CKK) [Korf, 1998]. The additional branches in this variation correspond to set unions, where numbers are joined rather than assigned to exclusive subsets. For k = 2, CKK performs dramatically faster than CGA (especially in the presence of perfect partitions) and can be further improved by pruning certain leaf nodes [Cerquides and Meseguer, 2012]. However, due to the high overhead and bookkeeping required, CKK is less effective for large k.

2.3 Recursive Number Partitioning (RNP)

Recall that in CGA, each number Si is committed to a specific subset before the assignment of any subsequent numbers are processed. A radically different approach is taken by Recursive Number Partitioning (RNP) [Korf, 2009], in which a complete set of members for a range of partitions is constructed (and partitioned) before considering the members of subsequent partitions. If k is even, the set of partitions may be divided in half, and each individual number can be assigned to one half or the other. If k is odd, the partitions may be divided into S1 and [S2, Sk]. In order to explore the space of all possible arrangements, an inclusion-exclusion tree is searched (see Figure 2). Here, a binary decision variable vi denotes the inclusion or exclusion of the number Si from a set Sj. An internal node of this tree may be pruned if a partial subset cannot possibly extend to a better solution. The leaves of this tree correspond to coarse decompositions of numbers to subproblems, but not necessarily to assignments within each group. To construct solutions, optimal partitions are obtained for each subproblem, and combined if their concatenation results in an improved solution. Subproblems are solved in the same way; only in the base case (where k = 2) is traditional two-way partitioning employed. For certain values of n and k, RNP is several orders of magnitude faster than CGA.

2.4 Improved Recursive Number Partitioning

The basic framework of RNP has recently been enhanced in two fundamental ways to produce the Improved Recursive Number Partitioning (IRNP) algorithm [Korf, 2011]. First, the inclusion-exclusion tree is replaced by an extension of the SS algorithm [Schroeppel and Shamir, 1981] that more effectively searches the space of viable subset sums. This new approach, called ESS, divides the set of numbers in half and enumerates all possible subsets in each division. Although this requires exponential memory, it allows very fast exploration of satisficing sums simply by iterating through the two halves in tandem. Second, the solver makes calls to CGA (or CKK) for small n, since these problems tend to be more amenable to the original search space. Again, the efficacy of IRNP was shown to be orders of magnitude faster than previous works under certain conditions.

3 The Principle of Weakest-Link Optimality

Previous algorithms for multi-way partitioning have relied greatly on a so-called principle of optimality. To facilitate the following discussion, we define a [k1, k2]-decomposition of a partition P = 〈S1, S2, ..., Sk〉 to be a pair 〈P1, P2〉 such that P1 = 〈S1, S2, ..., Sk1 〉 and P2 = 〈Sk1+1, Sk1+2, ..., Sk1+k2 〉, where k1 + k2 = k. Its composition is written as 〈P1 · P2〉. We also define max(Pj) to be the maximum subset sum in Pj, and opt(Pj) to be the maximum subset sum in any optimal repartitioning of Pj.

Theorem 1: Given any optimal k-way partition P and a [k1, k2]-decomposition 〈P1, P2〉, any optimal k1-way repartitioning of P1 combined with any optimal k2-way repartitioning of P2 produces an optimal k-way partition P ′ . □

Using this principle, it is possible to construct a globally optimal k-way partitioning P ′ by exploring the space of viable decompositions and computing optimal solutions to partitions smaller than k independently.

Corollary 1: There exists an optimal k-way partition P ′ = 〈P1 · P2〉, where 〈P1, P2〉 is a [k1, k2]-decomposition of P ′ , and both P1 and P2 are optimal. [Korf, 2009] □

For any partition P ′ that satisfies this corollary, we denote it as being semi-optimal (in addition to being optimal in the traditional sense) since the elements of its decomposition are optimal as well. Unfortunately, the property of semioptimality alone does not provide a sufficient condition for the global optimality of a given partition: that is, some semioptimal solutions do not form a globally optimal composition.

Example: Consider a 3-way partitioning instance containing the numbers {1, 2, ..., 7}. Solution S = 〈{7, 3}, {6, 2, 1}, {5, 4}〉 is both optimal and semi-optimal with respect to a [1, 2]-decomposition, since partitions 〈{7, 3}〉 and 〈{6, 2, 1}, {5, 4}〉 are independently optimal with maximum subset sums of 10 and 9, respectively. However, while S′ = 〈{7, 4}, {6, 3}, {5, 2, 1}〉 is also semioptimal with respect to a [1, 2]-decomposition, its maximum subset sum is 11 and therefore is not globally optimal. □

Because of this, all viable decompositions must be exhaustively considered to ensure the optimality of the composition. Furthermore, the requirement that these subproblems must be solved optimally themselves imposes a significant burden on even the most efficient implementation. In response, we propose a principle of weakest-link optimality that substantially reduces expectations on decomposition quality:

Theorem 2: Given any optimal k-way partition P and a [k1, k2]-decomposition 〈P1, P2〉, any k1-way repartitioning of P1 where max(P1) ≤ opt(P) combined with any k2-way repartitioning of P2 where max(P2) ≤ opt(P) produces an optimal k-way partition P ′ . □

The proof of this theorem is trivial. By definition, the cost of an optimal solution opt(P) is simply equal to max(P). Furthermore, the maximum subset sum of a composition of elements must be at least as large as the largest maximum subset sum of each partition participating in its decomposition. A key difference between this theorem and the original principle of optimality is that one possible solution for P ′ is P itself; in other words, any optimal solution may be produced by the above construction.

Corollary 2: Every optimal k-way partition P is the combination 〈P1 · P2〉 of a [k1, k2]-decomposition where max(P1) ≤ opt(P ) and max(P2) ≤ opt(P ). □

The principle of weakest-link optimality relaxes the requirement that the solutions to the decomposition are optimal; that is, each max(Pj) must be no greater than opt(P), but it may potentially exceed opt(Pj). This implies a fundamental consequence: semi-optimality is not a necessary condition for global optimality, hence optimal solutions may be composed from (potentially) suboptimal solutions to the subproblems of a decomposition.

Example (cont'd): Consider again the 3-way partitioning instance containing the numbers {1, 2, ..., 7}. Solution S′′ = 〈{7, 3}, {6, 4}, {5, 2, 1}〉 is globally optimal, yet not semi-optimal: 〈{6, 4}, {5, 2, 1}〉 has a maximum subset sum of 10, whereas a lower sum of 9 is achievable. □

The secret to this result lies in the sensitivity of the objective function: since only the maximum subset sum contributes to the quality of a solution (i.e., its "weakest link"), the relative balance between the remaining subsets is irrelevant. In some domains, objective functions that exhibit weakest-link optimality help to reduce the computational complexity required for exact optimization. For instance, in the case of constraint-based temporal reasoning, WLO-optimal solutions may be computed in polynomial time [Khatib et al., 2001; 2003]. Within our context of number partitioning, the difficulty in exploiting the principle of weakest-link optimality when systematically generating solutions is that the value of opt(P) is unknown in advance. Fortunately, it is possible to dynamically maintain upper and lower bounds on opt(P) by integrating the intermediate results obtained between successive decompositions. This forms the basis of our approach, which is described in the following section.

4 ANewMethod

We now introduce our method for optimal k-way number partitioning. As in prior work, we define the cost of a partitioning P = 〈S1, S2, ..., Sk〉 to be the maximum subset sum, rather than the maximum difference between sets [Korf, 2010]; hence, the quantity:

is to be minimized. In addition to the parameter k and the original set S of numbers, our solver also takes as input a pair 〈cmin, cmax〉. Solutions whose costs are greater than cmax need not be considered, and any solution whose cost is cmin or less may be returned immediately. Optimal solutions to the original k-way partitioning may be obtained by passing 〈max(S), ∑ S〉. As will be shown later, more aggressive settings to these parameters can be used to communicate expectations between nested invocations of the algorithm.

4.1 Basic Framework

Similar to previous methods, we assemble partitions through recursive decomposition, where potential subsets are constructed by exploring an inclusion-exclusion binary tree.

However, in contrast to the state-of-the-art, our implementation does not consider balanced [k/2, k/2] decompositions in the case of even k; this affords additional pruning capabilities (see Section 4.3) and also ensures consistent performance regardless of the parity of k. Each leaf within this tree corresponds to a complete assignment to a single partition subset P1 = 〈S1〉, and all remaining numbers are assigned to subsequent subsets P2 = 〈S2, S3, ..., Sk〉 through induction. Inclusion branches are always given precedence: whenever an element is assigned to the exclusion set S1, its inclusion in S1 has already been considered (and/or pruned) earlier in search.

Our algorithm also enforces self-imposed upper and lower bounds on the sum of the first subset in order to prune partial assignments that cannot possibly lead to improved solutions. Whenever ∑ S1 ≥ cbest, search may be aborted since the quality of the solution matches that of the best known partition. Furthermore, no better solution can possibly be found if ∑ S1 ≥ cbest ∗ (k - 1), and so in these cases search may be terminated as well. These bounds provide a powerful means to prune partial assignments, and they are employed by previous solvers.

4.2 Bounding Suboptimal Decompositions

Once a candidate subset is established for P1 = 〈S1〉, a recursive call is invoked to resolve the subproblem P2 = 〈S2, S3, ..., Sk〉. According to the classical principle of optimality, there exists some optimal solution to one of these decompositions that produces an optimal solution to the original problem.

However, previous examples have demonstrated that optimal solutions may exist that do not require strict optimality within the decomposition. Suboptimal solutions are generally easier to obtain [Thayer and Ruml, 2011], although they must still meet a minimum bar of quality in order to extend to globally optimal results. Theorem 2 tells us that for any [k1, k2]- decomposition to an optimal partition P, it must be the case that max(P1) ≤ opt(P). Although opt(P) is unknown, we can rest assured that if a solution to P2 happens to be found such that max(P2) ≤ max(P1), it must also be the case that max(P2) ≤ opt(P) (satisfying the property of global optimality). Furthermore, if some solution Sbest = 〈P ′1 · P ′2 〉 has already been found at the highest level with cost cbest, any solution (optimal or otherwise) to P2 where max(P2) ≥ cbest is clearly fruitless; any such decomposition would be incapable of improving upon the global objective function.

In order to limit the search performed by child solvers for P2 and its descendants, we pass the parameters 〈cmin, cmax〉 = 〈max(P1), cbest〉. Partial assignments are abandoned whenever ∑ Si ≥ cmax or ∑ Si ≥ cmax∗(k-i). Furthermore, a complete solution S will be returned whenever ∑ Si ≤ cmin for all i ≤ k. Note that these are distinct from the self-imposed upper and lower bounds, since they are determined by criteria computed by parent solvers. The reasoning behind these extensions should be intuitive, as they extend directly from the weakest-link nature of the partitioning objective function: a decomposition cannot be redeemed if its cost exceeds that of solutions encountered at higher levels, yet it receives no extra credit for obtaining sums below its neighboring partitions.

A'

B'

Figure 3: Extending partial assignment A to A′ supports a globally optimal solution. Partial assignment B′ supports a semi-optimal solution, but cannot improve the global result.

Example: Consider the 4-way partitioning instance containing the numbers {1, 2, ..., 9}. A decomposition that assigns S1 = {9, 3} will impose the directive cmin = 12 when partitioning the remaining numbers among the subsets {S2, S3, S4}. For this subproblem, the partial assignment A = 〈S2〉 = 〈{8, 4}〉 extends to a complete assignment A′ which satisfies this criterion (see Figure 3). An algorithm that requires strict semi-optimal decompositions must continue to exhaustively enumerate additional assignments, such as B = 〈S2〉 = 〈{8, 2, 1}〉. These attempts may succeed in improving the local cost of the subproblem (e.g., assignment B′ achieves a locally optimal cost of 11), but they cannot improve the cost of the global solution. Hence, our algorithm prunes B entirely and returns A′ to the topmost level. □

4.3 Dominance Detection and Elimination

The previous section employed tighter bounding criteria to prune partial assignments. In this section, we introduce a different form of pruning, in which dominated solutions (i.e., solutions that are cost-preserving transmutations of earlier assignments) are detected and eliminated from search. Set dominance techniques have proven particularly effective in related studies of bin packing [Korf, 2003] and bin completion [Fukunaga and Korf, 2005], in which bins are assigned a fixed (rather than variable) capacity.

Consider a partial assignment S = 〈S1, S1〉 and two subsequent extensions for the next number Si to be assigned:

• its inclusion branch S+ = 〈S+ 1 = S1 ∪ {Si}, S+ 1 〉
• its exclusion branch S- = 〈S1 , S1 = S1 ∪ {Si}〉

We assume that the branch for S+ has been taken, and that the alternate branch for S- is being considered.

Theorem 3: If ∑ S+ 1 < cmax, then in any complete solution Sc that extends S- where max(Sc ) < cmax, it must be the case that ∑ Sc 1 > ∑ S+ 1 . □

The above theorem makes a rather bold claim: after considering the inclusion of a number Si in a set whose sum is less than the upper bound, any subsequent extension to the set must strictly exceed that sum to obtain an improved solution.

Proof: Suppose by contradiction that there exists a solution Sc for which max(Sc ) < cmax and ∑ Sc 1 ≤ ∑ S+ 1 . The set of remaining numbers added to S1 in Sc are Sr 1 = Sc 1 -S1. Recall that Sc extends S-, therefore the number Si must be assigned to some subset Sc j where j > 1. We can construct

{S1:x-1}

{Sx:y-1}

{Sy:z-1}

{Sz:n}

Figure 4: Redundant search performed by RNP and IRNP. For any constants {x, y, z}, the subproblem {S1, ..., Sx} (along with three other subproblems illustrated) will be solved multiple times. This pattern repeats at all depths, and does not depend on subset contiguity.

a new solution S′ from Sc by exchanging contents between two of the subsets:

In the above construction, element Si is essentially swapped with all the numbers that were appended to S1 in forming Sc 1 . Since ∑ Sc 1 ≤ ∑ S+ 1 , it must be the case that ∑(Sc 1 -S1) ≤ ∑(S+ 1 - S1), which is equivalent to ∑ Sr 1 ≤ Si. This implies that ∑ S′j ≤ ∑ Sc j , i.e., the sum of subset j does not increase in our new solution. In contrast, the sum of the first subset may potentially increase: ∑ S′1 ≥ ∑ Sc 1 . However, note that S′1 is simply equal to S+ 1 , and therefore we are guaranteed that ∑ S′1 < cmax. No other subsets have been modified, so we conclude that max(S′ ) < cmax. However, since S′ is an extension of S+, it has already been discovered in the inclusion branch, implying that max(S′ ) ≥ cmax. These results are inconsistent, and therefore Sc cannot exist. □

Through similar reasoning, we can also prune leaf nodes (that is, any assignment where all numbers have been assigned to either S1 or S1) in which there exists a number Si ∈ S1 such that Si + ∑ S1 ≤ cmin. Although dominance detection is sound for any variable ordering strategy, it clearly benefits from a descending sort of the numbers in S, since individual numbers smaller than Si will be pruned unless they are combined with others.

4.4 Pruning Symmetric Solutions

For every solution P = 〈S1, S2, ..., Sk〉, there are k! equivalent symmetric solutions that can be obtained by permuting the relative ordering of subsets. Many of these isomorphic assignments can be eliminated by artificially imposing a total ordering over subsets. Recent works have achieved this by requiring subset sums to be non-decreasing, such that ∑ Sj ≤ ∑ Sj ′ for any j < j ′ . Unfortunately, such a policy defers the construction of the most influential subset (i.e., the one with maximal sum) and severely limits opportunities for pruning. We instead adopt a variation of a technique originally developed for CGA, in which a number is never assigned to more than one empty subset. This is accomplished

Figure 5: A mixed-integer program for number partitioning

by pruning the exclusion branch for the largest number in any subproblem solver. If the numbers are stored in decreasing order, the number S1 will be forced into subset S1, S2 will be assigned to subset S2 (assuming it is excluded from S1), and so on.

4.5 Comparison to IRNP

Our overall approach relies on fast computation of bounded suboptimal solutions to subproblems, eliminates partial assignments that are provably dominated by those considered earlier in search, and employs stronger techniques for symmetry breaking; these are the primary advantages over IRNP, the best multi-way number partitioner in the literature [Korf, 2011]. A secondary advantage is that our memory requirements are linear rather than exponential, since ESS is not used to generate subset sums. Our tighter bounding criteria could potentially be extended to the subset enumeration techniques within IRNP, although it considers candidates out-oforder and therefore cannot easily adopt our implementation of dominance detection. For small to medium values of n, the top-level of IRNP simply calls the old CGA solver, which is better equipped to optimize a large number of small partitions. In contrast, we do not use CGA for these settings since our algorithm is substantially faster.

5 Experimental Results

To determine the efficacy of our approach, we compare our algorithm to the latest results on optimal multi-way number partitioning as reported in [Korf, 2011]. Our solver is implemented in less than one hundred lines of C++ code and executed on a 3.47GHz Intel Xeon Processor. We consider the largest suite of benchmarks in the literature where k ranges from 7 to 10, and n is varied between 20 and 40. In each benchmark, n random numbers are generated uniformly in the range [0, 231 - 1]. For every setting of k and n, runtimes are averaged over a set of one hundred instances.

Table 1 provides the results of these experiments. Our solver dramatically outperforms IRNP on all test cases; furthermore, the runtime gap between the two algorithms consistently widens with increased k. At the highest setting of k = 10, our approach demonstrates an improvement of up to three or even four orders of magnitude. For the largest set of problems solved by both algorithms, IRNP requires nearly two hours on average, whereas the runtime of our solver remains well under one second.

Perhaps most surprising is that the performance of our algorithm scales almost independently of k. Recall that while k increases the set of available partitions for a number, it also reduces both the effective capacity for each partition in any optimal solution and (consequently) the number of viable subset combinations. Since only the arrangement of numbers within this area is ultimately affected, problems with higher k are not necessarily harder. Because our tighter pruning criteria propagate upper and lower bounds between nested decompositions, our algorithm tends to perform well under these conditions. We performed additional experiments with higher values of n, and found that problems with up to 56 numbers can be solved in roughly 100 minutes or less, regardless of k. This appears to be the largest problem size we can solve within a two-hour time limit, and is well beyond the capabilities of published works.

Several additional techniques were considered to further improve the performance of our approach, but most were found to be subsumed by the aforementioned innovations. One of these was memoization, a simple and well-known method that caches results of subproblems to avoid needless recomputation. As shown in Figure 4, RNP and IRNP both appear to be highly susceptible to redundant search, since successive decompositions tend to share considerable overlap (forcing solvers at lower levels to optimize identical subsets multiple times). To remedy this, solutions to intermediate problems can be stored and subsequently retrieved by using subset contents as the index into a hash table or prefix tree. However, we observed that when our bounding criteria and dominance techniques were both enabled, this enhancement rarely removed duplicate nodes, and often performed slower due to the bookkeeping of intermediate results and memory overhead.

We also explored solving strategies that rely on mixedinteger programming (MIP), a powerful and widely popular optimization paradigm that (to our knowledge) has never before been considered in prior works on number partitioning. The MIP encoding in Figure 5 creates a binary indicator variable vij for every number-partition pair, constraining each number to be assigned to exactly one partition. We used CPLEX to solve this formulation, but found that its performance came nowhere near the speed of the previous stateof-the-art. An additional complication is that CPLEX cannot ensure optimality for our benchmarks due to precision limitations: even in the 64-bit version, values and bounds on integer variables (including the objective cmax) must not exceed 231 - 1, and continuous variables are modeled by floatingpoint types which are subject to roundoff error. Nevertheless, improved MIP encodings may be viable for test cases requiring lower precision, and is a topic worthy of continued study.

6 Conclusions

We have proposed a new approach to multi-way number partitioning, one that produces optimal results despite relying on the solutions of potentially suboptimal decompositions. To achieve this, we have exploited a specific property of the objective function to develop a principle of weakest-link optimality. We have used this principle to strengthen the relationship between sequential decompositions by enforcing tighter bounds on partial assignments, and also to detect and remove dominated solutions from consideration. The efficiency of our algorithm is extremely competitive, outperforming the previous state-of-the-art by orders of magnitude and reducing average runtime on the largest benchmarks from several hours to less than a second.