qmkpy.util module

Utility functions.

This module contains various utility functions, e.g., the conversion from the binary assignment matrix to the chromosome form.

qmkpy.util.assignment_from_chromosome(chromosome: Iterable[int], num_ks: int) → array

Return the assignment matrix from a chromosome

Return the binary assignment matrix that corresponds to the chromosome. For more details about the connection between assignment matrix and chromosome check chromosome_from_assignment().

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.util.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.util.get_empty_knapsacks(assignments: Union[array, Iterable[int]], num_ks: Optional[int] = None) → Iterable[int]

Return the list of empty knapsacks

Return the list of empty knapsacks (as their indices) from a given assignment. An empty knapsack is one without any assigned item. The assignments can be either in the binary matrix form or in the chromosome form. If the chromosome form is used, the total number of knapsacks needs to be additionally provided.

Parameters

assignments (np.array or list of int) – Either a binary matrix of size \(N\times K\) which represents the assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). Or assignments in the chromosome form, 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 (optional)) – Total number \(K\) of knapsacks. This only needs to provided, if the assignments are given in the chromosome form.

Returns

empty_ks – List of the indices of the empty knapsacks.

Return type

list of int

qmkpy.util.get_remaining_capacities(weights: Iterable[float], capacities: Iterable[float], assignments: Union[array, Iterable[int]])

Return the remaining weight capacities of the knapsacks

Returns the remaining weight capacities of the knapsacks for given assignments. The function does not raise an error when a weight constraint is violated but will return a negative remaining capacity in this case.

Parameters

weights (list of float) – List of weights \(w_i\) of the \(N\) items that can be assigned.
capacities (list of float) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined as K=len(capacities).
assignments (np.array or list of int) – Either a binary matrix of size \(N\times K\) which represents the assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). Or assignments in the chromosome form, 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\).

Returns

remaining_capacities – List of the remaining capacities. Can be negative, if a knapsack is overloaded.

Return type

list of float

qmkpy.util.get_unassigned_items(assignments: Union[array, Iterable[int]]) → Iterable[int]

Return the list of unassigned items

Return the list of unassigned items (as their indices) from a given assignment. It can be either in the binary matrix form or in the chromosome form.

Parameters: assignments (np.array or list of int) – Either a binary matrix of size \(N\times K\) which represents the assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). Or assignments in the chromosome form, 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\).
Returns: unassigned_items – List of the indices of the unassigned items.
Return type: list of int

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