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, \dots, a_n$ into two disjoint subsets such that the difference between the two subset sums -- the {\em discrepancy}, $\triangle$, is minimized. In the balanced version of NPP ({\sc BalNPP}), the subsets have the same cardinality. With $a_j$s chosen randomly from $[1,R]$, $R > 2^n$ gives the {\em hard} phase, when there are no equal partitions, and the minimum partition is unique, with high probability. We propose reductions of NPP and {\sc BalNPP} in the hard phase to instances of the closest vector problem (CVP). We can solve the original problems by making polynomial numbers of calls to a CVP oracle. In practice, we apply basis reduction (BR) to several CVP instances ($O(n)$ in general, $4n$ in most cases) to solve NPP problems with reasonably large dimensions. Second, we propose a direct mixed integer programming (MIP) model for NPP and {\sc BalNPP}. We then solve a lattice-based reformulation of the original MIP using branch-and-cut methods. Assuming it terminates, the MIP model is guaranteed to find the optimum partition. Third, we propose a {\em truncated} NPP algorithm, which finds approximate minimum discrepancies for instances well into the hard phase. In place of the original instance, we solve a modified instance with $\bar{a}_j = \lfloor a_j / T \rceil$ for some $T \leq R$. We show that the discrepancy of the original problem given by the truncated solution, $\triangle_T$, is not much different from the expected optimal discrepancy: $\triangle_T \leq \triangle^* + nT/2$.

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: 07/19/2009

Modify/Update this entry