An exact algorithm for the three-dimensional bin packing problem
================================================================

The code consists of two parts:

  3dbpp.c    : The callable C-code which solves a three-dimensional
               bin packing problem.

  test3dbpp.c: A main algorithm which either reads input from a file
               or generates 10 instances of a given size/type, and 
               calls 3dbpp.c for the solution. 

To compile the code use one of the following commands

  gcc -ansi -o 3dbpp -O5 3dbpp.c test3dbpp.c -lm  (gnu C)
  cc  -Aa   -o 3dbpp +O4 3dbpp.c test3dbpp.c -lm  (HP-UX C)

The generated executable file "3dbpp" can either read an instance from 
a file or randomly generate 10 instances.

If the instance is read from a file, five arguments should be given:
  filename  A filename in which the test instance is found. The format 
            of the file is:
               n W H D
               w_1 h_1 d_1
               :
               w_n h_n d_n
            where 
               n is the number of items, 
               W,H,D is the size of the bin, and 
               w_j,h_j,d_j is the size of box j.
  nodelimit maximum number of decision nodes to be explored in the
            main branching tree. If set to zero, the algorithm will
            run until an optimal solution is found (or timelimit or
            iterlimit is reached). Measured in thousands (see IUNIT).
  iterlimit maximum number of iterations in the ONEBIN algorithm
            which packs a single bin. If set to zero, the algorithm will
            run until an optimal solution is found (or timelimit or
            nodelimit is reached). Measured in thousands (see IUNIT).
  timelimit Time limit for solving the problem expressed in seconds.
            If set to zero, the algorithm will run until an optimal
            solution is found; otherwise it terminates after timelimit
            seconds with a heuristic solution. 
  packingtype 
            Desired packing type. If set to zero, the algorithm will
            search for an optimal general packing; if set to one, it
            will search for a robot packing.
            will search for a robot packing.
If the code should randomly generate 10 instances, seven arguments 
should be given:
  n         The size of the instance, i.e., number of boxes.
  bindim    The size of the bin, typically 40-100.
  type      An integer saying which randomly generated instance should
            be generated. A value between 1-9 selects one of the instance 
            types described in the above papers. Value 10-11 generates
            1D and 2D instances.
  nodelimit as above
  iterlimit as above
  timelimit as above
  packingtype
            as above

Results are written to standard output. Thus for instance choosing n=30, 
bindim=100, type=1, nodelimit=0, iterlimit=0, timelimit=0, packingtype=1 
one should get the following output:

3DBPP PROBLEM 30 100 1 0 0 0 1
 1 : lb  9 z  9 node         0 iter         3 time   0.00
 2 : lb 11 z 11 node        41 iter       438 time   0.32
 3 : lb  8 z  8 node       239 iter     12392 time  12.79
 4 : lb  7 z  7 node         0 iter       978 time   1.14
 5 : lb 10 z 10 node      2194 iter     91653 time  79.18
 6 : lb  7 z  7 node         0 iter         2 time   0.00
 7 : lb  8 z  8 node      1716 iter     30606 time  32.02
 8 : lb  9 z  9 node         0 iter         6 time   0.00
 9 : lb  9 z  9 node         0 iter        38 time   0.02
10 : lb  8 z  8 node         5 iter       393 time   0.27
as well as some average values on the above values.

"lb" is the lower bound, "z" is the objective of the found solution,
"node" is the number of branch-and-bound nodes in thousands, and
"iter" is the number of iterations in the ONEBIN algorithm in thousands,
and "time" is the CPU-time used for solving the problem.

(c) Copyright 1998, 2003, 2006

  David Pisinger                        Silvano Martello, Daniele Vigo
  DIKU, University of Copenhagen        DEIS, University of Bologna
  Universitetsparken 1                  Viale Risorgimento 2
  Copenhagen, Denmark                   Bologna, Italy

This code can be used free of charge for research and academic purposes 
only.