search

klb2 / qmkpy

Python testbed for the Quadratic Multiple Knapsack Problem (QMKP)
https://qmkpy.readthedocs.io
GNU General Public License v3.0
8 stars 2 forks source link

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

Closed max-little closed 2 years ago

max-little commented 2 years ago

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.

jbytecode commented 2 years ago

Due to JOSS submission: https://github.com/openjournals/joss-reviews/issues/4718

klb2 commented 2 years ago

The mentioned Wikipedia article refers to the quadratic single knapsack problem. Most solution algorithms are not directly applicable to the quadratic multiple knapsack problem that is considered in the QMKPy framework. We added this remark to the paper in f8ec4a13a84bb8afad697460ad95d4c5e3b506d3.

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. Therefore, we feel that it is not necessary to provide a comprehensive collection of many algorithms in the initial version of QMKPy. However, there are still already four different algorithms available in version 1.1 for a baseline comparison.