# Implementing a Novel Algorithm

Note

TL;DR: Your function needs to be callable as: func(profits, weights, capacities, *args) and needs to return assignments in the binary form.

If you want to implement and test a novel solution algorithm for the QMKP, you simply need to write a Python function that takes profits as first argument, weights as second, and capacities as third argument. Beyond that, it can have an arbitrary number of additional arguments. However, it needs to be possible to pass them positionally.

The return of the function needs to be the assignment matrix in binary form.

The following example is also illustrated in a Jupyter notebook that you can either run locally or using an online service like Binder. ## Example

As an example, we want to implement the following algorithm

Assign the item $$i$$ with the smallest weight $$w_i$$ to the first knapsack $$k$$ where it fits, i.e., where $$c_k \geq w_i$$.

Obviously, this algorithm ignores the profits and will not yield very good results. However, it only serves demonstration purposes.

### Algorithm Implementation

The above algorithm could be implemented as follows

Example Algorithm
 1def example_algorithm(profits, weights, capacities):
2    assignments = np.zeros((len(weights), len(capacities)))
3    remaining_capacities = np.copy(capacities)
4    items_by_weight = np.argsort(weights)
5    for _item in items_by_weight:
6        _weight = weights[_item]
7        _first_ks = np.argmax(remaining_capacities >= _weight)
8        assignments[_item, _first_ks] = 1
9        remaining_capacities[_first_ks] -= _weight
10    return assignments


It should be emphasized that you should not modify any of the input arrays, e.g., capacities inplace, since this could lead to unintended consequences.

### Using the Algorithm

The newly implemented algorithm can then easily be used as follows.

Testing the Novel Algorithm
 1import numpy as np
2from qmkpy import total_profit_qmkp, QMKProblem
3from qmkpy import algorithms
4
5weights = [5, 2, 3, 4]  # four items
6capacities = [1, 5, 5, 6, 2]  # five knapsacks
7profits = np.array([[3, 1, 0, 2],
8                    [1, 1, 1, 4],
9                    [0, 1, 2, 2],
10                    [2, 4, 2, 3]])  # symmetric profit matrix
11
12qmkp = QMKProblem(profits, weights, capacities)
13qmkp.algorithm = example_algorithm
14assignments, total_profit = qmkp.solve()
15
16print(assignments)
17print(total_profit)


## Contributing a New Algorithm to the Package

1. Place your code in the qmkpy.algorithms module, i.e., in the qmkpy/algorithms.py file.
3. Make sure that all unit tests pass. In order to do this, add your algorithm to the SOLVERS list in the test file tests/test_algorithms.py. Additionally, you should create a new test file tests/test_algorithm_<your_algo>.py which includes tests that are specific to your algorithm, e.g., testing different parameter constellations. You can run all tests using the pytest command.