source.cpp

3DBPP BRANCH AND BOUND

#define TESTS          10     /* Number of test to run for each type */
#define MAXITEMS      201     /* Max number of items plus one */

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
//#include <values.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include "head.h"


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

#define srand(x)     srand48x(x)
#define randm(x)     (lrand48x() % (long) (x))
#define rint(a,b)    (randm((b)-(a)+1) + (a))

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

#define VOL(i)                 ((i)->w * (ptype) (i)->h * (i)->d)
#define DIF(i,j)               ((int) ((j) - (i) + 1))


/* ======================================================================
				 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 */

typedef int (*funcptr) (const void *, const void *);

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

FILE *trace;


/* =======================================================================
                                random
   ======================================================================= */

/* to generate the same instances as at HP9000 - UNIX, */
/* here follows C-versions of SRAND48, and LRAND48.  */

unsigned long _h48, _l48;

void srand48x(long s)
{
  _h48 = s;
  _l48 = 0x330E;
}

long lrand48x(void)
{
  _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC);
  _l48 = _l48 * 0xE66D + 0xB;
  _h48 = _h48 + (_l48 >> 16);
  _l48 = _l48 & 0xFFFF;
  return (_h48 >> 1);
}


/* ======================================================================
				   timeused
   ====================================================================== */

void timeused(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 */
  }
}


/* ======================================================================
				specialbin
   ====================================================================== */

void specialbin(item *f, item *l, int W, int H, int D)
{
  item *m, *i, *j, *k;
  int w, h, d, r;

  /* vis(1,"specialbin [%d] %d,%d,%d\n", DIF(f,l), W, H, D); */
  if (f == l) { f->w = W; f->h = H; f->d = D; return; }
  if (DIF(f,l) == 5) {
    w = W/3; h = H/3; i = f+1; j = f+2; k = f+3; 
    i->w =   W-w; i->h =     h; i->d = D;
    j->w =     w; j->h =   H-h; j->d = D;
    k->w =   W-w; k->h =     h; k->d = D; 
    l->w =     w; l->h =   H-h; l->d = D;
    f->w = W-2*w; f->h = H-2*h; f->d = D;
    return;
  }

  m = f + (l-f) / 2;
  for (;;) {
    switch (rint(1,3)) {
      case 1: if (W < 2) break;
		  w = rint(1,W-1); 
  	      specialbin(f, m, w, H, D);
	      specialbin(m+1, l, W-w, H, D);
	      return;
      case 2: if (H < 2) break;
	      h = rint(1,H-1); 
	      specialbin(f, m, W, h, D); 
	      specialbin(m+1, l, W, H-h, D);
	      return;
      case 3: if (D < 2) break;
	      d = rint(1,D-1);
	      specialbin(f, m, W, H, d); 
	      specialbin(m+1, l, W, H, D-d);
	      return;
    }
  }
}


/* ======================================================================
				randomtype
   ====================================================================== */

void randomtype(item *i, double W, double H, double D, int type)
{
  double w, h, d, t;

  if (type <= 5) { /* Martello, Vigo */
    t = rint(1,10); 
	if (t <= 5) type = t;
  }
  switch (type) {
    /* Martello, Vigo */
    case  1: w = rint(1,W/2);   h = rint(2*H/3,H); d = rint(2*D/3,D); break;
    case  2: w = rint(2*W/3,W); h = rint(1,H/2);   d = rint(2*D/3,D); break;
    case  3: w = rint(2*W/3,W); h = rint(2*H/3,H); d = rint(1,D/2);   break;
    case  4: w = rint(W/2,H);   h = rint(H/2,H);   d = rint(D/2,D);   break;
    case  5: w = rint(1,W/2);   h = rint(1,H/2);   d = rint(1,D/2);   break;

    /* Berkey, Wang */
    case 6: w = rint(1,10);    h = rint(1,10);    d = rint(1,10);    break;
    case 7: w = rint(1,35);    h = rint(1,35);    d = rint(1,35);    break;
    case 8: w = rint(1,100);   h = rint(1,100);   d = rint(1,100);   break;
  }
  i->w = w; i->h = h; i->d = d;i->vol = w*h*d;
  i->x = 0; i->y = 0; i->z = 0;
}


/* ======================================================================
				allgood
   ====================================================================== */

boolean allgood(stype totvol, item *f, item *l)
{
  item *j, *m;
  stype vol;

  for (vol = 0, j = f, m = l+1; j != m; j++) {
    if ((j->w < 1) || (j->h < 1) || (j->d < 1)) return FALSE;
    vol += VOL(j);
  }
  return (vol == totvol);
}


/* ======================================================================
				maketest
   ====================================================================== */

void maketest(item *f, item *l, double *W, double *H, double *D,
	      double bdim, short customer,int type)
{
  register item *i, *k, *m;
  int no;

  /* set bin dimensions */
  *W = bdim; *H = bdim; *D = bdim;

  /* make maxtypes item types */
  for (i = f, m = l+1, no = 1; i != m; i++, no++) {
    randomtype(i, *W, *H, *D, type);
    i->no = no;
	i->customer = rint(1,customer);
  }

  /* make two complete bins when test */
  if (type == 9) {
    no = DIF(f,l)/3;
    k = f + no; m = k + no;
    for (;;) {
      specialbin(f  , k, *W, *H, *D); 
      specialbin(k+1, m, *W, *H, *D); 
      specialbin(m+1, l, *W, *H, *D); 
      if (allgood(3*bdim*bdim*bdim, f, l)) break;
    }
  }
}

void randominput(solution *a, long n, long v, short customer, double bindim, short type){
	srand(v+n); /* initialize random generator */
	double W,H,D;
	a->D = a->W = a->H = bindim;
	a->BVOL = bindim*bindim*bindim;
	a->numitem = n;
	a->numcustomer = customer;
    item tab[MAXITEMS];
	a->fitem = &tab[0];
	a->litem = &tab[n-1];
	a->fsol = new item[MAXITEMS];
	a->fopt = new item[MAXITEMS];
	maketest(a->fitem, a->litem, &W, &H, &D, bindim, customer, type);
    /* printitems(f, l, W, H, D); */
}

/* ======================================================================
			       initialize_problem
   ====================================================================== */

int input(solution *a){
	ifstream myfile;
	char terminate;
	ntype tempitem,tempcustomer,tempno;
	itype tempw,tempd,temph;
    item temp[MAXITEMS];
	item *temp1;
	temp1 = a->fitem = temp;
	myfile.open("3dbpp.txt",ios::in);
    if(!myfile){
		cerr<<"unable to open the file"<<endl;
		return -1;
	}
    myfile >> tempcustomer >> tempitem;
	a->numcustomer = tempcustomer;
	a->numitem = tempitem;
    myfile >> tempw >> tempd >> temph;
	a->W = tempw; a->D = tempd; a->H = temph;
	a->BVOL = tempw*tempd*temph;
	a->fsol = new item[MAXITEMS];
	a->fopt = new item[MAXITEMS];
	while ( myfile.get(terminate)){
//      cout << temp1 <<endl;
		myfile >> tempno >> tempw >> tempd >> temph >> tempcustomer;
//      cout << tempno << tempw << tempd << temph << tempcustomer << endl;
		temp1->no = tempno;
		temp1->w = tempw;
		temp1->d = tempd;
		temp1->h = temph;
		temp1->customer = tempcustomer;
		temp1->x = temp1->y = temp1->z = temp1->k = 0;
		temp1->vol = tempw * tempd * temph;
        temp1++;
	}
	temp1--;
	a->litem = temp1;
	return 1;
}

/* ======================================================================
				clearitems
   ====================================================================== */

void clearitems(solution *a)
{
  item *i, *m;

  for (i = a->fitem, m = a->litem+1; i != m; i++) {
    i->x = i->y = i->z = 0; i->k = FALSE;
  }
  /* sort nonincreasing volume */
  qsort(a->fitem, (m-a->fitem), sizeof(item), (funcptr)initial);
}

void main(){
	solution *a = new solution;
	input(a);
	short type,customer;
	long n,v;
	double bindim;
	item *b,*i,*f,*l;
	double lowerbound, lowerbound1, lowerbound2, z, upperbound, rate, time;
	double vsum = 0;
    ofstream file;
	file.open ("result.txt",ios::app,0);
//	cout<< "3DBPP PROBLEM"<<endl;
//    cout<< "n = ";
//    cin >> n;
//	cout<< "customer = ";
//	cin >> customer;
//    cout<<"bindim = ";
//    cin >>bindim;
//    cout<<"type = ";
//    cin >>type;
 //   for ( v = 1;v<=TESTS;v++ ){
//		randominput(a,n,v,customer,bindim,type);
        vsum = 0;
		b = a->fitem;
	    qsort(b,a->numitem,sizeof(item),(funcptr)initial);
	    cout << "The information of the container:"<<endl;
	    file << "The information of the container:"<<endl;
	    cout << "Container width: "<<a->W<<" "<<"Container depth: "<<a->D<<" "<<"Container height: "<<a->H<<endl;
        file << "Container width: "<<a->W<<" "<<"Container depth: "<<a->D<<" "<<"Container height: "<<a->H<<endl;
	    cout << "The packing Items are as following: "<<endl; 
        file << "The packing Items are as following: "<<endl;   
	    for ( b = a->fitem ; b!= a->litem+1 ; b++){
		cout << "Item number: "<< b->no << " " <<"Customer number: "<< b->customer <<"Item width: "<<b->w<<" "<<"Item depth: "<<b->d<<" "<<"Item Height: "<<b->h<<endl;
        file << "Item number: "<< b->no << " " <<"Customer number: "<< b->customer <<"Item width: "<<b->w<<" "<<"Item depth: "<<b->d<<" "<<"Item Height: "<<b->h<<endl;
		vsum = vsum + b->vol;
		}
		lowerbound = bound_zero(a,a->fitem,a->litem);
	    lowerbound1 = bound_one_x(a,a->fitem,a->litem);
	    lowerbound2 = bound_two(a,a->fitem,a->litem);
        cout << " The continuous lower bound is: "<< lowerbound << endl;
    	file << " The continuous lower bound is: "<< lowerbound << endl;
    	cout << " The new lower bound one is: "<< lowerbound1 << endl;
    	file << " The new lower bound one is: "<< lowerbound1 << endl;
    	cout << " The new lower bound twe is: "<< lowerbound2 << endl;
    	file << " The new lower bound twe is: "<< lowerbound2 << endl;
        lowerbound = max(lowerbound,lowerbound1,lowerbound2);
/*    	z = dfirst_heuristic(a);
     	upperbound = z/a->D;
        rate = vsum/(upperbound*a->BVOL);
        if ( z < a->D ){
			cout << "The upper bound of the 3D-Binpacking problem is: "<< upperbound << endl;
	        file << "The upper bound of the 3D-Binpacking problem is: "<< upperbound << endl;
		    for ( f = a->fitem, l = a->litem; f != l+1 ; f++ ){
				cout <<" The coordinate of the packed items using layer strategy are as following:"<<endl;
			    file <<" The coordinate of the packed items using layer strategy are as following:"<<endl;
			    cout <<" Item number: "<< f->no << " " <<"Customer number: "<< f->customer <<" "<<"X-coordinate: "<<f->x<<" "<<"Y-coordinate: "<<f->y<<" "<<"Z-coordinate: "<<f->z<<endl;
		        file <<" Item number: "<< f->no << " " <<"Customer number: "<< f->customer <<" "<<"X-coordinate: "<<f->x<<" "<<"Y-coordinate: "<<f->y<<" "<<"Z-coordinate: "<<f->z<<endl; 
			}
	        cout << "The usage rate of the space is: "<<rate<<endl;
		    file << "The usage rate of the space is: "<<rate<<endl;
		}
        if ( z > a->D ){
		    cout << "The upper bound of the 3D-Binpacking problem is: "<< upperbound << endl;
	        file << "The upper bound of the 3D-Binpacking problem is: "<< upperbound << endl;
		    cout << "The usage rate is: " <<rate<<endl;
		    file << "The usage rate is: " <<rate<<endl;
		}
	    cout << " The Max lower bound of 3D-Binpacking problem is "<< lowerbound << endl;
	    clearitems(a);*/
	    timeused(NULL);
	    onebin_fill( a, a->fitem, a->litem , 1 );
	    timeused(&time);
	    if ( a->maxfill != 0 ){
			cout <<" The coordinate of the packed items using branch-and-bound are as following:"<<endl;
		    file <<" The coordinate of the packed items using branch-and-bound are as following:"<<endl;
		    for ( i = a->fopt ; i != a->lopt+1 ; i++ ){
				cout <<"Item number: "<< i->no << " " <<"Customer number: "<< i->customer <<" "<<"X-coordinate: "<<i->x<<" "<<"Y-coordinate: "<<i->y<<" "<<"Z-coordinate: "<<i->z<<endl;
		        file <<"Item number: "<< i->no << " " <<"Customer number: "<< i->customer <<" "<<"X-coordinate: "<<i->x<<" "<<"Y-coordinate: "<<i->y<<" "<<"Z-coordinate: "<<i->z<<endl;
			}
	        rate = vsum/(vsum+a->BVOL-a->maxfill);
	        cout << "The usage rates of the space is: "<<rate<<endl;
	    	file << "The usage rates of the space is: "<<rate<<endl;
	    	cout << "Time it used is: "<<time<<endl;
	    	file << "Time it used is: "<<time<<endl;
		}
	    if (a->maxfill == 0){
			cout <<"The items can not packed in a singe bin using branch-and-bound"<<endl;
	        file <<"The items can not packed in a singe bin using branch-and-bound"<<endl;
		    cout <<"Time it used is: "<<time<<endl;
		    file <<"Time it used is: "<<time<<endl;
		}
//	}
	file.close();
}