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
orlist
ofint
) – Chromosome version ofassignments
, 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
orlist
ofint
) – 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
ofint
- 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
offloat
) – List of weights \(w_i\) of the \(N\) items that can be assigned.capacities (
list
offloat
) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined asK=len(capacities)
.assignments (
np.array
orlist
ofint
) – 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
offloat
- 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
orlist
ofint
) – 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
ofint
- 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 toTrue
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
offloat
) – List of weights \(w_i\) of the \(N\) items that can be assigned.assignments (
np.array
orlist
ofint
) – 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 toTrue
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\), ifreduced_output
isFalse
. Ifreduced_output
isTrue
, the return has lengthlen(densities)==len(unassigned_items)
. The number of dimensions is equal to the number of dimensions ofassignments
. 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 whenreduced_output
is set toTrue
.