qmkpy.qmkp module
General definitions of the quadratic multiple knapsack problem.
This module contains the basic implementation of the quadratic multiple
knapsack problem (QMKP).
In particular, this includes the base class QMKProblem
.
- class qmkpy.qmkp.QMKProblem(profits: Union[array, Iterable[Iterable]], weights: Iterable[float], capacities: Iterable[float], algorithm: Optional[Callable] = None, args: Optional[tuple] = None, assignments: Optional[array] = None, name: Optional[str] = None)
Bases:
object
Base class to represent a quadratic multiple knapsack problem.
This class defines a standard QMKP with \(N\) items and \(K\) knapsacks.
- profits
Symmetric matrix of size \(N\times N\) that contains the (joint) profit values \(p_{ij}\). The profit of the single items \(p_i\) corresponds to the main diagonal elements, i.e., \(p_i = p_{ii}\).
- Type
np.array
- weights
List of weights \(w_i\) of the \(N\) items that can be assigned.
- Type
list
offloat
- capacities
Capacities of the knapsacks. The number of knapsacks \(K\) is determined as
K=len(capacities)
.- Type
list
offloat
- algorithm
Function that is used to solve the QMKP. It needs to follow the argument order
algorithm(profits, weights, capacities, ...)
.- Type
Callable
, optional
- assignments
Binary matrix of size \(N\times K\) which represents the final assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). This attribute is overwritten when calling
solve()
.- Type
np.array
, optional
- name
Optional name of the problem instance
- Type
str
, optional
- classmethod load(fname: str, strategy: str = 'numpy')
Load a QMKProblem instance
This functions allows loading a previously saved QMKProblem instance. The
save()
method provides a way of saving a problem.See also
save()
Method to save a QMKProblem instance which can then be loaded.
- Parameters
fname (
str
) – Filepath of the saved modelstrategy (
str
) –Strategy that is used to store the model. Valid choices are (case-insensitive):
numpy
: Save the individual arrays of the model using thenp.savez_compressed()
function.pickle
: Save the whole object using Pythonspickle
moduletxt
: Save the arrays of the model using the text-based format established by Billionnet and Soutif.json
: Save the arrays of the model using the JSON format.
- Returns
problem – Loaded problem instance
- Return type
- save(fname: Union[str, bytes, PathLike], strategy: str = 'numpy') NoReturn
Save the QMKP instance
Save the profits, weights, and capacities of the problem. There exist different strategies that are explained in the
strategy
parameter.See also
load()
For loading a saved model.
- Parameters
fname (
str
orPathLike
) – Filepath of the model to be saved atstrategy (
str
) –Strategy that is used to store the model. Valid choices are (case-insensitive):
numpy
: Save the individual arrays of the model using thenp.savez_compressed()
function. See alsoqmkpy.io.save_problem_numpy()
.pickle
: Save the whole object using Pythonspickle
module. See alsoqmkpy.io.save_problem_pickle()
.txt
: Save the arrays of the model using the text-based format established by Billionnet and Soutif. See alsoqmkpy.io.save_problem_txt()
.json
: Save the arrays of the model using the JSON format.
- Return type
None
- solve(algorithm: Optional[Callable] = None, args: Optional[tuple] = None) Tuple[array, float]
Solve the QMKP
Solve the QMKP using
algorithm
. This function both returns the optimal assignment and the total resulting profit. This method also automatically sets the solution to the object’s attributeassignments
.- Parameters
algorithm (
Callable
, optional) – Function that is used to solve the QMKP. It needs to follow the argument orderalgorithm(profits, weights, capacities, ...)
. If it isNone
, the object attributealgorithm
is used.args (
tuple
, optional) – Optional tuple of additional arguments that are passed toalgorithm
. If it isNone
, the object attributeargs
is used.
- Returns
assignments (
np.array
) – Binary matrix of size \(N\times K\) which represents the final assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\).total_profit (
float
) – Final total profit for the found solution.
- qmkpy.qmkp.total_profit_qmkp(profits: array, assignments: array) float
Calculate the total profit for given assignments.
This function calculates the total profit of a QMKP for a given profit matrix \(P\) and assignments \(\mathcal{A}\) as
\[\begin{split}\sum_{u=1}^{K}\left(\sum_{i\in\mathcal{A}_u} p_{i} + \sum_{\substack{j\in\mathcal{A}_u\\j\neq i}} p_{ij}\right)\end{split}\]where \(\mathcal{A}_{u}\) is the set of items that are assigned to knapsack \(u\).
- Parameters
profits (
np.array
) – Symmetric matrix of size \(N\times N\) that contains the (joint) profit values \(p_{ij}\). The profit of the single items \(p_i\) corresponds to the main diagonal elements, i.e., \(p_i = p_{ii}\).assignments (
np.array
) – Binary matrix of size \(N\times K\) which represents the final assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\).
- Returns
Value of the total profit
- Return type
float