Test Data

• The70 input files should be placed in a folder named data. The first 65 input files contain 2000 rectangles, the final 5 input files contain somewhere between 1900 and 2100 rectangles.
  • Files 1.in - 20.in: width range is 1-1000, length range is 1-1000, rectangles are generated randomly
  • Files 21.in - 40.in: width range is 501-1000, length range is 1-500, rectangles are generated randomly
  • Files 41.in - 60.in: width range is 1-500, length range is 501-1000, rectangles are generated randomly
  • File 61.in: width is 1, length 1, for all rectangles
  • File 62.in: width is 1, length 1, for all rectangles
  • File 63.in: width is 1, length 1, for all rectangles
  • File 64.in: width is 1, length 1, for all rectangles
  • File 65.in: width is 1, length 1, for all rectangles
  • Files 66.in - 70.in: width range is 1-1000, length range is 1-1000, the original 2000 (plus or minus up to 100) rectangles are generated to fit inside a perfect square
• The driver.py file used for testing.
• Performance Levels: To receive 20/20, an average n-fold improvement of 23.0 or greater is needed. To receive 15/20, an improvement of 21.6 or greater is needed. To receive 10/20, an improvement of 19.6 or greater is needed. To receive 5/20, an improvement of 13.0 or greater is needed.
• The best solution produced an average n-fold improvement of 25.1. Here is Tom Warner's and Jason Sander's solution.

CSCI 338 Bin Packing Assignment

• Due Date: Friday, February 19th no later than 11:59 p.m.
• You must complete this assignment with exactly one other classmate. If you work alone, there will be a 20 point penalty.

Assignment

Consider a company such as Falcon Structures that builds custom rectangular shipping containers. A custom shipping container is built to provide a safe environment for goods that a customer wants to have transported somewhere. A shipping container with a smaller perimeter requires less material to build and consequently saves money. For this assignment, Falcon Structures has hired you to determine how to build a shipping container as cheaply as possible.

For additional information and background, take a look at Alex's GitHub Bin-Packing Repository.

CSCI 338 Relevance

This problem is an NP-Complete problem, a class of problems that we will learn about in CSCI 338. Although no one knows for sure, it is believed that the only way to solve an NP-Complete problem optimally is with exponential time complexity. Since combinatorics quickly make this impractical, such problems are solved using heuristics (or rules-of-thumb) that yield pretty good answers in reasonable amounts of time. This assignment will give you experience developing heuristics for such a problem. Be creative and have fun!

Provided Code

• bin_packing.py. This is the file that you must modify. In particular, implement the find_solution function in a more sophisticated fashion so that better solutions are found. You are welcome to add auxiliary functions as needed.
• driver.py. This file provides infrastructure to create input files and to evaluate the solution returned by the find_solution function. Do not modify this file. This simplistic driver program is designed to help you learn Python. Because the function used to check for overlapping boxes is quadratic, this driver program is suitable for input files that contain up to 5,000 boxes.
• A more sophisticated driver appears in Alex's GitHub Repo. In particular, the rect_collision.py file contains a faster algorithm for detecting overlap.

Requirements

• Your solution must run in the IDLE environment with Python 3.5.
• 2-D boxes must be placed inside a rectangular shipping container in such a way that they do not overlap.
• Boxes are specified by a width and a length. Because this is a 2-D problem, no height is needed.
• Boxes have a fixed orientation. Thus, they can't be rotated.
• The dimensions of the boxes are integers between 1 and 1000 inclusive.
• An input file contains no more than 10,000 boxes.
• Your solution must run in 5.0 seconds or less on a Mac that has a 2.6 GHz CPU, a 64-bit Intel i7 and 16 GB of RAM.
• The find_solution function must improve upon the naive solution in driver.py by at least 75%.
• Do not modify driver.py at all. Your entire solution must appear in bin_packing.py and must correctly interface with driver.py.

Grading

• 70 points. The program will be tested on 70 mystery input files. Each input file will contain up to 10,000 boxes. For each input file, you will receive 1 point for improving upon the naive solution by at least 75% using no more than 5.0 seconds of time. (Note: a 75% improvement requires finding a perimeter than is at least 4 times smaller than that of the naive solution.)
• 20 points. The percentage improvements of all 70 inputs will be averaged and must be 75% or better to be eligible for these points. If your percentage improvement is in the top 10% of all solutions, 20 points are earned. If your percentage improvement is in the next 10%, 15 points are earned. If your percentage improvement is in the next 20%, 10 points are earned. If your percentage improvement is in the next 30%, 5 points are earned.
• 5 points. Place a comment at the top of your solution that explains the strategy you used to place the boxes.
• 5 points. The Python solution is high quality, easily understandable and maintainable.

Tips

• Python 3.5 with the IDLE editor can be downloaded from python.org.
• Python 3.5 has online documentation and tutorials.
• Make sure you understand the provided code.
• Design a strategy first, code second.
• Develop your own test cases.

Submission

One (and only one) partner should upload bin_packing.py to the D2L Dropbox no later than 11:59 p.m. on Friday, February 19th. When the solution is uploaded, write both partner's names in the D2L upload comment box.

Late submissions will receive no credit, but partial credit can be earned by making an ontime submission.