# Welcome to QMKPy’s documentation!

**QMKPy** is a Python library for modeling and solving quadratic multiple
knapsack problems (QMKP).
It provides a framework that allows quickly implementing and testing novel
algorithms to solve the QMKP.
It is therefore primarily targeting researchers working in the area of
operations research/optimization.

Additionally, it can be used to easily generate datasets of QMKP instances which can be used as reference test set to fairly compare different algorithms.

The QMKP is an assignment problem where \(N\in\mathbb{N}\) items are assigned to \(K\in\mathbb{N}\) knapsacks such that an overall profit is maximized. The exact formulation of the QMKP that can be solved by this package is given as follows

where \(\mathcal{K}=\{1, 2, \dots, K\}\) describes the set of \(K\) knapsacks, \(\mathcal{A}({u})\) is the set of items that are assigned to knapsack \(u\), and \(a_{iu}\in\{0, 1\}\) is the indicator whether item \(i\) is assigned to knapsack \(u\). Each item \(i\) has the weight \(w_i\in\mathbb{R}_{+}\) and knapsack \(u\) has the weight capacity \(c_u\in\mathbb{R}_{+}\). When assigning item \(i\) to a knapsack, it yields the non-negative profit \(p_i\in\mathbb{R}_{+}\). When assigning item \(j\) (with \(j\neq i\)) to the same knapsack, the additional (joint) profit \(p_{ij}\in\mathbb{R}_{+}\) is obtained.

The objective of the above optimization problem is to maximize the total profit such that each item is assigned to at most one knapsack and such that the weight capacity constraints of the knapsacks are not violated.

*Remark:* The profits \(p\) are also referred to as “values” in the
literature.

A detailed description of the way how the mathematical components of the QMKP
are implemented in the `qmkpy`

framework can be found in the code
conventions page.

For a basic overview on knapsack problems, see [KPP04].