head1.h

3DBPP BRANCH AND BOUND

/* ======================================================================
				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(allinfo *a, box *f, box *l, int miss, stype fill)
{
  register box *i;
  register point *s;
  int d;
  stype bound;
  point *sl, s1[9*MAXBOXES];

  if (stopped) return; 
  a->iter3d++;  // 在onebin_robot算法中的迭代次数
  if ((a->iter3d == a->maxiter) && (a->maxiter != 0)) terminate = TRUE; // maxiter为迭代最高次数
  if (a->iter3d % 1000 == 0) check_timelimit(a->timelimit); // 到达1000次后开始使用时间限制函数
  a->subiterat++; 
  if (a->subiterat == IUNIT) { 
    a->subiterat = 0;
    a->iterat++; check_iterlimit(a->iterat, a->iterlimit); // iterat为onebin_decision中的迭代指示数
  }
  if (terminate) return;

  /* find min/max dimensions of remaining boxes */
  if (miss == 0) {
    /* none left -> good: save solution */
    memcpy(a->fsol, f, sizeof(box) * DIF(f,l)); // 从f开始把解复制到从a->fsol开始的解中
    a->maxfill = a->BVOL; terminate = TRUE; a->miss = miss;
  } 
  else {
    /* check if better filling */
    if (fill > a->maxfill) {
      memcpy(a->fsol, f, sizeof(box) * DIF(f,l)); 
      a->maxfill = fill; a->miss = miss;
	}

    /* find bound and positions to place new boxes */
    bound = findplaces(a, f, l, s1, &sl, fill); // 此函数会返回更新后最大pack的bound，并修改
                                                // 各个可pack的point的地址
    if (bound > a->maxfill) {
      /* for each position in S, try to place an box there */
      for (s = s1; s != sl+1; s++) {
	for (i = f, d = 0; i != l+1; i++) {
	  if (i->k) continue; /* already chosen */ // continue为跳出本循环

	  /* see if box 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;

	  /* place box 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++; // 此处是要释放所有i的空间吗？？？？
	  if (d == a->mcut) break; /* terminate after mcut branches */
	  if (terminate) break;
	}
	  }
    }
  }
}


/* ======================================================================
				onebin_robot
   ====================================================================== */

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

  /* initialize boxes */
  for (i = f, m = l+1, vol = 0; i != m; i++) {
    i->x = 0; i->y = 0; i->z = 0; i->k = 0; vol += i->vol;
  }

  /* try to fill one bin with boxes [f,l] */
  n = DIF(f,l);
  a->iter3d  = 0;
  a->maxfill = vol-1; /* lower bound equal to all minus one */ // 之所以要减去1主要是确保这个数
  // 足够小
  a->miss = n; 
  a->maxiter = (fast ? MAXITER : 0); /* limited or infinitly many */
  a->mcut = 0; /* try all branches */
  terminate = FALSE;

  /* calling branch-and-bound algorithm */
  timer(&t1);
  branch(a, f, l, n, 0); // 此函数内部的计时函数主要是看有没超过规定某一时间，与此处的timer并无关联
  timer(&t2);
  a->robottime += t2 - t1;

  /* copy solution */
  if (a->maxfill == a->BVOL) { /* NB: maxfill = BVOL, when optimal found */
    for (i = a->fsol, j = f, m = l+1; j != m; i++, j++) *j = *i;
    return TRUE;
  } 
  return FALSE;
}


/* ======================================================================
				mcut_heuristic
   ====================================================================== */

/* Knapsack filling of a single bin, solved heuristically. The heuristic */
/* is based on the exact algorithm for knapsack filling a single bin, where */
/* only a limited number of sub-nodes are considered at every branching node */
/* (the so-called m-cut approach) */

// 所谓的mcut即为在每个分支节点只能有一定数量的分支
 
void mcut_heuristic(allinfo *a)
{
  box *f, *l, *i, *j, *m;
  int b, n;

  /* initialize boxes */
  for (i = a->fbox, m = a->lbox+1; i != m; i++) {
    i->bno = i->x = i->y = i->z = 0; i->k = FALSE;
  }

  /* fill bins one by one */
  f = a->fbox; l = a->lbox;
  for (b = 1; ; b++) {
    /* fill one bin */
    for (i = f; i <= l; i++) i->k = FALSE; /* box not chosen */
    a->iter3d = 0;
    a->maxfill = 0;
    a->miss = DIF(f,l);
    a->maxiter = 5*MAXITER;
    terminate = FALSE;
    n = DIF(f,l);
    a->mcut = 2;
    if (n < 15) a->mcut = 3;
    if (n < 10) a->mcut = 4;
    branch(a, f, l, n, 0);

    /* copy solution */
    for (i = a->fsol, j = f, m = l+1; j != m; i++, j++) *j = *i;

    /* remove chosen boxes */
    for (i = f; i <= l;) if (i->k) { i->bno = b; SWAP(i,l); l--; } else i++;

    /* check if finished */
    if (l == f-1) break;
  }
  if (b < a->zmcut) a->zmcut = b; /* save solution */ // 此处的zmcut可以直接理解为bin的个数，即为解
  if (a->zmcut < a->z) savesol(a, a->fbox, a->lbox, a->zmcut);
}


/* ======================================================================
				mcut3_heuristic
   ====================================================================== */

/* Knapsack filling of a single bin, solved heuristically. Three different */
/* rotations of the problem are considered, and the best found solution */
/* is selected. */

void mcut3_heuristic(allinfo *a)
{
  int i;
  double t1, t2;
 
  timer(&t1); 
  a->zmcut = a->n;  /* very bad lower bound */ // 这个数字是确保这个解是最差的
  for (i = WDIM; i <= DDIM; i++) {
    mcut_heuristic(a);
    rotate_solution(a, a->fopt, a->lopt);
    rotate_problem(a, a->fbox, a->lbox);
  }
  timer(&t2);
  a->mhtime = t2 - t1;
}