head.h

3DBPP BRANCH AND BOUND

}

/* **********************************************************************
   **********************************************************************
			      Lower Bounds
   **********************************************************************
   ********************************************************************** */

/* ======================================================================
			      bound_zero
   ====================================================================== */

/* The continuous bound L_0 */

double bound_zero(solution *a, item *f, item *l)
{
  item *i, *m;
  double sum, lb;
  sum = 0;
  for (i = f, m = l+1; i != m; i++){
	  sum =  i->vol + sum;
  }
//  cout << sum << endl;
//  cout << a->BVOL<<endl;
  lb = sum / (double) a->BVOL;
  return lb;
}


/* ======================================================================
                               rotate_solution
   ====================================================================== */

/* rotates the solution. After 3 rotations we return to original problem */

void rotate_solution(solution *a, item *f, item *l)

{
  register item *i, *m;
  register double w, x;

  for (i = f, m = l+1; i != m; i++) {
    w = i->w; i->w = i->h; i->h = i->d; i->d = w;
    x = i->x; i->x = i->y; i->y = i->z; i->z = x;
  }
}


/* ======================================================================
			       rotate_problem
   ====================================================================== */

/* rotates the dimensions by one step */

void rotate_problem(solution *a, item *f, item *l)
{
  register item *i, *m;
  register double w, x;

  for (i = f, m = l+1; i != m; i++) {
    w = i->w; i->w = i->h; i->h = i->d; i->d = w;
    x = i->x; i->x = i->y; i->y = i->z; i->z = x;
  }
  w = a->W; a->W = a->H; a->H = a->D; a->D = w;
}

/* ======================================================================
			       choose_items
   ====================================================================== */

/* returns a set of items with w > W2 and d > D2. This set is used in */
/* bound_one */ 

// 本函数用以返回 w > W2 and d > D2 的item

void choose_items(solution *a, item *f, item *l, double W2, double D2, 
		  item *fitem, item **litem)
{
  item *i, *k, *m;

  for (i = f, m = l+1, k = fitem; i != m; i++) {
//	  cout<< i->w << " " << i->d << endl;
	  if ((i->w > W2) && (i->d > D2)) { 
		  *k = *i; k++; }
  }
  *litem = k-1;
}


/* ======================================================================
			       find_plist
   ====================================================================== */

/* returns a zero-terimanted list of distinct dimensions */

void find_plist(item *fitem, item *litem, double M, int dim, double *pl)
{
  register item *i, *m;
  register double *k, *j, *l;

  i = fitem; m = litem+1; k = pl;
  switch (dim) {
    case WDIM: for (; i != m; i++) {
		 if (i->w <= M) { *k = i->w; k++; } 
	       } break;
    case HDIM: for (; i != m; i++) {
		 if (i->h <= M) { *k = i->h; k++; } 
	       } break;
    case DDIM: for (; i != m; i++) {
		 if (i->d <= M) { *k = i->d; k++; } 
	       } break;
  }
  if (k == pl) { *k = 0; return; }
  isortincr(pl, k-1);  /* sort the dimensions */ //以上升序列进行单个维度的排序
  for (j = pl+1, l = pl; j != k; j++) { /* remove duplicates */
    if (*j != *l) { l++; *l = *j; } 
  }
  l++; *l = 0;
}


/* ======================================================================
			       bound_one
   ====================================================================== */

/* Derive bound L_1 for a fixed dimension */

double bound_one_x(solution *a, item *f, item *l){
  item *i, *m;
  double H, H2, h;
  double p, j1, j2, j3, j2h, j2hp, j3h;
  double *pp, lb, lb_one, alpha, beta;;
  item *fitem, *litem;
  fitem = new item[MAXITEMS];
  double plist[MAXITEMS];
  if (l == f-1) return 0;
  lb = 0; H = a->H; H2 = H/2;
//  cout << f->w << endl;
  choose_items(a, f, l, a->W/2, a->D/2, fitem, &litem);
  if (litem == fitem-1) { /* empty */return lb; }
  find_plist(a->fitem, a->litem, H2, HDIM, plist);
  for (pp = plist; *pp != 0; pp++) {
    p = *pp;
//	cout << "p:  " <<p<<endl;
	j1 = j2 = j3 = j2h = j2hp = j3h = 0;
    for (i = fitem, m = litem+1; i != m; i++) {
      h = i->h; 
//	  cout << "h " << h <<endl; 
      if (h > H-p) j1++;
      if ((H-p >= h) && (h > H2)) { j2++; j2h += h; j2hp += floor((H-h)/p); }
      if ((H2 >= h) && (h >= p)) { j3++; j3h += h; }
    }
    alpha = ceil((j3h - (j2 * H - j2h)) / H);
//	cout << alpha << endl;
    beta  = ceil((j3 - j2hp) / floor((H/p)));
//  cout << beta << endl;
	if (alpha < 0) alpha = 0;
    if (beta  < 0) beta  = 0;
    lb_one = j1 + j2 + MAXIMUM(alpha, beta);
//	cout << "bound one: " << lb_one <<endl;
    if (lb_one > lb) lb = lb_one;
  }
  return lb;
}

/* Derive bound L_1 as the best of all L_1 bounds for three rotations */

double bound_one(solution *a, item *f, item *l)
{
  int i;
  double lb, lbx;

  lb = 0;
  for (i = WDIM; i <= DDIM; i++) {
    lbx = bound_one_x(a, f, l);
    if (lbx > lb) lb = lbx; 
    rotate_problem(a, f, l);
  } 
  return lb;
}

/* ======================================================================
			       bound_two
   ====================================================================== */

/* Derive bound L_2 for a fixed dimension */

double bound_two_x(solution *a, item *f, item *l)
{
  register item *i, *m;
  register double W, H, D, w, h, d, W2, D2;
  register double p, q, k1h, k23v;
  double hlb1, lb, lb1, lbx, fract;
  double plist[MAXITEMS], qlist[MAXITEMS];
  double *qq, *pp;
  double WD, BVOL;

  /* derive bound_one */
  lb = lb1 = bound_one_x(a, f, l);
  W = a->W; H = a->H; D = a->D; hlb1 = H * lb1; 
  W2 = W/2; D2 = D/2; WD = W*D; BVOL = a->BVOL;

  /* run through all values of p, q */
  find_plist(f, l, W2, WDIM, plist);
  find_plist(f, l, D2, DDIM, qlist);
  for (pp = plist; *pp != 0; pp++) {
    p = *pp;
    for (qq = qlist; *qq != 0; qq++) {
      q = *qq;
      k1h = k23v = 0;
      for (i = f, m = l+1; i != m; i++) {
	w = i->w; h = i->h; d = i->d;
	if ((w > W - p) && (d > D - q)) { k1h += h; continue; }
	if ((w >= p) && (d >= q)) { k23v += i->vol; }
      }
      fract = ceil((k23v - (hlb1 - k1h)*WD) / BVOL);
      if (fract < 0) fract = 0;
      lbx = lb1 + fract;
      if (lbx > lb) lb = lbx;
    }
  }
  return lb;
}


/* Derive bound L_2 as the best of all L_2 bounds for three rotations */

double bound_two(solution *a, item *f, item *l)
{
  int i;
  double lb, lbx;
  lb = 0;
  for (i = WDIM; i <= DDIM; i++) {
    lbx = bound_two_x(a, f, l);
    if (lbx > lb) lb = lbx;
    rotate_problem(a, f, l);
  } 
  return lb;
}

/* **********************************************************************
   **********************************************************************
			    heuristic filling
   **********************************************************************
   ********************************************************************** */

/* ======================================================================
			      onelayer
   ====================================================================== */

/* Fill a layer of depth f->d by arranging the items in a number of */
/* vertical shelfs. The items $i$ packed are assigned coordinates */
/* (i->x, i->y) and the field i->k is set to the argument d (layer no). */

double onelayer(solution *a, item *f, item *l, double d)
{
  int n , t;
  double r; /* remaining width */
  double depth; // mark depth
  double width, height, x;
  item *i, *j, *markstart, *markend;
  markstart = f;
  n = DIF(f,l)+1;
  width = height = x = depth = 0;
  //  qsort(f, DIF(f,m), sizeof(item), (funcptr) hcomp);
  r = a->W;
  for ( i = f ; i != l+1 ; i++ ){
//	  cout << " item no "<< i->no << endl;
	  if ( i->w > r )
		  break;
	  if ( i->w < r ){
		  if ( height + i->h <= a->H ){
			  if ( i == l ){
				  height = 0;
				  markend = i;
				  qsort (markstart,DIF(markstart,markend),sizeof(item),(funcptr)wcomp);
				  for ( j = markstart; j != markend + 1; j++ ){
					  if (j->d > depth) depth = j->d;
			          j->x = x;
			          j->y = height ;
				      j->z = d;
				      j->k = 1;
				      height = height + j->h;
//				      cout <<j->no<<" "<<j->x<<" "<<j->y<<" "<<j->z<<" customer "<< j->customer<< endl;
				  }
			  }
			  height += i->h;
		  }
		  else {
			  markend = i-1;
//			  cout << "markend "<< markend->no<< "height "<< height<<endl;
			  height = 0;
		      qsort (markstart,DIF(markstart,markend),sizeof(item),(funcptr)wcomp);
//			  for ( b = a->fitem ; b!= a->litem+1 ; b++){
//				  cout << b->customer << " " << b->no << " " << b->vol << endl;
//			  }
			  for ( j = markstart; j != markend + 1; j++ ){
				  if (j->d > depth) depth = j->d;
				  j->x = x;
			      j->y = height ;
				  j->z = d;
				  j->k = 1;
				  height = height + j->h;
//				  cout <<j->no<<" "<<j->x<<" "<<j->y<<" "<<j->z<<" customer "<< j->customer<< endl;
			  }
		      x = x + markstart->w;
		      markstart = i;
			  i = i - 1;
		      r = r - x;
			  if ( r>0 ) height = 0;
		  }
	  }
  }

//  for ( f = a->fitem, l = a->litem; f != l+1 ; f++ ){
//	  cout << f->k <<" "<<f->x<<" "<<f->y<<" "<<f->z << " " << f->customer << " " << f->no << endl;
//  }
//  cout <<" depth " << depth <<endl;
  return depth;
}

/* ======================================================================
				  countarea
   ====================================================================== */

/* Select a subset of the items such that the selected items have a total */
/* area of two times the face of a bin (the parameter: barea) */

item *countarea(item *f, item *l, double barea)
{
  item *i;
  double area, d;

  for (area = 0, i = f; i != l+1; i++) {
    d = i->h * i->w;
    area += d;
    if (area > 2*barea) return i-1;
  }
  return l;
}

/* ======================================================================
				  remitems
   ====================================================================== */

/* Remove the items which were chosen for a layer, i.e. where i->k != 0. */
/* The depth of the layer is set equal to the deepest box chosen. */

item *remitems(item *f, item *l)
{
  item *i, *j;
  for (i = f,j = f; j != l+1; ) {
    if (i->k) {
		i++; j++; 
	}
	if (!i->k)
		j++;
  }
  return i;