QMKPy
QMKPy: A Python Testbed for the Quadratic Multiple Knapsack Problem - Published in JOSS (2022)
Science Score: 95.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 1 DOI reference(s) in JOSS metadata -
✓Academic publication links
Links to: joss.theoj.org -
✓Committers with academic emails
2 of 3 committers (66.7%) from academic institutions -
○Institutional organization owner
-
✓JOSS paper metadata
Published in Journal of Open Source Software
Keywords
Repository
Python testbed for the Quadratic Multiple Knapsack Problem (QMKP)
Basic Info
- Host: GitHub
- Owner: klb2
- License: gpl-3.0
- Language: Python
- Default Branch: master
- Homepage: https://qmkpy.readthedocs.io
- Size: 216 KB
Statistics
- Stars: 8
- Watchers: 1
- Forks: 2
- Open Issues: 0
- Releases: 1
Topics
Metadata Files
README.md
QMKPy: A Python Testbed for the Quadratic Multiple Knapsack Problem
This software package primarily aims at research in the areas of operations research and optimization. It serves as a testbed that provides a way of quickly implementing and testing new algorithms to solve the quadratic multiple knapsack problem (QMKP) and compare it with existing solutions.
The goal is to encourage researchers and developers to share their algorithms and make them publicly available.
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 cu & \quad & \forall u\in\mathcal{K} \ & \sum{u=1}^{K} a{iu} \leq 1 & & \forall i \in {1, 2, \dots, N} \end{alignat} $$
This describes an assignment problem where one wants to assign $N\in\mathbb{N}$ items to $K\in\mathbb{N}$ knapsacks, which are described by the index set $\mathcal{K}={1, 2, \dots, K}$. Item $i$ has the weight $wi\in\mathbb{R+}$ and knapsack $u$ has the weight capacity $cu\mathbb{R+}$. If item $i$ is assigned to a knapsack, it yields the (non-negative) profit $pi\in\mathbb{R+}$. If item $j$ (with $j\neq i$ ) is assigned to the same knapsack, we get the additional joint profit $p{ij}\in\mathbb{R+}$.
The set of items which are assigned to knapsack $u$ is denoted by $\mathcal{A}(u)$ and $a_{iu}\in{0, 1}$ is an indicator whether item $i$ is assigned to knapsack $u$.
The objective of the above 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.
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
The benefit of enabling a simple and direct way of implementing novel
algorithms is highlighted by an example in the provided Jupyter notebook in
examples/Custom
Algorithm.ipynb.
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 -r requirements.txt
pip3 install .
pip3 install pytest # optional if you want to run the unit tests
Usage
In order to test the installation and get an idea of how to use the QMKPy
package, you can take a look at the examples/ directory.
It contains some standalone scripts that can be executed and perform some
simple tasks.
More detailed descriptions of the implemented algorithms and a documentation of the API can be found in the documentation.
A collection of reference datasets can be found at https://github.com/klb2/qmkpy-datasets.
Contributing
Please see CONTRIBUTING.md for guidelines on how to contribute to this project. In particular, novel algorithms are always welcome. Please check out the documentation for a brief overview on how to implement new algorithms for the QMKPy framework.
Owner
- Name: Karl-Ludwig Besser
- Login: klb2
- Kind: user
- Location: USA
- Company: Princeton University
- Website: https://klb2.gitlab.io
- Repositories: 7
- Profile: https://github.com/klb2
Postdoc at Princeton University in the area of wireless communications. My research interests lie in the areas of ultra-reliable communications and copulas.
JOSS Publication
QMKPy: A Python Testbed for the Quadratic Multiple Knapsack Problem
Authors
Institute for Communications Technology, Technische Universität Braunschweig, Germany
Institute for Communications Technology, Technische Universität Braunschweig, Germany
Editor
Mehmet Hakan Satman
Tags
knapsack problems QMKP operations research combinatorial optimizationGitHub Events
Total
Last Year
Committers
Last synced: 5 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| KLB | k****r@t****e | 107 |
| Mehmet Hakan Satman | m****n@g****m | 1 |
| Daniel S. Katz | d****z@i****g | 1 |
Issues and Pull Requests
Last synced: 4 months ago
All Time
- Total issues: 18
- Total pull requests: 2
- Average time to close issues: 13 days
- Average time to close pull requests: about 6 hours
- Total issue authors: 3
- Total pull request authors: 2
- Average comments per issue: 1.06
- Average comments per pull request: 1.0
- Merged pull requests: 2
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- ulf1 (10)
- max-little (7)
- ngocbh (1)
Pull Request Authors
- jbytecode (1)
- danielskatz (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- pypi 31 last-month
- Total dependent packages: 0
- Total dependent repositories: 2
- Total versions: 3
- Total maintainers: 1
pypi.org: qmkpy
Framework for solving the Quadratic Multiple Knapsack Problem (QMKP)
- Homepage: https://github.com/klb2/qmkpy
- Documentation: https://qmkpy.readthedocs.io
- License: GPLv3
-
Latest release: 1.2.0
published about 3 years ago
Rankings
Maintainers (1)
Dependencies
- matplotlib *
- qmkpy *
- numpy *
- numpy *
- actions/checkout v3 composite
- actions/setup-python v3 composite
- actions/upload-artifact v3 composite
- actions/checkout v2 composite
- actions/setup-python v2 composite
- codecov/codecov-action v3 composite