Heuristics and exact methods for number partitioning |
| |
Authors: | João Pedro Pedroso Mikio Kubo |
| |
Institution: | 1. INESC Porto and Faculdade de Ciências, Universidade do Porto, 4169-007 Porto, Portugal;2. Tokyo University of Marine Science and Technology, 135-8533 Tokyo, Japan |
| |
Abstract: | Number partitioning is a classical NP-hard combinatorial optimization problem, whose solution is challenging for both exact and approximative methods. This work presents a new algorithm for number partitioning, based on ideas drawn from tree search, 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 testbeds is analyzed and compared to other well known heuristics and exact algorithms. |
| |
Keywords: | Number partitioning problem Tree search Heuristics Combinatorial optimization |
本文献已被 ScienceDirect 等数据库收录! |
|