Month
Month
Welcome to the CSIG, a Special Interest Group of the ACGNJ. The subject for this month is a utility for packing shipping containers. (Again.) It uses the latest C++ compiler in Microsoft's Visual Studio 2005. There are a number of ways to refer to this compiler and code. Here's what Wikipedia says:
The Common Language Infrastructure (CLI) is an open specification developed by Microsoft that describes the executable code and runtime environment that form the core of the Microsoft .NET Framework. The specification defines an environment that allows multiple high-level languages to be used on different computer platforms without being rewritten for specific architectures.
| Microsoft .Net Framework 2.0 |
| C++ 7.0 |
| .Net 2.0 |
| CLI |
| Common Language Infrastructure |
| Managed |
Here are the details of this utility. Object: This program takes as input a list of boxes to be shipped in a container. It then iterates a large number of possible locations for the placement of the boxes while calculating the volume of the container. When the program finishes, the dimensions of the smallest container is displayed along with the packing efficiency. The ideal is 100 percent. For example: 5 boxes dimensioned 3x4x4 will fit in a 9x5x8 container with a packing efficiency of 66.7 percent.
Last month's meeting was quite lively with everyone participating in the discussion about the latest computers and programming issues. We then discussed the main technical subject about "Bin Sorting Algorithms" using the "Monty Carlo" technique. There were comments from just about everyone and many of the suggestions have been incorporated in the second half of the presentation for February. Here are some of the comments:
// 1. How about doing the long iteration in another thread. // 2. Check Wikipedia for Bin Packing algorithms. // 3. Watch out for strange object sizes like a baseball bat. // 4. Provide more user control for the solution. // 5. Make it easier to input box sizes. // 6. Why use fixed orientation of the boxes? Let the computer rotate them. // 7. Wikipedia suggests sorting the boxes by volume first. // 8. Provide box locations after the program finds a solution. // 9. Use bit algorithms for the flags; then, "AND" results to check. // 10. Provide a graphical output for the solution. // 11. Improve basic algorithm. // 12. If packing has reached 90 percent, quit. // 13. Check for no-data condition. // 14. Zero Progress Bar when new data is entered.
Virtually all of the comments have been addressed. The most exciting changes involve running the 1,000,000 calculations as a separate thread and then displaying the results in a 3d-like diagram. We will spend time this month discussing these and any special questions.
This is an exciting time for the C Language programming since Microsoft now has 4 different language compilers: C++, C++ Express, C-Sharp, and C-Sharp Express. These are all capable of creating Windows (tm) programs and the "Express" versions are free ! Additionally, Borland has just announced that it also has four new programs that are also available in free versions. These are Turbo C++, Turbo C-Sharp, Turbo Delphi and Turbo Delpi for .NET. You may also want to check with Intel and others for their generally free evaluation versions.
The beginning of the evening (starting at 7:30pm) will be a RANDOM ACCESS discussion. The main presentation will discuss the program.
Our download site has code and programs from most of our meetings. ( Source Code Files )
Sample Code
===========
//
// CALCULATE: This is the workhorse procedure of the utility.
// It will iterate through many possible solutions.
//
private: System::Void Calculate_Click(System::Object^ sender, System::EventArgs^ e) {
// Ideal Package would be cube root of sum of box volumes.
IEnumerator ^pBox = listView1->Items->GetEnumerator();
double real_volume = 0.0;
int i,j,k;
pBox->Reset();
Calculate->Enabled = false;
while (pBox->MoveNext())
{
ListViewItem ^ item1 = (ListViewItem ^) pBox->Current;
i = Convert::ToInt32(item1->Text);
j = Convert::ToInt32(item1->SubItems[1]->Text); // Note: starting at index 1.
k = Convert::ToInt32(item1->SubItems[2]->Text);
real_volume += (double) (i * j * k);
}
// ideal shipping carton = cube root volume;
double power = 0.333333333;
double real_ideal = Math::Pow(real_volume, power);
String ^sMsg = String::Format("Product Volume = {0:F3}\nCube size = {1:F3}",
real_volume, real_ideal);
//MessageBox::Show(sMsg);
// Create an immaginary box with twice the dimensions.
int imgBox = (int) (2.0 * (real_ideal + 0.99) );
Cubit ^flags = gcnew Cubit(imgBox, imgBox, imgBox);
//
// try to fit the boxes in the ideal shipping carton.
//
int mWidth, mHeight, mLength, orgx, orgy, orgz, volume;
bool collision, cubit_status;
int maxWidth, maxHeight, maxLength, minVolume, count;
int final_x, final_y, final_z;
minVolume = 12345678;
int tick = Environment::TickCount & Int32::MaxValue;
Random ^ pRand = gcnew Random(tick);
for (count=0; count < 500001; count++) // Loop through all boxes in list.
{
//Loop for many many cycles.
// For each box in the table
// Loop
// Select random origin.
// Test each CUBIT for collision.
// Endloop
// If no collisions, save volume and dimensions.
// If new volume is smaller, save volume and dimensions.
//EndLoop
//
pBox->Reset();
collision = false;
maxWidth = 0;
maxHeight = 0;
maxLength = 0;
flags->ResetAll();
pBox->Reset();
// Single Box Loop
while (pBox->MoveNext()) // Get dimensions of box
{
ListViewItem ^ item1 = (ListViewItem ^) pBox->Current;
mWidth = Convert::ToInt32(item1->Text);
mHeight = Convert::ToInt32(item1->SubItems[1]->Text);
mLength = Convert::ToInt32(item1->SubItems[2]->Text);
//
// pick a random location for the origin of the immaginary box
//