head.h

3DBPP BRANCH AND BOUND

#define MAXITEMS      201    /* max number of items (plus one item) */
#define MAXBPP    1000000    /* max numer of iterations in 1-dim bpp */
#define MAXITER      1000    /* max number of iterations in fast onebin_fill */
#define MAXCLOSE       16    /* max level for which try_close is applied */

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
//#include <values.h>
#include <string.h>
#include <math.h>
#include <malloc.h>
#include <time.h>  
#include <limits.h>
#include <iostream.h>
#include <fstream.h>

/* ======================================================================
				   macros
   ====================================================================== */

#define TRUE  1           /* logical variables */
#define FALSE 0

#define WDIM  0           /* rotations of boxes */
#define HDIM  1
#define DDIM  2

#define VOL(i)            ((i)->w * (ptype) (i)->h * (i)->d)
#define MINIMUM(i,j)      ((i) < (j) ? (i) : (j))
#define MAXIMUM(i,j)      ((i) > (j) ? (i) : (j))
#define DIF(i,j)          ((int) ((j) - (i) + 1))
#define SWAPINT(a,b)      { register double t; t=*(a);*(a)=*(b);*(b)=t; }
#define SWAP(a,b)         { register item t; t=*(a);*(a)=*(b);*(b)=t; }
#define SWAPI(a,b)        { register itype t; t=(a);(a)=(b);(b)=t; }
#define SWAPP(a,b)        { register point t; t=*(a);*(a)=*(b);*(b)=t; }
#define DF(a,b)           ((r=(a).y-(b).y) != 0 ? r : (a).z-(b).z)


/* ======================================================================
				 type declarations
   ====================================================================== */

typedef short         boolean; /* logical variable      */
typedef short         ntype;   /* number of states,bins */
typedef short         itype;   /* can hold up to W,H,D  */
typedef long          stype;   /* can hold up to W*H*D  */
typedef long          ptype;   /* product multiplication */

/* item record */
typedef struct item
{
	short     no;           /* item number */
    double    w;            /* item width  (x-size) */
    double    h;            /* item height (y-size) */
    double    d;            /* item depth  (z-size) */
    double    x;            /* optimal x-position */
    double    y;            /* optimal y-position */
    double    z;            /* optimal z-position */
    short     k;            /* is the item chosen */
    long      vol;          /* volume of item */
    short     customer;     /* customer number*/
};

/* all problem information */
typedef struct solution
{
    double    W;            /* x-size of bin             */
    double    H;            /* y-size of bin             */
    double    D;            /* z-size of bin             */
    double    BVOL;         /* volume of a bin           */
    short     numitem;      /* number of items           */
    item      *fitem;       /* first item in problem     */
    item      *litem;       /* last item in problem      */
    item      *fsol;
    item      *lsol;
    item      *fopt;        /* first item in optimal solution */
    item      *lopt;        /* last item in optimal solution  */
    short     mindim;       /* currently smallest box length  */
    short     maxdim;       /* currently largest box length   */
    double    maxfill;      /* the best filling found         */
    int       mcut;         /* how many siblings at each node in b&b */
    short     optimal;      /* a solution which packs all found */
    short     numcustomer;  /* number of customers*/

    /* different bounds */
    ntype     z;            /* currently best solution */

    /* controle of 3d filler */
    long      maxiter;      /* max iterations in onebin_fill */
    long      miss;         /* number of items not packed in onebin_fill  */

  /* debugging and controle information */
    long      iterates;     /* iterations in branch-and-bound */
    long      iter3d;       /* iterations in onebin_fill */
    long      zmcut;        /* heuristic solution mcut */
};

/* structure for greedy algorithm */
typedef struct heurpair
{
    int      lno;          /* layer number */
    int      d;            /* depth of layer */
    int      bno;          /* bin no assigned to layer */
    int      z;            /* z level of layer within bin */
    int      b;            /* temporary bin number */
};

/* structure for extreme points in a single bin */
typedef struct point
{
    double    x;            // x-coordinate 
    double    y;            // y-coordinate 
    double    z;            // z-coordinate 
    item      *belong;      // belong to which item
    short     mark;         // decide whether it is before another item
};

/* pointer to comparison function */
typedef int (*funcptr) (const void *, const void *); 

/* ======================================================================
				  global variables
   ====================================================================== */

/* boolean variable to indicate time-out situation */
boolean stopped; 


/* maximum amount of time to be used */
int maxtime;

/* =======================================================================
				  error
   ======================================================================= */

void error(char *str, ...)
{
	va_list args;
	va_start(args, str);
    vprintf(str, args); printf("\n");
    va_end(args);
    printf("IRREGULAR PROGRAM TERMINATION\n");
    exit(-1);
}

double max(double a,double b,double c)
{
	double temp;
	if ( a>b ) temp = a;
	else temp = b;
	if ( temp < c ) temp = c;
	return temp;
}

/* **********************************************************************
   **********************************************************************
			     Timing routines 
   **********************************************************************
   ********************************************************************** */

/* This timing routine is based on the ANSI-C procedure "clock", which
 * has a resolution of 1000000 ticks per second. This however implies
 * that we pass the limit of a long integer after only 4295 seconds.
 * The following routine attempts to correct such situations by adding
 * the constant ULONG_MAX to the counter whenever wraparound can be
 * detected. But the user is advised to use a timing routine like "times"
 * (which however is not ANSI-C standard) for measuring longer time
 * periods.
 */

void timer(double *time)
{
	static double tstart, tend, tprev;

	if (time == NULL) {
		clock(); /* one extra call to initialize clock */
        tstart = tprev = clock();
	} 
	else {
		tend = clock(); 
        if (tend < tprev) tstart -= ULONG_MAX; /* wraparound occured */
        tprev = tend;
        *time = (tend-tstart) / CLOCKS_PER_SEC; /* convert to seconds */
	}
}

/* test for time limit */
void timelimit(long max)
{
  double t;
  if (max == 0) return;
  timer(&t); if (t >= max) stopped = TRUE; 
}



/* ======================================================================
			    simple comparisions
   ====================================================================== */

/* Comparisons used as argument to qsort. */
double wcomp(item *a, item *b)
{ double r; r = b->w - a->w; if (r != 0) return r; else return b->no = a->no; }
double dcomp(item *a, item *b) 
{ double r; r = b->d - a->d; if (r != 0) return r; else return b->no - a->no; }
double hcomp(item *a, item *b) 
{ double r; r = b->h - a->h; if (r != 0) return r; else return b->no - a->no; }
double vcomp(item *a, item *b) /* volume decr. */
{ double r; r = b->vol-a->vol; if (r != 0) return r; else return b->no - a->no; }
double xcomp(heurpair *a, heurpair *b) /* depth decr. */
{ double r; r = b->d - a->d; if (r != 0) return r; else return b->lno - a->lno; }
int lcomp(heurpair *a, heurpair *b) /* layer number decr. */
{ int r; r = a->lno-b->lno; if (r != 0) return r; else return b->d - a->d; }
int initial(item *a, item *b)
{ int r; r = b->customer - a->customer ; if (r!=0) return r;else return b->vol - a->vol;}
int initial1(item *a, item *b)
{ int r; r = b->customer - a->customer ; if (r!=0) return r;else return b->d - a->d;}
int initial2(item *a, item *b)
{ int r; r = b->customer - a->customer ; if (r!=0) return r;else return b->w - a->d;} 

/* ======================================================================
			     checksol
   ====================================================================== */

/* check correctnes of solution, i.e. no items overlap, no duplicated items */

void checksol(solution *a, item *f, item *l)
{
  item *i, *j, *m;

  for (i = f, m = l+1; i != m; i++) { 
    if (!i->k) continue;  /* item currently not chosen */
    for (j = f; j != m; j++) {
      if (i == j) continue;
      if (i->no == j->no) error("duplicated item %d\n", i->no); 
      if (!j->k) continue;
      if ((i->x + i->w > j->x) && (j->x + j->w > i->x) &&
	  (i->y + i->h > j->y) && (j->y + j->h > i->y) &&
	  (i->z + i->d > j->z) && (j->z + j->d > i->z)) {
	error("overlap item %d,%d: [%d,%d,%d] [%d,%d,%d]",
	      i->no, j->no, i->w, i->h, i->d, j->w, j->h, j->d);
      }
    }
  }
}

/* ======================================================================
			       savesol
   ====================================================================== */

/* save an updated solution, checking its validity */

void savesol(solution *a, item *f, item *l, ntype z)
{
  item *i, *j, *k, *m;

  /* first check validity */
  if (z >= a->z) error("not improved");

  /* now do the saving */
  a->z = z;
  for (i = f, k = a->fopt, m = l+1; i != m; i++, k++) *k = *i;
  for (i = a->fopt, m = a->lopt+1; i != m; i++) i->k = TRUE;
  if (DIF(a->fopt,k-1) != a->numitem) error("not correct amount of items");
  checksol(a, a->fopt, a->lopt);
}


/* ======================================================================
			       isortincr
   ====================================================================== */

/* A specialized routine for sorting integers in increasing order. */
/* qsort could be used equally well, but this routine is faster. */

void isortincr(double *f, double *l)
{
  register double mi;
  register double *i, *j, *m;
  register int d;

  d = l - f + 1;
  if (d < 1) error("negative interval in isortincr");
  if (d == 1) return;
  m = f + d / 2; if (*f > *m) SWAPINT(f, m);
  if (d > 2) { if (*m > *l) { SWAPINT(m, l); if (*f > *m) SWAPINT(f, m); } }
  if (d <= 3) return;
  mi = *m; i = f; j = l;
  for (;;) {
    do i++; while (*i < mi);
    do j--; while (*j > mi);
    if (i > j) break; else SWAPINT(i, j);
  }
  isortincr(f, i-1); isortincr(i, l);
}


/* ======================================================================
			       isortdecr
   ====================================================================== */

/* A specialized routine for sorting integers in decreasing order. */
/* qsort could be used equally well, but this routine is faster. */

void isortdecr(double *f, double *l)
{
  register double mi;
  register double *i, *j, *m;
  register int d;

  d = l - f + 1;
  if (d < 1) error("negative interval in isortdecr");
  if (d == 1) return;
  m = f + d / 2; if (*f < *m) SWAPINT(f, m);
  if (d > 2) { if (*m < *l) { SWAPINT(m, l); if (*f < *m) SWAPINT(f, m); } }
  if (d <= 3) return;
  mi = *m; i = f; j = l;
  for (;;) {
    do i++; while (*i > mi);
    do j--; while (*j < mi);
    if (i > j) break; else SWAPINT(i, j);
  }
  isortdecr(f, i-1); isortdecr(i, l);
}


/* ======================================================================
			       psortdecr
   ====================================================================== */

/* A specialized routine for sorting extreme points according to decreasing */
/* y-coordinate (decreasing x-coordinate in case of ties) */

void psortdecr(point *f, point *l)
{
  register point mi;
  register point *i, *j, *m;
  register int d;
  double r;

  d = l - f + 1; 
  if (d <= 1) return;
  m = f + d / 2; 
  if (DF(*f,*m) < 0) 
	  SWAPP(f,m); 
  if (d == 2) return;
  if (DF(*m,*l)<0) { 
	  SWAPP(m,l); 
	  if (DF(*f,*m)<0) 
		  SWAPP(f,m); }
  if (d <= 3) return;
  mi = *m; i = f; j = l;
  for (;;) {
    do i++; while (DF(*i,mi) > 0);
    do j--; while (DF(*j,mi) < 0);
    if (i > j) break; else SWAPP(i, j);
  }
  psortdecr(f, i-1); psortdecr(i, l);