klb2
commented
1 year ago Hi. Thank you for your interest in the qmkpy package.
Yes, you can use it to solve the quadratic knapsack problem (QKP). Since it is a special case of the QMKP, you can simply set the number of knapsacks to one and use the package. All solvers, which are currently implemented with this package, can be used for the QKP. You can also easily implement your own solution algorithm. A description can be found in the documentation at https://qmkpy.readthedocs.io/en/latest/developing.html
A code example could look like the following
import numpy as np
from qmkpy import total_profit_qmkp, QMKProblem
from qmkpy import algorithms
from qmkpy import util
num_items = 10
weight = 5
weights = weight*np.ones(num_items) # all items have the same weight
capacities = [25] # single knapsack with capacity 25
_profits = 3*np.random.rand(num_items, num_items)
profits = _profits @ _profits.T # symmetric profit matrix
qmkp = QMKProblem(profits, weights, capacities)
qmkp.algorithm = algorithms.constructive_procedure # you could replace this function with your own solver
assignments, total_profit = qmkp.solve()
print(f"Solution (assignments):\n{assignments}")
print(f"Total profit with this solution: {total_profit:.2f}")
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?