Implementing a Novel Algorithm
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
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.
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.
The above algorithm could be implemented as follows
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,
capacities inplace, since this could lead to unintended consequences.
Using the Algorithm
The newly implemented algorithm can then easily be used as follows.
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
When you feel that your algorithm should be added to the QMKPy package, please follow the following steps:
Place your code in the
qmkpy.algorithmsmodule, i.e., in the
Make sure that you added documentation in form of a docstring. This should also include possible references to literature, if the algorithm is taken from any published work.
Make sure that all unit tests pass. In order to do this, add your algorithm to the
SOLVERSlist in the test file
tests/test_algorithms.py. Additionally, you should create a new test file
tests/test_algorithm_<your_algo>.pywhich includes tests that are specific to your algorithm, e.g., testing different parameter constellations. You can run all tests using the