Technical Report: DCC-2008-03

Heuristics and Exact Methods for Number Partitioning

João P. Pedroso and Mikio Kubo

DCC-FC, Universidade do Porto
R. do Campo Alegre 1021/1055 , 4169-007 Porto, Portugal
Phone: +351 220402919 , Fax: 351 22 402 950
E-mail: jpp@fc.up.pt

February 2008

Abstract

Number partitioning is a classical NP-hard combinatorial optimization problem, whose so- lution is challenging for both exact and approximative methods. This work presents a new algorithm for number partitioning, based on ideas drawn from branch-and-bound, breadth first search, and beam search. A new set of benchmark instances for this problem is also proposed. The behavior of the new method on this and other test beds is analyzed and compared to other well known heuristics and exact algorithms.