Tree search for the Number Partitioning Problem

This directory contains data and programs for the number partitioning problem (NPP), as described in "Heuristics and Exact Methods for Number Partitioning", J.P.Pedroso and M.Kubo

Table of Contents

• 1 BENCHMARK INSTANCES
• 2 PROGRAM FILES
• 3 OUTPUT OF COMPUTATIONAL EXPERIMENT

1 BENCHMARK INSTANCES

• easy.zip - contains easy*.dat instances: random data with under-critical number of bits.
• hard.zip - contains hard*.dat instances: random data with over-critical number of bits.

  Notice that most of the numbers do not fit in a 32 or 64 bit integer.

• D.zip - contains files for decimal instances nNNNdDDeXX.dat, were each number corresponds to DD digits drawn uniformely from {0,...9}; instances have NNN elements. For each pair NNN,DD there are 10 independent instance (XX digits).

2 PROGRAM FILES

• npp.py heuristics for the NPP
• npp_dfs.py tree search, based on depth-first search
• npp_bfs.py tree search, based on breadth-first search
• graphtools.py auxiliary file (generic tools for dealing with graphs)
• npp_run_dfs.py run complete experiment with depth-first search
• npp_run_bfs.py run complete experiment with breadth-first search
• npp_mk_inst.py program used to produce the instance files

3 OUTPUT OF COMPUTATIONAL EXPERIMENT

• npp_bfs.csv main results for breadth-first
• npp_bfs.log standard output log for breadth-first
• npp_dfs.csv main results for breadth-first
• npp_dfs.log standard output log for breadth-first
• npp_dfs_interrupted.log standard output log for the interrupted runs with breadth-first

Author: Joao Pedro Pedroso and Mikio Kubo < >

Date: 2009/01/09 10:34:21