In this assignment you will implement either Tabu Search or Variable Neighbourhood            Search or Large Neighbourhood Search and investigate its usefulness for solving the 2D         rectangle packing problem. Pick whichever algorithm you prefer. You will need to produce a program, a report and video for this assignment. You may work in pairs. Please make sure     that every source code file and the report has the details of both partners in the format         name_ID_name_ID. Any programming language can be used for this assignment. No existing metaheuristic code can be used for this assignment.

The Problem

The 2D rectangle packing problem is also known as the stock cutting problem. It’s a problem faced by the wood, glass and paper industries. The issue is how to cut out a certain number  of shapes from a material (such as a chunk of wood or a roll of steel) with the minimum         wastage. In other words, we have a set of items and we want to arrange those items inside  one or more larger regions (called objects) such that an objective function (usually called       wastage) is minimized. The 2D rectangle packing problem is a specific instance of this class   of problem where:

n The items are 2D rectangles

n There is a single rectangular 2D object with a fixed width but potentially infinite height (e.g. a roll of steel)

n Items can be rotated 90 degrees and placed anywhere on the object

n Individual items cannot be cut up or overlapped

Two examples of solutions to the 2D rectangular packing problem for seven rectangles of

different sizes1  are shown below:

The configuration on the right has lower wastage because the total height of the

configuration on the right is less than the total height of the configuration on the left. So in the specific case of the 2D rectangle packing problem, height of the configuration can be a proxy for wastage.

While the two above solutions are relatively small and can be solved by hand, realistic     problems are much larger. On moodle I have provided four stock cutting problems in the form of CSV files, described in the following table:

Each CSV file consists of a row for each individual rectangle, and is of the form

<id>,<width>,<height>. The width the steel is always 100. The final row in the CSV file is the total area, which you can use as a sanity check.

Search Algorithms

The three search algorithms are clearly described in lectures and in the book and you need to implement one of them. You should make sure that you understand clearly how the       algorithm works before beginning.

Next, think about how to solve this problem with your given algorithm. You need to consider all possible components for a solutions, e.g. :

•   The problem representation : how can a valid solution be represented?

•   The value function : how can wastage be measured? (This is easy: wastage is directly proportional to the height of a configuration)

•   The neighbourhood and the move function : how can neighbourhoods of valid  solutions be defined around each possible solution, with an appropriate move function for moving to neighbours? Will infeasible solutions be allowed or        disallowed?

•   The initialisation : how will the initial solution be generated?

•   The algorithm specific issues: e.g. how will tabus be implemented if you focus on Tabu Search? How will destroy/repair methods be implemented if you focus on  Large Neighbourhood Search?

•   The termination criteria;

•   etc

To get started, implement the most naïve version of your algorithm and test in on problem 1 for debugging. Then expand it to the other problems and see how it goes. When that is   done, expand the implementation to include some of the advanced tweaks and                    improvements that are possible for these algorithms.

A minimum passing effort should consist of multiple experiments performed against the      four test problems to determine the overall best variant of your chosen algorithm. You can  choose to focus on one aspect (e.g. varying the length of the tabu list systematically and       seeing what happens) or you can focus on multiple aspects (e.g. the advanced concepts) or you can do both. Since most of these algorithms are randomised, a good experiment should consist of at least 10 runs of each variant with the average and lowest costs reported. Also  include timing results: a configuration that achieves only a slight improvement in value may actually take a lot longer, and timing data can reveal this. You will need to ensure that you   run your program on identical hardware in this case.