Metadata-Version: 2.1
Name: qmkpy
Version: 1.0.0
Summary: Framework for solving the Quadratic Multiple Knapsack Problem (QMKP)
Home-page: https://github.com/klb2/qmkpy
Author: Karl Besser
Author-email: k.besser@tu-bs.de
License: GPLv3
Project-URL: Documentation, https://qmkpy.readthedocs.io
Project-URL: Source Code, https://github.com/klb2/qmkpy
Keywords: quadratic multiple knapsack problem,knapsack problem,operations research
Platform: UNKNOWN
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Telecommunications Industry
Classifier: License :: OSI Approved :: GNU General Public License v3 (GPLv3)
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Topic :: Scientific/Engineering
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy

# QMKPy: A Python Framework for Solving Quadratic Multiple Knapsack Problems

[![Pytest](https://github.com/klb2/qmkpy/actions/workflows/pytest.yml/badge.svg)](https://github.com/klb2/qmkpy/actions/workflows/pytest.yml)
[![codecov](https://codecov.io/gh/klb2/qmkpy/branch/master/graph/badge.svg?token=NFBF1ZZEXQ)](https://codecov.io/gh/klb2/qmkpy)
[![Read the docs status](https://readthedocs.org/projects/qmkpy/badge/?version=latest&style=flat)](https://qmkpy.readthedocs.io)


This software package primarily aims at research in the areas of operations
research and optimization.
It provides a way of quickly implementing and testing new algorithms to solve
the quadratic multiple knapsack problem (QMKP) and compare it with existing
solutions.


## Problem Description
The QMKP is defined as the following combinatorial optimization problem

$$
\begin{alignat}{3}
	\max\quad & \sum_{u\in\mathcal{K}}\Bigg(\sum_{i\in\mathcal{A}(u)} p_{i} &+&\sum_{\substack{j\in\mathcal{A}(u), \\ j\neq i}} p_{ij}\Bigg)\\
	\mathrm{s.t.}\quad & \sum_{i\in\mathcal{A}(u)} w_{i} \leq c_u & \quad & \forall u\in\mathcal{K} \\
	& \sum_{u=1}^{K} a_{iu} \leq 1  & & \forall 1\leq i \leq N
\end{alignat}
$$

This describes an assignment problem where one wants to assign $N$ items to $K$
knapsacks. If item $i$ is assigned to a knapsack, it yields the profit $p_i$.
If item $j$ (with $j\neq i$ ) is assigned _to the same_ knapsack, we get the
additional joint profit $p_{ij}$.

## Features

- Quick and simple creation of QMKP instances
- Saving/loading of problem instances for a simple creation and use of
  reference datasets
- Easy implementation of novel algorithms to solve the QMKP
- High reproducibility and direct comparison between different algorithms


## Installation
The package can easily be installed via pip.
Either from the PyPI
```bash
pip3 install qmkpy
```
or from the GitHub repository
```bash
git clone https://github.com/klb2/qmkpy.git
cd qmkpy
git checkout dev  # optional for the latest development version
pip3 install .
```


