qmkpy package

Module contents

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

chromosome_from_assignment(): For more details on the connection between assignment matrix and chromosome.

Parameters

chromosome (np.array or list of int) – Chromosome version of assignments, which is a list of length \(N\) where \(c_{i}=k\) means that item \(i\) is assigned to knapsack \(k\). If the item is not assigned, we set \(c_{i}=-1\).
num_ks (int) – Number of knapsacks \(K\).

Returns

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

Return type

np.array

qmkpy.chromosome_from_assignment(assignments: array) → Iterable[int]

Return the chromosome from an assignment matrix

The chromosome version of assignments is a list of length \(N\) where \(c_{i}=k\) means that item \(i\) is assigned to knapsack \(k\). If the item is not assigned, we set \(c_{i}=-1\).

Example

Assume that we have 4 items and 3 knapsacks. Let Items 1 and 4 be assigned to Knapsack 1, Item 2 is assigned to Knapsack 3 and Item 3 is not assigned. In the binary representation, this is

\[\begin{split}A = \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0\\ 1 & 0 & 0 \end{pmatrix}\end{split}\]

The corresponding chromosome is

\[C(A) = \begin{pmatrix}1 & 3 & 0 & 1\end{pmatrix}\]

However, in the 0-index based representation in Python, this function will return

chromosome_from_assignment(A) = [0, 2, -1, 0]

as the chromosome.

Parameters: 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: chromosome – Chromosome version of assignments, which is a list of length \(N\) where \(c_{i}=k\) means that item \(i\) is assigned to knapsack \(k\). If the item is not assigned, we set \(c_{i}=-1\).
Return type: np.array

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

qmkpy.value_density(profits: array, weights: Iterable[float], assignments: Union[array, Iterable[int]], reduced_output: bool = False) → Iterable[float]

Calculate the value density given a set of selected objects.

This function calculates the value density of item \(i\) for knapsack \(k\) and given assignments \(\mathcal{A}_k\) according to

\[\begin{split}\mathrm{vd}_i(\mathcal{A}_k) = \frac{1}{w_i} \left(p_i + \sum_{\substack{j\in\mathcal{A}_k\\j\neq i}} p_{ij} \right)\end{split}\]

This value indicates the profit (per item weight) that is gained by adding the item \(i\) to knapsack \(k\) when the items \(\mathcal{A}_k\) are already assigned. It is adapted from the notion of the value density from (Hiley, Julstrom, 2006).

When a full array of assignements is used as input, a full array of value densities is returned as

\[\begin{split}\mathrm{vd}(\mathcal{A}) = \begin{pmatrix} \mathrm{vd}_1(\mathcal{A}_1) & \mathrm{vd}_1(\mathcal{A}_2) & \cdots & \mathrm{vd}_1(\mathcal{A}_K)\\ \mathrm{vd}_2(\mathcal{A}_1) & \mathrm{vd}_2(\mathcal{A}_2) & \cdots & \mathrm{vd}_2(\mathcal{A}_K)\\ \vdots & \cdots & \ddots & \vdots \\ \mathrm{vd}_N(\mathcal{A}_1) & \mathrm{vd}_N(\mathcal{A}_2) & \cdots & \mathrm{vd}_N(\mathcal{A}_K) \end{pmatrix}\end{split}\]

When the parameter reduced_output is set to True only a subset with the values of the unassigned items is returned.

Parameters

profits (np.array) – Symmetric matrix of size \(N\times N\) that contains the (joint) profit values \(p_{ij}\).
weights (list of float) – List of weights \(w_i\) of the \(N\) items that can be assigned.
assignments (np.array or list of int) – 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\). Alternatively, one can provide a list of the indices of selected items. In this case, it is assumed that these items are assigned to all knapsacks.
reduced_output (bool, optional) – If set to True only the value density values of the unassigned objects are returned. Additionally, the indices of the unassigned items are returned as a second output.

Returns

densities (np.array) – Array that contains the value densities of the objects. The length is equal to \(N\), if reduced_output is False. If reduced_output is True, the return has length len(densities)==len(unassigned_items). The number of dimensions is equal to the number of dimensions of assignments. Each column corresponds to a knapsack. If only a flat array is used as input, a flat array is returned.
unassigned_items (list) – List of the indices of the unassigned items. This is only returned when reduced_output is set to True.

qmkpy package

Submodules

Module contents