Framework for solving the Quadratic Multiple Knapsack Problem (QMKP)
Project description
QMKPy: A Python Framework for Solving Quadratic Multiple Knapsack Problems
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
pip3 install qmkpy
or from the GitHub repository
git clone https://github.com/klb2/qmkpy.git
cd qmkpy
git checkout dev # optional for the latest development version
pip3 install .
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.