Investigating Bin-Packing Heuristics with C++ (100 pt. project)
In this project we investigate the efficacy of various bin-packing heuristics. The bin-packing problem is to fit n blocks of sizes w1, w1, w2, w3,…, wn into a number of bins, each of size W, where, obviously wi < W for i = 1, 2,…,n.
Here are the heuristics we’ll investigate.
Next Fit (NF) The idea behind this procedure is to open a bin and place the items into it in the order they appear in the list. If an item on the list will not fit into the open bin, we close this bin permanently and open a new one and continue packing the remaining items in the list. Of course, if some of the consecutive weights on the list exactly fill a bin, the bin is then closed and a new bin opened.
First Fit (FF) For First Fit, we place the next item in the list into the first bin which has not been completely filled (thought of as numbered from left to right) into which it will fit. When bins are filled completely they are closed and if an item will not fit into any currently open bin, a new bin is opened.
Best Fit (BF) For Best Fit, one again keeps bins open even when the next item in the list will not fit in previously opened bins, in the hope that a later smaller item will fit. The criterion for placement is that we put the next item into the currently open bin (e.g. not yet full) which leaves the least room left over. (In the case of a tie we put the item in the lowest numbered bin as labeled from left to right.)
Worst Fit (WF) For Worst Fit, one places the item into that currently open bin into which it will fit with the most room left over.
To test these under various circumstances, we’ll first create a file with a user-supplied number of random numbers (wi blocks), then we’ll read from the file and pack the blocks into “bins” which will be elements of an array bin.
Here’s some pseudo code to guide us:
http://www.ams.org/featurecolumn/archive/bins2.html
Here is an example of how the output might present the packing results.
****************************
* Welcome to Bin Packing! *
****************************
How big are your bins? 50
How many packages do you want to pack? 100
You have asked to pack 100 packages into bins of size 50
8 33 30 37 50 29 23 10 41 29 44 50 44 15 22 47 17 25 26 34 27 21 20 37 24 42 12
39 2 31 21 24
17 20 16 23 37 10 43 36
The packages, as read back from the file are
8 33 30 37 50 29 23 10 41 29 44 50 44 15 22 47 17 25 26 34 27 21 20 37 24 42 12
39 2 31 21 24
17 20 16 23 37 10 43 36
With "next fit" heuristic, there were 68 bins
filled to the following capacities:
34 50 38 40 50 50 50 44 36 42 17 38 45 30 37 35 40 38 33 30 37 50 29 33 41 29 44
50 44 37 47 42 26 34 48 20 37 24 42 12 41 31 49 35 41 38 37 33 46 41 42 47 47 4
7 34 47 34 37 39 47 43 46 27 47 48 43 23 43 39
With "first fit" heuristic, there were 57 bins
filled to the following capacities:
50 50 50 50 50 49 50 48 48 48 48 48 47 48 47 50 50 47 50 41 50 50 41 50 44 50 44
47 47 50 50 45 47 42 49 48 42 41 37 50 46 41 50 47 47 47 43 34 43 37 43 36 48 4
7 48 43 43 39
With "worst fit" heuristic, there were 63 bins
filled to the following capacities:
48 50 38 40 48 38 50 44 36 42 45 38 44 47 37 35 40 38 43 35 37 50 50 33 41 47 44
50 44 39 47 46 46 34 42 37 36 42 39 49 42 41 37 33 46 41 48 35 47 47 39 43 34 3
6 33 37 43 36 48 47 48 43 43 39
With "best fit" heuristic, there were 56 bins
filled to the following capacities:
50 50 50 50 50 49 50 48 50 42 50 50 50 48 50 50 50 50 50 49 50 50 41 47 48 50 44
50 47 50 50 47 47 42 49 49 47 41 47 50 50 41 50 31 47 47 43 50 37 43 36 48 47 4
8 43 43 39
You will need to create at least one input stream for the file. You can either create a new file stream each time you want to read from the beginning of the file again, or you can use advanced file operations as discussed in chapter 12 of Gaddis. The easier approach might be to just create a new file stream each time you want to rewind:
ifstream in1File, in2File, in3File, in4File;
Create and initialize integer arrays to represent the bins. Two hundred bins may be enough. As shown below, you can easily initialize all bins to have size 0.
int nfbins[200] = {0};
int ffbins[200] = {0};
int wfbins[200] = {0};
int bfbins[200] = {0};
Prompt the user for the size of the bins and the number of blocks (packages) you want to pack.
cout << "\n\nHow big are your bins? ";
while(binSize < 1) {
cin >> binSize;
if(!(binSize > 0)) cout << "\nThat's a negative, try again: ";
}
cout << "\n\nHow many package do you want to pack? ";
while(numbPacks < 1) {
cin >> numbPacks;
if(!(numbPacks > 0)) cout << "\nThat's a negative, try again: ";
}
Seed the random number generator:
srand(time(0));
Write numbPacks random numbers less than binSize to a file.
ofstream outputFile;
outputFile.open("packages.txt");
if ( !outputFile.is_open() ) { // Check to see if file was opened
// The file could not be opened
cout << endl << "ERROR: Unable to open file" << endl;
exit(1);
}
You can signal the end of file with a
negative number and close the file.
outputFile << -1;
outputFile.close();
//////////////////////////////////////////////
// Next Fit
// Now open the file for reading and start packing bins
inFile.open("packages.txt");
binNum = 0;
in1File >> curValue;
while(curValue >= 0) {
cout << curValue <<
" ";
// If it fits, put it in.
if(nfbins[binNum]+curValue <= binSize)
nfbins[binNum] += curValue;
// If it doesn’t fit, open a new bin and but it in.
else {
++binNum;
nfbins[binNum] = curValue;
}
// Get next package from file.
In1File >> curValue;
}
// Report results.
cout << "\n\nWith
\"next fit\" heuristic, there were " << binNum
<< " bins \nfilled
to the following capacities: \n";
for(i=0;i<=binNum;++i)
cout << nfbins[i] << " ";
in1File.close();
Repeat with first fit, worst fit and best fit heuristics.