Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Coursework: Perturbative hyper-heuristic for Bin Packing Problem
1. Introduction
Bin packing is one of the most studied combinatorial optimisation problems and has
applications in logistics, space planning, production, cloud computing, etc. Bin packing is
proven to be NP-Hard and the actual difficulties depend on both the size of the problem (i.e.
the total number of items to be packed) and other factors like the distribution of item sizes in
relation to the bin size as well as the number of distinct item sizes (different items may have a
same size).
In this coursework, you are asked to write a C/C++/Python program to solve this problem
using a perturbative hyper-heuristic method. In addition to submitting source code, a
written report (no more than 2000 words and 6 pages) is required to describe your algorithm
(see Section 4 for detailed requirements). Both your program and report must be completed
independently by yourself. The submitted documents must successfully pass a plagiarism
checker before they can be marked. Once a plagiarism case is established, the academic
misconduct policies shall be applied strictly.
This coursework carries 45% of the module marks.
2. Bin Packing Problem (BPP)
Given a set of n items, each item j has a size of aj, BPP aims to pack all items in the
minimum number of identical sized bins without violating the capacity of bins (V). The
problem can be mathematically formulated as follow:
Artificial Intelligence Methods (COMP2051 or AE2AIM) Coursework Ver1.0 2
This mathematical formulation is generally NOT solvable by existing integer programming
solvers like CPlex, Gurobi, LPSolve, especially when the number of items n is large. The
solution space of bin packing problem is characterised by its huge size and plateau-like that
makes it very challenging for traditional neighbourhood search methods. In order to
consistently solve the problem with good quality solutions, metaheuristics and hyperheuristics are used,
which is the task of this coursework.
3. Problem instances
Over the years, a large number of BPP instances have been introduced by various research.
In this coursework, we shall provide 3 instances files (binpack1.txt,
binpack3.txt and binpack11.txt), respectively representing easy, medium and hard instances.
From which 10 instances shall be selected for testing and evaluation of your algorithm in
marking. For each test instance, only 1 run is executed, and its objective value is used for
marking the performance component (see Section 5).