A branch-and-bound algorithm for number partitioning

Question

I am working on a branch-and-bound algorithm for number partitioning, similar to Complete greedy algorithm. The input is a list of positive integers and an integer $k$; the output is a partitioning of the integers into $k$ bins, such that the smallest bin sum is as large as possible.

For the "bound" part, I want a function that takes as input a partial partition (a partition of the first $m$ integers) and the sum of the remaining integers, and returns an upper bound on the smallest sum. If this bound is not larger than the best solution found so far, then the branch can be pruned.

For example, suppose $k=3$, we have a partial partition with sums: $70, 90, 100$, and the sum of all remaining inputs is 30. Then, the upper bound is $95$, since in the best case, even if the remaining inputs are perfectly divisible, we would put $25$ in the first bin and $5$ in the second bin, so the best partition would be $95,95,100$.

I am looking for a fast algorithm to compute this upper bound. My current algorithm is as follows. Suppose we have a partial partition with sums $b_1\leq \ldots \leq b_k$, and the sum of remaining inputs is $s$. Then:

• If $b_1+s\leq b_2$, return $b_1+s$ (- put all remaining inputs in bin 1).
• Else, if $(b_1+b_2+s)/2 \leq b_3$, return $(b_1+b_2+s)/2$ (- divide all remaining inputs between bins 1 and 2 in a balanced way).
• Else, if $(b_1+b_2+b_3+s)/3 \leq b_4$, return $(b_1+b_2+b_3+s)/3$ ...
• Else, return $(b_1+\cdots+b_k)/k$.

Since the upper bound is calculated many times throughout the algorithm, I want the calculation to be as fast as possible.

QUESTION: Is there a faster way to compute this upper bound? I am looking both for improvements in runtime complexity (e.g. runtime that is sublinear in $k$), and for improvements in the constants.

Answer 1

The following contains two modest tweaks (cumulative sum, multiplying rather than dividing) to your algorithm that might speed it up slightly.

1. $\sigma \leftarrow b_1 + s$ (cumulative sum)

2. If $\sigma \le b_2$ return $\sigma$ else $\sigma \leftarrow \sigma + b_2$

3. For $j=2,\dots,k-1$ {

   If $\sigma \le j \cdot b_{j+1}$ return $\left\lfloor \frac{\sigma}{j}\right\rfloor $ else $\sigma \leftarrow \sigma + b_{j+1}$

   }

4. Return $\left\lfloor \frac{\sigma}{k}\right\rfloor $

Using a cumulative sum avoids repetitive additions. I'm pretty sure multiplying by $j$ is faster than dividing by $j$, and this way you do a maximum of one division.

I included the floor operator in case you are using a language in which the computations are floating point, but most likely you will be using integer arithmetic and the division will produce the correct result automatically.

Answer 2

If k is relatively large, rather than iterating through the possibilities one at a time, it might be faster to double the index of the test case each iteration, and then do a binary search between the two last found points that are too small and too large.