Lattice-based Algorithms for Number Partitioning in the Hard Phase

Bala Krishnamoorthy (bkrishnamath.wsu.edu)
William Webb (webbmath.wsu.edu)
Nathan Moyer (nmoyermath.wsu.edu)

Abstract: The number partitioning problem (NPP) is to divide n numbers a_1,...,a_n into two disjoint subsets such that the difference between the two subset sums - the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the hard phase, when there are no equal partitions (i.e., D=0) with high probability (whp). In this phase, the minimum partition is also unique whp. Most current methods struggle in the hard phase, as they often perform exhaustive enumeration of all partitions to find the optimum.

We propose reductions of NPP and BalNPP in the hard phase to the closest vector problem (CVP). We can solve the original problems by making polynomial numbers of calls to a CVP oracle. In practice, we implement a heuristic which applies basis reduction (BR) to several CVP instances (less than 2n in most cases). This method finds near-optimal solutions without proof of optimality to NPP problems with reasonably large dimensions - up to n=75. second, we propose a truncated NPP algorithm, which finds approximate minimum discrepancies for instances on which the BR approach is not effective. In place of the original instance, we solve a modified instance with a'_j = round(a_j / T) for some T <= R. We show that the expected optimal discrepancy of the original problem given by the truncated solution, D*_T, is not much different from the expected optimal discrepancy: E(D*_T) <= E(D*) + nT/2. This algorithm can be used to find good quality partitions within a short time for problems of sizes up to n=100. Third, we propose a direct mixed integer programming (MIP) model for NPP and BalNPP. We then solve a lattice-based reformulation of the original MIP using standard branch-and-cut methods. Assuming it terminates, the MIP model is guaranteed to find the optimum partition.

Keywords: Number partitioning, closest vector problem, basis reduction, integer programming

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (Other )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation:

Download: [PDF]

Entry Submitted: 10/15/2008
Entry Accepted: 10/17/2008
Entry Last Modified: 06/16/2010

Modify/Update this entry