Code Conventions

The code in the library follows some conventions, which are specified in the following. We assume that there are \(N\) items and \(K\) knapsacks.

Basic Arrays

In the following, we will discuss the essential elements of the QMKP and their implementation in the qmkpy framework.

Mathematical Description

The four essential components of the QMKP are the following.

Profit matrix \(P\in\mathbb{R}_{+}^{N\times N}\)

This symmetric matrix contains the profit values \(p_i\) on the main diagonal and the joint profit values \(p_{ij}\) as the other elements.

Weights \(w\in\mathbb{R}_{+}^{N}\)

This vector contains the weights of the items, where the \(i\)-th component \(w_i\) corresponds to the weight of item \(i\).

Capacities \(c\in\mathbb{R}_{+}^{K}\)

This vector contains the capacities of the knapsacks, where the \(i\)-th component \(c_i\) corresponds to the capacity of knapsack \(i\).

Assignments \(\mathcal{A}=\{\mathcal{A}_1, \mathcal{A}_2, \dots, \mathcal{A}_K\}\) with \(\mathcal{A}_i\subseteq \{1, 2, \dots{}, N\}\)

The assignments of items to knapsacks are collected in the set \(\mathcal{A}\). It contains the individual sets \(\mathcal{A}_i\) which contains the indices of all items that are assigned to knapsack \(i\).

Implementation

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 \times N\) matrix \(P\). We have that the profits of the individual items \(p_i\) are placed on the main diagonal profits[i-1, i-1] = p_i and the joint profits \(p_{ij}\) make up the other elements as profits[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 \(w_i\) corresponds to the index i-1, i.e., weights[i-1] = w_i.

capacities

The capacities vector is implemented as a list of length K, where the capacity \(c_i\) corresponds to the index i-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 \(\mathcal{A}\) are represented by a binary array of size [N, K] where row \(i\) stands for item \(i\) and column \(u\) represents knapsack \(u\). Thus, element assignments[i-1, u-1] = 1, if item \(i\) is assigned to knapsack \(u\) and assignments[i-1, u-1] = 0 otherwise.

Argument Order

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.

Alternative Representation of the Assignment Matrix

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\in\{0, 1, \dots{}, 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()).