The code in the library follows some conventions, which are specified in the following. We assume that there are N items and K knapsacks.
In the following, we will discuss the essential elements of the QMKP and their implementation in the qmkpy
framework.
The four essential components of the QMKP are the following.
- Profit matrix P ∈ ℝ+N × N
This symmetric matrix contains the profit values pi on the main diagonal and the joint profit values pij as the other elements.
- Weights w ∈ ℝ+N
This vector contains the weights of the items, where the i-th component wi corresponds to the weight of item i.
- Capacities c ∈ ℝ+K
This vector contains the capacities of the knapsacks, where the i-th component ci corresponds to the capacity of knapsack i.
- Assignments 𝒜 = {𝒜1, 𝒜2, …, 𝒜K} with 𝒜i ⊆ {1, 2, …, N}
The assignments of items to knapsacks are collected in the set 𝒜. It contains the individual sets 𝒜i which contains the indices of all items that are assigned to knapsack i.
The three main components described above are implemented in qmkpy
as arrays. The details are as follows.
profits
The profit matrix is implemented as an array of size
[N, N]
which represents the symmetric N × N matrix P. We have that the profits of the individual items pi are placed on the main diagonalprofits[i-1, i-1] = p_i
and the joint profits pij make up the other elements asprofits[i-1, j-1] = profits[j-1, i-1] = p_{ij}
. (The-1
index shift is due to Python's 0-based indexing.)weights
The weight vector is implemented as a list of length
N
, where the weight wi corresponds to the indexi-1
, i.e.,weights[i-1] = w_i
.capacities
The capacities vector is implemented as a list of length
K
, where the capacity ci corresponds to the indexi-1
, i.e.,capacities[i-1] = c_i
.assignments
There are multiple ways of representing the assignment of items to knapsacks. For all algorithms, the binary representation is used to represent the solution to a QMKP. In this, the assignments 𝒜 are represented by a binary array of size
[N, K]
where row i stands for item i and column u represents knapsack u. Thus, elementassignments[i-1, u-1] = 1
, if item i is assigned to knapsack u andassignments[i-1, u-1] = 0
otherwise.
Functions that work on a QMKP always assume the argument order profits, weights, capacities
and they are expected to return assignments
in the binary form described above.
So if you want to write a function that solves a QMKP, the argument list of your function needs to start with this. More details on this can also be found on the Implementing a Novel Algorithm page.
There are multiple ways of representing the final solution to a QMKP. Essentially, we need to represent the assignment of the items to the knapsacks.
Besides the binary representation of the algorithms, which is described above, another popular representation is the chromosome form C ∈ {0, 1, …, K}N which is a vector of length N, where the value of entry i specifies the knapsack to which item i is assigned. If the item is not assigned to any knapsack, the value 0 is used. In the qmkpy
framework, this is implemented such that chromosome
is a list of length N
, where index i-1
represents item i, i.e., chromosome[i-1] = u-1
indicates that item i is assigned to knapsack u. If item i is not assigned to any knapsack, we have chromosome[i-1] = -1
.
While the binary representation is dominantly used in this library, there exist functions to convert the to representations (see qmkpy.util.assignment_from_chromosome
and qmkpy.util.chromosome_from_assignment
).