head.h

3DBPP BRANCH AND BOUND

}

/* ======================================================================
			      dfirst_heuristic
   ====================================================================== */

/* Heuristic algorithm for the 3D BPP. A number of layers are constructed */
/* using the shelf approach to pack every layer. Then the individual layers */
/* are combined to bins by solving a 1D BPP defined in the layer depths. */

double dfirst_heuristic(solution *a)
{
  item *j, *f, *l, *m;
  int n;
  double d , z , upperbound, rate,vol;
  z = d = 0;
  /* initialize items */
  for (j = a->fitem, m = a->litem+1,vol = 0; j != m; j++) {
    j->x = j->y = j->z = 0; j->k = 0;
	vol = vol + j->vol;
  }
  n = DIF(a->fitem,a->litem); 
  f = a->fitem;
  l = a->litem;
  qsort(f, n, sizeof(item), (funcptr) initial);
  /* fill layer one by one */
  for (; f !=  l+1; ) {
    cout << "mark "<< z <<endl;
    m = countarea(f, l, a->W * a->H);
    d = onelayer(a, f, m, z);
    f = remitems(f, l);
	z = z + d;
  }

/* now assign bin number to each items */
//  assignitems(t, t+h-1, z, a->fitem, a->litem);
//  if (z < a->zlayer) a->zlayer = z;
//  if (a->zlayer < a->z) savesol(a, a->fitem, a->litem, a->zlayer);
  return z;
}

/* **********************************************************************
   **********************************************************************
			     fill one 3D bin
   **********************************************************************
   ********************************************************************** */

/* ======================================================================
			     initboxes
   ====================================================================== */

/* Initialize boxes. Already placed boxes define extreme points, and thus */
/* they are placed into the list fc,..,lc. Not placed boxes are used to */
/* derive minimum dimensions. */

// 对于已经pack的盒子就定义其极点，并将其存入队列fc,..,lc。对于没有pack的盒子
// 就获得最小的维度，即每个维度上的最小长度。

void initboxes(solution *a, item *f, item *l, point *fc, point **lc, 
               double *minw, double *minh, double *mind)
{
  item *j, *m;
  point *k;
  double minx, miny, minz;

  minx = *minw; miny = *minh; minz = *mind; 
  for (j = f, k = fc, m = l+1; j != m; j++) {
	if (j->k) { /* defines an extreme box */
      k->x = j->x+j->w; 
	  k->y = j->y+j->h; 
	  k->z = j->z+j->d;
      k->belong = j;
	  k++;
    } 
	else { /* free box */
      if (j->w < minx) minx = j->w;
      if (j->h < miny) miny = j->h;
      if (j->d < minz) minz = j->d;
    }
  }
  *minw = minx; *minh = miny; *mind = minz; 
  if (*minw == a->W) *minw = 0;
  if (*minh == a->H) *minh = 0;
  if (*mind == a->D) *mind = 0;
  *lc = k-1;
/*  if (*lc == fc-1){
	  *lc = fc;
	  fc->x = 0;
	  fc->y = 0;
	  fc->z = a->D + 1;
  }*/
}

/* ======================================================================
				envelope
   ====================================================================== */

/* Find the two-dimensional envelope of the boxes given by extreme */
/* points f to l. */

// 对于由initbox产生出来的极点f,..,l，从中选出2D的corner points，并存于s1,..,*sm，
// cz用以标明当前的depth，ll用以标明当前所处理到的极点，nz用以标明当前最小depth，
// *area用以记录当前层所有面积的和

void envelope(point *f, point *l, point *s1, point **sm,double W, double H, 
			  double D, double RD, double RH, double cx, point **ll, double *nz, double *area)
{
	register point *i, *s, *t,*mark;
    register double z, zz, y, x, ix, iy, iz, mx;
    register double sum;
  
    /* find corner points and area */
    z = zz = x = 0; y = H; sum = 0; mx = W;
    mark = NULL;

    for (i = t = f, s = s1; i != l; i++) {
 //   cout<<"gg"<<i->x<<" "<<i->y<<" "<<i->z<<endl;
		ix = i->x; if (ix <= cx) continue;
        if (ix < mx) 
		mx = ix; /* find minimum next x coordinate */
        iz = i->z; 
	    if (iz <= z) { // 此判断为将不是本层应该处理的盒子留给以后处理
			if (ix > x) { *t = *i; t++; } 
            continue;
		}
        iy = i->y;
	    s->x = cx; s->y = iy; s->z = z;
	    if(mark == NULL){
			s->belong = i->belong;
		    s->mark = FALSE;
		}
	    if(mark != NULL){
	        s->belong = mark->belong;
		    s->mark = TRUE;
		} 
        s++;
	    mark = i;
	    sum += (z - zz) * (ptype) y; 
	    y = iy; zz = z;	
	    x = ix; z = iz; *t = *i; t++;
	}
    if (y != 0) sum += (D - zz) * (ptype) y;
    *sm = s-1;
    *area = sum;
//  cout<< "mz1: "<<mz<<endl;
    *nz = mx;
    *ll = t-1;
}

/* ======================================================================
			     checkdom
   ====================================================================== */

/* The 3D envelope is found by deriving a number of 2D envelopes. This */
/* may however introduce some "false" corner points, which are marked */
/* by the following algorithm. */

void checkdom(point *s1, point *sl, point *sm)
{
  register point *s, *t, *u;

  if (sl == s1-1) return;
  for (s = s1, t = sl+1, u = sm+1; t != u; t++) {
    while (s->z < t->z) { s++; if (s > sl) return; }
    if ((s->z == t->z) && (s->y == t->y)) t->x = 0;
  } 
}

/* ======================================================================
			     removedom
   ====================================================================== */

/* Remove "false" corner points marked by algorithm "checkdom". */

point *removedom(point *s1, point *sl)
{
  register point *i, *m, *k;
  register int pz;
 
  for (i = k = s1, m = sl+1, pz = 0; i != m; i++) {
    if (i->x == 0) continue; 
    *k = *i; k++; 
  }
  return k-1;
}

/* ======================================================================
			      findplaces
   ====================================================================== */

/* Find all corner points, where a new box may be placed as well as the */
/* volume of the "envelope" occupied by already placed boxes. Already */
/* placed boxes are given by f,..,l, while a list of possible placings */
/* is returned in s1,..,sm. The return value of the procedure is an upper */
/* bound on the possible filling of this bin. */

// 在pack入一个新盒子后找出所有corner points同时找出这些盒子所构成的envelope的体积。
// 已经pack入的盒子存于队列f,..,l,所有寻找的corner points存于s1,..,sm。最后返回可能
// pack入盒子的最大体积。

double findplaces(solution *a, item *f, item *l, point *s1, point **sm, double fill)
{
  register point *k;
  double minw, minh, mind, W, H, D, RZ, RH, x, xn;
  point *sk, *lc, *sl, *st, *s0;
  double sum, area, bound;
  bound = 0;
  point fc[MAXITEMS+1];
  /* select items which are chosen, and find min dimensions of unchosen */
  minw = W = a->W; minh = H = a->H; mind = D = a->D; 
  initboxes(a, f, l, fc, &lc, &minw, &minh, &mind); 
  // fc,..,lc存放已pack入箱子所有盒子的极点
  // minw,minh,mind存放没有pack入箱子的盒子的各维度的最小值
  /* sort the boxes according to max y (first) max z (second) */
  if (lc >= fc) psortdecr(fc, lc); /* order decreasing */
  /* for each z-coordinate find the 2D envelope */
  sum = 0; sl = s1-1; sk = s1;
  RZ = D - mind; RH = H - minh;
  lc++; k = lc; k->x = W+1; k->y = 0; k->z = a->D+1;k->belong = f;k->mark = FALSE;
  for (x = 0; x != W; x = xn) {
    /* find 2D envelope for all boxes which cover *y */
    envelope(fc, lc+1, sl+1, &st, W, H, D, RZ, RH, x, &lc, &xn, &area);
    if (xn + minw > W) xn = W; /* nothing fits between zn and D */
	sum += area * (ptype) (xn - x); /* update volume */
    checkdom(sk, sl, st); /* check for dominance */
    sk = sl+1; sl = st; 
    if (x == 0) s0 = sl;
  }
  bound = a->BVOL + fill - sum ;
  cout<<"bound: "<< bound <<endl;
  *sm = removedom(s0+1, sl);
  return bound;/* bound is curr filling + all free vol */
}

/* ======================================================================
				branch
   ====================================================================== */

/* Recursive algorithm for solving a knapsack filling of a single bin. */
/* In each iteration, the set of feasible positions for placing a new */
/* box is found, and an upper bound on the filling is derived. If the */
/* bound indicates that an improved solution still may be obtained, every */
/* box is tried to be placed at every feasible position, before calling */
/* the algorithm recursively. */

// 分支算法，单盒子的背包迭代算法。在每个迭代过程中，判断一个改进的解能否得到，然后
// 执行其他各种操作。

void branch(solution *a, item *f, item *l, int miss, double fill)
{
  register item *i,*j,*k;
  register point *s;
  boolean sym;
  int d;
  double bound;
  point *sl;
  point	*s1;
  s1 = new point[9*MAXITEMS];

//  cout<<"branch f: "<<f->no<<endl;
//  cout<<"branch l: "<<l->no<<" "<<l->k<<endl;

  if (stopped) return;
//  a->iter3d++;
//  if (a->iter3d % 100000 == 0) timelimit(maxtime);
//  if (a->iter3d == a->maxiter) a->optimal = TRUE;
  if (a->optimal) return;

  // find min/max dimensions of remaining items 
  if (miss == 0) { // 重要的终止条件，由a->optimal来控制
    // none left -> good: save solution 
	bound = findplaces(a, f, l, s1, &sl, fill);
	cout<< "best bound: " << bound<<endl;
	if ( bound > a->maxfill ){
		for ( j = a->fsol, k = f; k != l+1 ; k++ ){
			*j = *k;
//			cout<<j->x<<" "<<j->y<<" "<<j->z<<endl;
		    j++;
		}
		a->lsol = j-1;
        a->maxfill = bound; 
		if (a->maxfill == a->BVOL){
			a->optimal = TRUE;
		}
	    a->miss = miss;
	}
  }
  else {
      
      // find bound and positions to place new items 
      bound = findplaces(a, f, l, s1, &sl, fill);
	  
	  if (bound > a->maxfill) {
          // for each position in S, try to place an item there 
          for (s = s1; s != sl+1; s++) { // 分枝递归，从每枝的尾端开始倒退递归
			  for (i = f, d = 0; i != l+1; i++) {
			  if (i->k) continue; // already chosen 
			  
			  // see if item fits at position s 
	          if ((int) (s->x) + i->w > a->W) continue;
	          if ((int) (s->y) + i->h > a->H) continue;
	          if ((int) (s->z) + i->d > a->D) continue;
			  if ((s->mark == 1)&&(f->customer > s->belong->customer))continue;

	          // place item and call recursively 
	          i->k = TRUE; i->x = s->x; i->y = s->y; i->z = s->z;
	          branch(a, f, l, miss - 1, fill + i->vol); // 递归函数
	          i->k = FALSE; i->x = i->y = i->z = 0; d++; // 倒退函数
	          if (d == a->mcut) break; // terminate after mcut branches 
	          if (a->optimal) break;
		  }
	  }
	}
  }
}

/* ======================================================================
				onebin_fill
   ====================================================================== */

/* Knapsack filling of a single bin. The following procedure initializes */
/* some variables before calling the recursive branch-and-bound algorithm. */
 
boolean onebin_fill(solution *a, item *f, item *l, boolean fast)
{
  item *i, *j, *m;
  double vol,rate;
  int n;

  /* initialize items */
  for (i = f, m = l+1, vol = 0; i != m; i++) {
//	  cout << "item no: "<< i->no << endl;
	  i->x = 0; i->y = 0; i->z = 0; i->k = 0; 
	  vol += i->vol;
  }

  /* try to fill one bin with items [f,l] */
  n = DIF(f,l);
//  cout << "n: "<< n <<endl;
  a->iter3d  = 0;
  a->maxfill = 0; /* lower bound equal to all minus one */
  a->miss = n; 
  a->maxiter = (fast ? MAXITER : 0); /* limited or infinitly many */
  a->optimal = FALSE;
  a->mcut = 0; /* try all branches */
  branch(a, f, l, n, 0);

  /* copy solution */
  if (a->maxfill != 0) { 
	  cout<< "best: "<<a->maxfill<<endl;
	  for (i = a->fsol, j = a->fopt, m = a->lsol+1; i != m; i++, j++) 
		  *j = *i;
	  a->lopt = j-1;
      return TRUE;
  }
  return FALSE;
}