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()).