Tree search for the Number Partitioning Problem
                ===============================================

Author: Joao Pedro Pedroso and Mikio Kubo < >
Date: 2009/01/09 10:57:04


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).

Files were generated with [npp_mk_inst.py], using:\\
Python 2.4.4 (#2, Jan  3 2008, 13:36:28) \\
[GCC 4.2.3 20071123 (prerelease) (Debian 4.2.2-4)] on linux2


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