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 of float

capacities

Capacities of the knapsacks. The number of knapsacks \(K\) is determined as K=len(capacities).

Type

list of float

algorithm

Function that is used to solve the QMKP. It needs to follow the argument order algorithm(profits, weights, capacities, ...).

Type

Callable, optional

args

Optional tuple of additional arguments that are passed to algorithm.

Type

tuple, 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 model

• strategy (str) –

  Strategy that is used to store the model. Valid choices are (case-insensitive):

  • numpy: Save the individual arrays of the model using the np.savez_compressed() function.

  • pickle: Save the whole object using Pythons pickle module

  • txt: 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

QMKProblem

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 or PathLike) – Filepath of the model to be saved at

• strategy (str) –

  Strategy that is used to store the model. Valid choices are (case-insensitive):

  • numpy: Save the individual arrays of the model using the np.savez_compressed() function. See also qmkpy.io.save_problem_numpy().

  • pickle: Save the whole object using Pythons pickle module. See also qmkpy.io.save_problem_pickle().

  • txt: Save the arrays of the model using the text-based format established by Billionnet and Soutif. See also qmkpy.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 attribute assignments.

Parameters

• algorithm (Callable, optional) – Function that is used to solve the QMKP. It needs to follow the argument order algorithm(profits, weights, capacities, ...). If it is None, the object attribute algorithm is used.

• args (tuple, optional) – Optional tuple of additional arguments that are passed to algorithm. If it is None, the object attribute args 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