# 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()`

).