Coursework: The Multi-Knapsack Problem

The assignment is worth 50 marks.

It has 3 parts, worth 10, 25 and 15 marks, respectively

The Multi-dimensional Knapsack problem

The multi-dimensional knapsack problem is an optimisation problem where the goal is to maximise the total value or profit of a set of items.

It can be seen as an extension of the single knapsack problem, but instead of having a single constraint (a single sack), we can have two or more constraints.

It is better to think in terms of constraints or resources (rather than sacks) to understand this problem.

The following data provides an instance of the multi-dimensional knapsack problem.

n = number of possible items

m = number of constraints

A list of length n with the profits or values of each item

A list of length m with the amounts of each constraint or resource An n x m matrix with the “weight” or “use” of item i in constraint j

In mathematical terms, the problem can be formulated as follows

Maximise sum of p(j)s(j) for j = 1,…,n

Subject to sum of r(i,j)s(j) <= b(i) for i=1,…,m and j = 1,…,n Where, s is a binary vector s(j)=0 or 1

p is the vector of profits

r is the matrix of resource coefficients (weights) b is the vector with resource capacities

Let us make this more concrete with an example.

Let us assume we have a pizza shop.

We have the recipes of n different pizzas that we can produce.

Each of the n pizzas has a value or profit, we can think of it as its selling price.

But we have limited resources! In this case ingredients, so we cannot produce all the n pizza recipes.

This means that we need to select a subset of the n pizza recipes that maximises our profit.

Let us assume that for producing the pizzas we have m required ingredients (eg. flour, cheese, olives, ham, mushrooms, pineapple, etc), for each of them we have a fixed amount.

Each of the n pizza recipes uses a certain amount of the m ingredients (note: it can be zero for some of them).

Our task is to select the subset of the n pizza recipes subject to the constraints imposed by the amounts of the m ingredients we have.

Datasets

You are given 2 datasets to support your work. A small instance to facilitate your work and debugging and a harder instance to challenge your algorithm. The naming convention indicates the number of items n and the number of constraints m:

multi_knap_n28_m2.txt (https://canvas.stir.ac.uk/courses/13859/files/3303402?wrap =1) (https://canvas.stir.ac.uk/courses/13859/files/3303402/download?download_frd=1)

multi_knap_n200_m25.txt (https://canvas.stir.ac.uk/courses/13859/files/3303434?wrap =1) (https://canvas.stir.ac.uk/courses/13859/files/3303434/download?download_frd=1)

The format of each file is as follows:

number of variables (n), number of constraints (m) the coefficients p(j); j=1,…,n

for each constraint i (i=1,…,m): the coefficients r(i,j); j=1,…,n the constraint right-hand sides, capacities or bounds b(i); i=1,…,m

Jupyter Notebook & Use of Libraries

To facilitate your work, you are given a Jupyter notebook: multi_knapsack.ipynb ( https://canvas.stir.ac.uk/courses/13859/files/3303401?wrap =1) (https://canvas.stir.ac.uk/courses/13859/files/3303401/download?download_frd=1)

This notebook contains the code to read the data files. To read the files easily, place the notebook and the data files in the same folder.

You can use standard Python libraries such as matplotlib, math, random, and numpy.

You are not allowed to use libraries that implement metaheuristics, evolutionary or swarm- intelligence algorithms. You need to implement your method from scratch.

Part 1: Simple Hill-Climbing

Total: 10 marks

Implement a fitness (evaluation) function. That is a function, that measures the quality of a solution.

Implement a function that checks the validity of a solution.

Using the functions above, implement a simple hill-climbing search method to solve this problem.

Using the instance with n = 28 and m = 2, run experiments and report the results obtained using both numerical metrics and plots.

Part 2: Algorithm of Your Choice

Total: 25 marks

Here you’re given the opportunity to design your own algorithm.

The goal is to try to improve the performance of the simple hill-climbing method in Part 1.

Can you design an algorithm that improves the performance (finds better solutions) than hill- climbing?

To do so, you can either use some of the algorithm ideas discussed in the lectures and/or try your own ideas.

The marking on this part will be based on the following criteria

Design Effort and Algorithm Performance: A good algorithm requires design effort and produces good performance (finding good solutions in a reasonably short time).

Implementation Quality: The clarity, modularity and conciseness of your code.

Documentation: It is essential to document your design choices.

You should provide in text form (using markdown cells in your notebook) brief descriptions of

The type of algorithm

The choice of search operator (s) or components you used, and their parameter values Justify your choices when possible

Part 3: Performance Comparison

Total: 15 marks

Here you’re given the opportunity to perform a sound comparison of two versions of your algorithm.

By two versions, I do not mean two completely different algorithms!

For example, you can contrast two values of your algorithm hyper-parameters, or two different search operators.

Please note that

The optimisation methods we have studied are stochastic, meaning that any performance comparison needs to consider several runs, at least 10 runs.

In order to have a fair comparison between the two algorithm variants, we need to give them approximately the same computational effort (running time) to solve the problem.

Base your comparison on the hardest instance. To complete this part you should

Report in text form (using markdown cells in your notebook).

Briefly describe the two selected algorithm versions. Justify your design of the two selected versions.

What did you do to try to make the comparison fair?

Report numerical values such as average and standard deviation. Report plots with your comparative results.

Submission Guidelines

Submit a single Jupyter document (.ipynb), clearly identifying each part using markdown cells. Submit also an HTML version of your notebook to facilitate reading and initial inspection.

Use code cells for your code and plots, and markdown cells for your text descriptions and justification of design choices.

Programming Assignment (https://canvas.stir.ac.uk/courses/13859/assignments/110645)