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