Git Product home page Git Product logo

qmkpy's Introduction

QMKPy: A Python Testbed for the Quadratic Multiple Knapsack Problem

Pytest codecov Read the docs status PyPI License status

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 c_u & \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 $w_i\in\mathbb{R_+}$ and knapsack $u$ has the weight capacity $c_u\mathbb{R_+}$. If item $i$ is assigned to a knapsack, it yields the (non-negative) profit $p_i\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.
Binder

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 -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.

qmkpy's People

Contributors

danielskatz avatar jbytecode avatar klb2 avatar

Stargazers

avatar avatar avatar avatar avatar avatar avatar avatar

Watchers

avatar

Forkers

najibodhah theamrzaki

qmkpy's Issues

Recommendation: Show how to add a novel algorithm in the README.md to highlight what's claimed in the Statement of Need

In your statement of need, you state that adding novel algorithms with a easy-to-use function wrapper is the main contribution of this software. Thus, it would be beneficial to show potential users of your software an usage example directly in the README.md (e.g., https://qmkpy.readthedocs.io/en/latest/developing.html).
You hinted the ./example folder but this assumes that potential users of your software would clone the repo like a developer would. Alternatively, you could assume that potential software users pip install the package in Google Colab, and want to run an easy-to-copy code snippet there.

Include description of source code files

It would be helpful if a comment was provided at the top of each source file, describing what/why the various functions in that file are collected together in that file.

setup.py doesn't install numpy

Describe the bug
A clear and concise description of what the bug is.

Processing /Users/uh/projects/misc/qmkpy
  Preparing metadata (setup.py) ... error
  error: subprocess-exited-with-error
  
  × python setup.py egg_info did not run successfully.
  │ exit code: 1
  ╰─> [10 lines of output]
      Traceback (most recent call last):
        File "<string>", line 36, in <module>
        File "<pip-setuptools-caller>", line 34, in <module>
        File "/Users/uh/projects/misc/qmkpy/setup.py", line 3, in <module>
          from qmkpy import __version__, __author__, __email__
        File "/Users/uh/projects/misc/qmkpy/qmkpy/__init__.py", line 6, in <module>
          from . import algorithms
        File "/Users/uh/projects/misc/qmkpy/qmkpy/algorithms.py", line 3, in <module>
          import numpy as np
      ModuleNotFoundError: No module named 'numpy'
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: metadata-generation-failed

× Encountered error while generating package metadata.
╰─> See above for output.

note: This is an issue with the package mentioned above, not pip.
hint: See above for details.

To Reproduce
Follow https://github.com/klb2/qmkpy#installation

git clone https://github.com/klb2/qmkpy.git
cd qmkpy
# stay in main branch

python3 -m venv .venv                      
source .venv/bin/activate
pip3 install --upgrade pip

# error happens here
pip3 install .

Expected behavior
Successful installation

Screenshots
If applicable, add screenshots to help explain your problem.

Desktop (please complete the following information):

  • OS: macOS 12.5.1
  • Version Python 3.7.9
  • Versions of required packages: numpy 1.21.6

Additional context
The quick fix would be to run
pip3 install -r requirements.txt
before
pip3 install .

syntax errors

flake8 qmkpy

qmkpy/algorithms.py:1:1: F401 'typing.Any' imported but unused
qmkpy/algorithms.py:42:1: W293 blank line contains whitespace
qmkpy/algorithms.py:67:80: E501 line too long (102 > 79 characters)
qmkpy/algorithms.py:72:5: F841 local variable 'c_bar' is assigned to but never used
qmkpy/algorithms.py:75:80: E501 line too long (94 > 79 characters)
qmkpy/algorithms.py:77:5: E265 block comment should start with '# '
qmkpy/algorithms.py:78:80: E501 line too long (98 > 79 characters)
qmkpy/algorithms.py:79:5: E265 block comment should start with '# '
qmkpy/algorithms.py:83:80: E501 line too long (83 > 79 characters)
qmkpy/algorithms.py:90:80: E501 line too long (82 > 79 characters)
qmkpy/algorithms.py:94:5: E265 block comment should start with '# '
qmkpy/algorithms.py:105:9: E265 block comment should start with '# '
qmkpy/algorithms.py:106:5: E265 block comment should start with '# '
qmkpy/algorithms.py:156:5: F841 local variable 'num_items' is assigned to but never used
qmkpy/algorithms.py:157:5: F841 local variable 'num_ks' is assigned to but never used
qmkpy/algorithms.py:165:80: E501 line too long (80 > 79 characters)
qmkpy/algorithms.py:166:5: E265 block comment should start with '# '
qmkpy/algorithms.py:181:13: E265 block comment should start with '# '
qmkpy/algorithms.py:304:80: E501 line too long (102 > 79 characters)
qmkpy/algorithms.py:309:80: E501 line too long (164 > 79 characters)
qmkpy/algorithms.py:312:5: E303 too many blank lines (2)
qmkpy/algorithms.py:316:80: E501 line too long (94 > 79 characters)
qmkpy/algorithms.py:319:5: E303 too many blank lines (2)
qmkpy/algorithms.py:320:80: E501 line too long (80 > 79 characters)
qmkpy/algorithms.py:323:80: E501 line too long (95 > 79 characters)
qmkpy/algorithms.py:329:80: E501 line too long (95 > 79 characters)
qmkpy/util.py:1:1: F401 'typing.Any' imported but unused
qmkpy/util.py:1:1: F401 'typing.Callable' imported but unused
qmkpy/util.py:1:1: F401 'typing.Tuple' imported but unused
qmkpy/util.py:5:1: E302 expected 2 blank lines, found 1
qmkpy/util.py:14:80: E501 line too long (141 > 79 characters)
qmkpy/util.py:28:80: E501 line too long (122 > 79 characters)
qmkpy/util.py:29:80: E501 line too long (122 > 79 characters)
qmkpy/util.py:31:80: E501 line too long (118 > 79 characters)
qmkpy/util.py:88:80: E501 line too long (86 > 79 characters)
qmkpy/util.py:97:1: E302 expected 2 blank lines, found 1
qmkpy/util.py:110:1: W293 blank line contains whitespace
qmkpy/util.py:112:1: W293 blank line contains whitespace
qmkpy/util.py:113:12: W291 trailing whitespace
qmkpy/util.py:127:11: W291 trailing whitespace
qmkpy/util.py:132:1: W293 blank line contains whitespace
qmkpy/util.py:142:1: W293 blank line contains whitespace
qmkpy/util.py:158:80: E501 line too long (83 > 79 characters)
qmkpy/util.py:182:1: W293 blank line contains whitespace
qmkpy/util.py:198:1: E302 expected 2 blank lines, found 1
qmkpy/util.py:198:80: E501 line too long (87 > 79 characters)
qmkpy/util.py:229:80: E501 line too long (86 > 79 characters)
qmkpy/util.py:232:1: E302 expected 2 blank lines, found 1
qmkpy/util.py:266:80: E501 line too long (126 > 79 characters)
qmkpy/util.py:268:80: E501 line too long (111 > 79 characters)
qmkpy/util.py:276:80: E501 line too long (86 > 79 characters)
qmkpy/checks.py:1:1: F401 'typing.Any' imported but unused
qmkpy/checks.py:1:1: F401 'typing.Union' imported but unused
qmkpy/checks.py:5:1: E302 expected 2 blank lines, found 1
qmkpy/checks.py:36:80: E501 line too long (89 > 79 characters)
qmkpy/checks.py:38:1: E302 expected 2 blank lines, found 1
qmkpy/checks.py:58:1: E302 expected 2 blank lines, found 1
qmkpy/checks.py:60:51: W291 trailing whitespace
qmkpy/checks.py:70:1: W293 blank line contains whitespace
qmkpy/checks.py:115:80: E501 line too long (124 > 79 characters)
qmkpy/io.py:2:1: F401 'typing.Iterable' imported but unused
qmkpy/io.py:2:1: F401 'typing.Any' imported but unused
qmkpy/io.py:2:1: F401 'typing.Callable' imported but unused
qmkpy/io.py:2:1: F401 'typing.Tuple' imported but unused
qmkpy/io.py:2:1: F401 'typing.NoReturn' imported but unused
qmkpy/io.py:47:1: E302 expected 2 blank lines, found 1
qmkpy/io.py:115:1: E302 expected 2 blank lines, found 1
qmkpy/io.py:159:1: W293 blank line contains whitespace
qmkpy/io.py:175:1: W293 blank line contains whitespace
qmkpy/io.py:177:1: W293 blank line contains whitespace
qmkpy/io.py:178:80: E501 line too long (80 > 79 characters)
qmkpy/io.py:187:1: W293 blank line contains whitespace
qmkpy/io.py:235:80: E501 line too long (80 > 79 characters)
qmkpy/io.py:263:1: W293 blank line contains whitespace
qmkpy/io.py:265:64: E231 missing whitespace after ':'
qmkpy/io.py:296:5: F841 local variable 'reference' is assigned to but never used
qmkpy/qmkp.py:2:1: F401 'typing.Any' imported but unused
qmkpy/qmkp.py:3:1: F401 'pickle' imported but unused
qmkpy/qmkp.py:51:46: W291 trailing whitespace
qmkpy/qmkp.py:69:1: W293 blank line contains whitespace
qmkpy/qmkp.py:173:1: W293 blank line contains whitespace
qmkpy/qmkp.py:220:1: W293 blank line contains whitespace
qmkpy/qmkp.py:221:80: E501 line too long (138 > 79 characters)
qmkpy/__init__.py:24:11: E124 closing bracket does not match visual indentation

flake8 tests

tests/test_algorithm_fcs.py:7:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_fcs.py:18:80: E501 line too long (92 > 79 characters)
tests/test_algorithm_fcs.py:20:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_fcs.py:31:80: E501 line too long (92 > 79 characters)
tests/test_algorithm_fcs.py:33:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_fcs.py:42:9: F841 local variable 'solution' is assigned to but never used
tests/test_algorithm_fcs.py:45:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_fcs.py:54:9: F841 local variable 'solution' is assigned to but never used
tests/test_algorithm_fcs.py:57:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:1:1: E265 block comment should start with '# '
tests/test_qmkp.py:15:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:28:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:35:5: F841 local variable 'cp_solution' is assigned to but never used
tests/test_qmkp.py:41:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:53:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:66:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:77:80: E501 line too long (81 > 79 characters)
tests/test_qmkp.py:79:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:90:80: E501 line too long (81 > 79 characters)
tests/test_qmkp.py:92:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:102:5: E265 block comment should start with '# '
tests/test_qmkp.py:106:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:119:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:137:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:151:1: E302 expected 2 blank lines, found 1
tests/test_qmkp.py:152:33: E231 missing whitespace after ','
tests/test_qmkp.py:165:9: F841 local variable 'loaded_problem' is assigned to but never used
tests/test_io.py:5:1: F401 'pytest' imported but unused
tests/test_io.py:14:1: E302 expected 2 blank lines, found 1
tests/test_io.py:16:1: W293 blank line contains whitespace
tests/test_io.py:17:80: E501 line too long (82 > 79 characters)
tests/test_io.py:25:1: E302 expected 2 blank lines, found 1
tests/test_io.py:26:80: E501 line too long (82 > 79 characters)
tests/test_io.py:31:38: F541 f-string is missing placeholders
tests/test_util.py:5:52: W291 trailing whitespace
tests/test_util.py:10:1: F401 'qmkpy.checks' imported but unused
tests/test_util.py:18:26: E124 closing bracket does not match visual indentation
tests/test_util.py:28:1: E302 expected 2 blank lines, found 1
tests/test_util.py:29:80: E501 line too long (108 > 79 characters)
tests/test_util.py:30:80: E501 line too long (137 > 79 characters)
tests/test_util.py:31:80: E501 line too long (110 > 79 characters)
tests/test_util.py:32:26: E124 closing bracket does not match visual indentation
tests/test_util.py:42:80: E501 line too long (84 > 79 characters)
tests/test_util.py:44:1: E302 expected 2 blank lines, found 1
tests/test_util.py:49:26: E124 closing bracket does not match visual indentation
tests/test_util.py:56:80: E501 line too long (86 > 79 characters)
tests/test_util.py:60:1: E302 expected 2 blank lines, found 1
tests/test_util.py:61:80: E501 line too long (84 > 79 characters)
tests/test_util.py:62:80: E501 line too long (107 > 79 characters)
tests/test_util.py:63:80: E501 line too long (120 > 79 characters)
tests/test_util.py:64:80: E501 line too long (91 > 79 characters)
tests/test_util.py:65:26: E124 closing bracket does not match visual indentation
tests/test_util.py:72:80: E501 line too long (86 > 79 characters)
tests/test_util.py:87:18: E261 at least two spaces before inline comment
tests/test_util.py:92:1: E302 expected 2 blank lines, found 1
tests/test_util.py:101:18: E261 at least two spaces before inline comment
tests/test_util.py:106:1: E302 expected 2 blank lines, found 1
tests/test_util.py:116:9: F841 local variable '_objective' is assigned to but never used
tests/test_util.py:118:1: E302 expected 2 blank lines, found 1
tests/test_util.py:119:80: E501 line too long (97 > 79 characters)
tests/test_util.py:120:80: E501 line too long (87 > 79 characters)
tests/test_util.py:121:80: E501 line too long (98 > 79 characters)
tests/test_util.py:122:26: E124 closing bracket does not match visual indentation
tests/test_util.py:127:1: E302 expected 2 blank lines, found 1
tests/test_util.py:128:80: E501 line too long (97 > 79 characters)
tests/test_util.py:129:80: E501 line too long (87 > 79 characters)
tests/test_util.py:130:80: E501 line too long (98 > 79 characters)
tests/test_util.py:131:26: E124 closing bracket does not match visual indentation
tests/test_util.py:137:1: E302 expected 2 blank lines, found 1
tests/test_util.py:138:80: E501 line too long (97 > 79 characters)
tests/test_util.py:139:80: E501 line too long (87 > 79 characters)
tests/test_util.py:140:80: E501 line too long (98 > 79 characters)
tests/test_util.py:141:26: E124 closing bracket does not match visual indentation
tests/test_util.py:156:26: E124 closing bracket does not match visual indentation
tests/test_util.py:161:1: E302 expected 2 blank lines, found 1
tests/test_util.py:164:26: E124 closing bracket does not match visual indentation
tests/test_util.py:167:9: F841 local variable 'unassigned_items' is assigned to but never used
tests/test_util.py:175:26: E124 closing bracket does not match visual indentation
tests/test_util.py:180:1: E302 expected 2 blank lines, found 1
tests/test_util.py:185:26: E124 closing bracket does not match visual indentation
tests/test_util.py:190:1: E302 expected 2 blank lines, found 1
tests/test_util.py:195:26: E124 closing bracket does not match visual indentation
tests/test_util.py:198:9: F841 local variable 'empty_ks' is assigned to but never used
tests/test_util.py:200:1: E302 expected 2 blank lines, found 1
tests/test_util.py:205:26: E124 closing bracket does not match visual indentation
tests/test_util.py:206:80: E501 line too long (84 > 79 characters)
tests/test_util.py:208:9: F841 local variable 'empty_ks' is assigned to but never used
tests/test_util.py:210:1: E302 expected 2 blank lines, found 1
tests/test_util.py:213:26: E124 closing bracket does not match visual indentation
tests/test_util.py:216:9: F841 local variable 'empty_ks' is assigned to but never used
tests/test_util.py:220:80: E501 line too long (80 > 79 characters)
tests/test_util.py:221:80: E501 line too long (81 > 79 characters)
tests/test_util.py:222:80: E501 line too long (81 > 79 characters)
tests/test_util.py:223:80: E501 line too long (95 > 79 characters)
tests/test_util.py:224:26: E124 closing bracket does not match visual indentation
tests/test_util.py:229:1: E302 expected 2 blank lines, found 1
tests/test_util.py:234:26: E124 closing bracket does not match visual indentation
tests/test_util.py:235:80: E501 line too long (89 > 79 characters)
tests/test_algorithm_robin.py:22:80: E501 line too long (93 > 79 characters)
tests/test_algorithm_robin.py:24:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_robin.py:40:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_robin.py:44:80: E501 line too long (82 > 79 characters)
tests/test_algorithm_robin.py:57:9: F841 local variable 'solution' is assigned to but never used
tests/test_algorithm_robin.py:77:80: E501 line too long (91 > 79 characters)
tests/test_algorithm_robin.py:79:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_robin.py:92:9: F841 local variable 'solution' is assigned to but never used
tests/test_checks.py:6:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:16:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:21:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:26:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:38:24: E712 comparison to True should be 'if cond is True:' or 'if cond:'
tests/test_checks.py:40:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:50:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:62:24: E712 comparison to False should be 'if cond is False:' or 'if not cond:'
tests/test_checks.py:64:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:74:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:82:39: F841 local variable 'e_info' is assigned to but never used
tests/test_checks.py:83:9: F841 local variable 'is_feasible' is assigned to but never used
tests/test_checks.py:95:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:100:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:106:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:109:39: F841 local variable 'e_info' is assigned to but never used
tests/test_checks.py:114:1: E303 too many blank lines (3)
tests/test_checks.py:115:80: E501 line too long (91 > 79 characters)
tests/test_checks.py:119:80: E501 line too long (91 > 79 characters)
tests/test_checks.py:121:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:126:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:127:80: E501 line too long (91 > 79 characters)
tests/test_checks.py:130:80: E501 line too long (91 > 79 characters)
tests/test_checks.py:131:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:136:1: E302 expected 2 blank lines, found 1
tests/test_checks.py:137:80: E501 line too long (83 > 79 characters)
tests/test_checks.py:143:26: E124 closing bracket does not match visual indentation
tests/test_checks.py:146:9: F841 local variable 'symmetric' is assigned to but never used
tests/test_algorithm_cp.py:24:80: E501 line too long (93 > 79 characters)
tests/test_algorithm_cp.py:26:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_cp.py:42:1: E302 expected 2 blank lines, found 1
tests/test_algorithm_cp.py:46:80: E501 line too long (82 > 79 characters)
tests/test_algorithm_cp.py:58:9: F841 local variable 'solution' is assigned to but never used
tests/test_algorithm_cp.py:59:80: E501 line too long (82 > 79 characters)
tests/test_algorithms.py:10:80: E501 line too long (81 > 79 characters)
tests/test_algorithms.py:12:1: E302 expected 2 blank lines, found 1
tests/test_algorithms.py:39:1: E302 expected 2 blank lines, found 1
tests/test_algorithms.py:53:1: E302 expected 2 blank lines, found 1
tests/test_algorithms.py:58:5: F841 local variable 'num_knapsacks' is assigned to but never used

Errors/problems in mathematical descriptions

In the doc welcome page and in the readme.md, the following needs fixing/clarification:

  • Are the p_i and p_ij, positive integers or positive reals? Or, are there no restrictions on these values?
  • Similar comment on the weight capacities c_u, and the weights w_i?
  • u in the set script K; we assume K is some set of indices? Is this set finite?
  • i in sets script A_u -- we assume these are indexed sets of indices? Finite?
  • If i comes from script A_u, then are the values in the A_u different for different u's in script K? Otherwise, it seems that the profits p_i are somehow shared between knapsacks? Is this intentional? In which case, why are there separate joint profits p_ij?
  • Similarly for the w_i: is there just one set of weights indexed by the values in A_u? In which case weights are shared among knapsacks?
  • In the final summation in the constraint, the limits should just be u in script K, as it is with the other summations?
  • Since the a_iu are zero-one values, actually, this package only addresses zero-one knapsack problems, rather than integer knapsack problems, right? In which case, this should be made clear in the title, description of the package etc.
  • The readme.md and the doc welcome page use different notation e.g. A(u) rather than A_u, this should be made consistent across the entire documentation.
  • The explanation for the variables in the mathematical description in the readme.md are entirely missing and need to be included.
  • In the readme.md, the description under the equations is wrong, it should have script K rather than K.
  • In both doc welcome page and readme.md: write forall i in 1,2,..,N rather than forall 1<=i<=N.

Add your Community Guidelines

Please add your community guidelines at the end of the README.md
This can be boilerplate stuff.

Address the following:

  1. Contribute to the software
  2. Report issues or problems with the software
  3. Seek support

Boilerplate example

...
### Contributing
Please contribute using [Github Flow](https://guides.github.com/introduction/flow/). Create a branch, add commits, and [open a pull request](https://github.com/yourname/yourreponame/compare/).

Very "thin" review of the area e.g. missing exact solver examples?

The paper review is pretty shallow on this extensive topic, e.g. just a simple search on Wikipedia provides multiple references and pointers:
https://en.wikipedia.org/wiki/Quadratic_knapsack_problem

For instance, as with the standard knapsack, there are exact (quasi-polynomial time) dynamic programming and branch-and-bound methods. It would be very helpful to review these in the paper and provide an example implementation, for comparison.

State of the field - Please other software that deals with QKP problems or related problems

In your paper https://github.com/klb2/qmkpy/blob/joss-paper/paper/paper.md you should mention other software. Think of it as a literature review to find their drawbacks that are fixed by your software.

  1. What other software for QKP exists? (Is there anything in Gurobi, SCIP, CPLEX, or some old papers with super old F or C code?)
  2. What are today's or your software requirements (e.g., you are targeting python users, you need an OSS licensed software, adaptability for new algorithm ideas)
  3. Write your paper text

Naming of terms

Although the knapsack problem is well-known, the choice of the terms "profit" is unusual. I would suggest "value" instead, because maximizing value under weight constraints is usually how knapsack problems are described.

Very "thin" review of the area e.g. missing exact solver examples? #17

"While many solution algorithms are proposed in the literature, the primary goal of the framework is to provide a testbed environment for researchers and developers working in that area to quickly implement and share their novel solutions."

OK, so, I think the appropriate solution would be to make this very clear in the title of the package: i.e. it is not a package providing solutions for the quadratic multiple knapsack problem, it is a package providing a testbed for the development and testing of quadratic multiple knapsack algorithms. Otherwise the package name and title are quite misleading.

Improve description of the package.

It isn't really made sufficiently clear the purpose of this package. It is not a package for solving the zero-one QMKP per se, rather, it is a package containing a testbed for developing novel zero-one QMKP solver algorithms. This needs to be made much clearer, in the paper, the readme, and the documentation.

Can I use it package to solve quadratic knapsack problem?

I want to solve the Quadratic Knapsack problem and the weights of all items are the same. How efficient it is to use this package to solve that problem? will it be equipped with the latest solver for QKP or it is mainly for QMKP?

Substantial inconsistencies between documented mathematical description and code

  • In the "basic arrays" part of the documentation, the "profits" variable is stated as an NxN array. But in the documentation, the mathematical description is i in A_u, i.e. an arbitrary set of indices. It seems that the only consistent description is that A_u is actually an array of integers. But then the documented mathematical description should just say this.
  • Similarly with the weights and capacities variables.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.