Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 4: Local Search and Metaheuristics

COMP4691-8691 2021

Guidelines

● Answers to go in answers.pdf (replace the file with your pdf).

● In order to get full marks for the implementation parts, your code should be clear, well commented, sensibly structured and correct. We will only deduct marks for performance if the model you come up with is very inefficient.

● The key files you will edit are corner_heuristic.py and lns.py. These are both setup as scripts. They have a help message to give you the command line options, e.g.: python3 lns.py --help.

● You will need to study the code provided in framework.py, which provides a number of classes to get you started.

● It is encouraged that you construct new smaller functions or classes as required other than those explicitly requested, to make it easier to implement and present your code.

2D Packing

The problem considers a set of n rectangular boxes that are to be packed into a set of m containers. Each box and each container has an x-length and a y-length. Furthermore each box as an associated weight w that represents how important it is that the box is packed into a container. A box can either be packed vertically or horizontally into the container. The aim of the problem is to pack as many boxes into containers as possible such that the sum of the weights of packed boxes is maximised. Note that boxes cannot overlap and must stay within the boundaries of the containers. A solution to a problem with four containers and 100 boxes is visualised in figure 1.

1 Corner Heuristic [50 marks]

An efficient heuristic for the 2D packing problem can be developed that is based on a couple of insights: we may as well pack in corners, and corners are easy to track.

To do so, for all empty containers we only consider the bottom-left corner (x, y) = (0, 0) as the initial corner. When we insert a box into that container we check whether the box can be placed (both horizontally and vertically) into that corner. A box can fit into a specific corner in a container in a specific direction if firstly the box fits inside the container, and secondly it does not overlap any other boxes that are already placed in the container. Once a box is inserted into a corner we can create two new corners - one at the top-left corner of the box, and one at the bottom-right corner of the box. In figure 2, we see how the corners progress as boxes are inserted into a container.

If a box cannot fit into any of the corners from any of the containers then in the final solution it remains unpacked. Note that the order that both the boxes and containers are considered by the heuristic will most likely produce

different solutions, as well as the order corners are considered by a box and whether the box first attempts to be inserted horizontally or vertically.

This first section of the assignment will consider implementing this heuristic. Template code is given but only to generate an initial solution.

1.1 Check Fit [10 marks]

Complete the check_fit function in the corner_heuristic.py file. This funciton should check whether a box with a particular orientation (i.e. either horizontal or vertical), can be inserted into a specific corner of a container.

Note: a position is infeasible if any part of the box is outside the container or if the box overlaps with any other box that is already positioned in the container.

1.2 Heuristic Algorithm [10 marks]

Implement the corner_heuristic function in the corner_heristic.py file. You should parameterise this function, so that the heuristic can utilise dif-ferent orders for consideration of the boxes, containers, container corners and box orientations. The provided code sets you up to do this by passing lambda functions that take a list of the appropriate type, and return a new list in a particular order. Their default value is to just return the original ordering, but in the next question you will experiment with different ordering functions.

1.3 Experiments [10 marks]

Play around with different order functions for the corner heuristic on in-stance case-1-020.json. For the best combination you come up with, plot the solution you achieve in your report, and state the objective it achieves. Discuss the ordering combinations you tried, and what the best one was you found.

Note: different orderings you could consider passing to this heuristic include: reversing the order, randomised order, sorted based on identifier, sorted based on weight, sorted based on size (container or box), sorted based on the re-maining space in container. The random.sample and sorted python func-tions might come in useful for this.

1.4 Larger Instances [10 marks]

For the same ordering configuration (no need to retune for each instace), use the corner heuristic to solve instances case-4-100.json, case-5-200.json, and case-5-300.json, and present the objectives achieved in a table along-side the case-1-020.json result.

What is one way you could know if you have achieved an optimal solution for any of these instances? Have you achieved an optimal solution for any of these instances?

1.5 Incompleteness [10 marks]

In general when building a meta-heuristic it is desirable to ensure that the heuristic being used to generate solutions is complete, i.e. for a given pa-rameter setting the heuristic will generate the optimal solution. The corner-heuristic is known to be incomplete. This means that for some problems, there does not exist a parameter setting (in terms of orderings) to the heuris-tic that will generate an optimal solution.

Provide a minimal counter example that demonstrates that the corner heuris-tic is incomplete, i.e. an instance of the 2D packing problem described in this assignment, where no matter what parameters the heuristic is given it will never find the optimal solution. Briefly explain your answer.

2 Large Neighbourhood Search [50 marks]

Large Neighbourhood Search (LNS) is a single-solution based metaheuristic that aims to find high quality solutions to optimisation problems through iteratively destroying and repairing an incumbant solution. In the second part of this assignment we will build an LNS to the 2D packing problem that utilises the corner heuristic developed in the first part of this assignment. LNS requires an initial feasible solution to the problem as a starting point. Here we will simply just use the trivial solution where the containers are empty.

2.1 Destroy [10 marks]

Here we partially destroy a solution to our problem by completely unpacking a number of containers. In this way, the boxes in the packed containers re-main fixed whereas the unpacked containers are relaxed. Clearly, the number of containers that we unpack (the “degree of destruction” parameterised by fraction_destroyed) will impact how the search progresses.

Complete the destroy function in lns.py to partially destroy a given solu-tion by completely unpacking a number of containers. Use random sampling for deciding which containers to destroy (e.g., random.sample).

Hint: with the provided framework, any boxes removed from a container will need to be reinserted into the unpacked list.

2.2 Repair [10 marks]

We repair a solution by using the corner-heuristic to try to reinsert the un-packed boxes. Recall from section 1.3 that there are many different orderings you could consider providing to the corner heuristic, which you should lever-age in your LNS implementation. In particular you will want to introduce enough randomness to get a good balance between exploration and exploita-tion.

Complete the repair function in lns.py to reconstruct a solution.

2.3 LNS Algorithm [10 marks]

LNS works by iteratively destroying and repairing an incumbant solution. Applications of LNS often differ in how they update the incumbant solution. For example, the simplest version of LNS simply accepts any new solution that has an objective function that is at least as good as the current incum-bant. This can be thought of as a hill-climbing method. More advanced methods, such as Simulated-Annealing, allow the possibly for the incumbant solution to be replaced by a solution with a worse objective.

Complete the lns function in lns.py to implement the LNS algorithm using your destroy and repair functions. Design it to accept a new solution if the objective is at least as good as the incumbant solution.

Hint: you’ll likely want to “deepcopy” the incumbent solution prior to de-struction, so that we have a solution to continue from if that iteration doesn’t lead to an improvement.

2.4 Experiments [10 marks]

Evaluate your LNS solver on instances case-4-100.json, and case-5-200.json. Play around with different parameterisations of the corner heuristic (order-ings) and the fraction of containers destroyed. Describe the best param-eterisation combination you find in your report. State the best objective you achieve for each of the two instances after 300 iterations, and plot the corresponding solutions.

Hint: You should be aiming for a solution with an objective above 800 after 300 iterations for case-4-100.json.

2.5 Benefits? [10 marks]

Re-run your code but with fraction_destroyed = 1.0 (assuming this wasn’t the best you found in the previous section). Explain the implication of this parameter setting. By comparing the solutions after 300 iterations to your best parameterisation solutions, discuss whether or not this provides evidence that LNS is a beneficial approach for solving this 2D packing problem.

Note: For submission, be sure to leave your code so it runs with the best parameterisation you found in the previous section.