qmkpy.algorithms module
Solution algorithms for the QMKP.
This module contains all the algorithms that can be used to solve the quadratic multiple knapsack problem (QMKP).
- qmkpy.algorithms.constructive_procedure(profits: array, weights: Iterable[float], capacities: Iterable[float], starting_assignment: Optional[array] = None) array
Constructive procedure that completes a starting assignment
This constructive procedure is based on Algorithm 1 from [AGH22] and the greedy heuristic in [HJ06]. It is a greedy algorithm that completes a partial solution of the QMKP.
- 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.capacities (
list
offloat
) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined asK=len(capacities)
.starting_assignments (
np.array
, optional) – Binary matrix of size \(N\times K\) which represents existing starting assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). These assignments are not modified and will only be completed. If it is None, no existing assignment is assumed.
- 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
- Raises
ValueError – Raises a
ValueError
if the starting assignment is infeasible.
- qmkpy.algorithms.fcs_procedure(profits: array, weights: Iterable[float], capacities: Iterable[float], alpha: Optional[float] = None, len_history: int = 50) array
Implementation of the fix and complete solution (FCS) procedure
This fix and complete solution (FCS) procedure is based on Algorithm 2 from [AGH22]. It is basically a stochastic hill-climber wrapper around the constructive procedure
constructive_procedure()
(also see [HJ06]).- 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.capacities (
list
offloat
) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined asK=len(capacities)
.alpha (
float
, optional) – Float between 0 and 1 that indicates the ratio of assignments that should be dropped in an iteration. If not provided, a uniformly random value is chosen.len_history (
int
, optional) – Number of consecutive iterations without any improvement before the algorithm terminates.
- 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.algorithms.random_assignment(profits: array, weights: Iterable[float], capacities: Iterable[float]) array
Generate a random (feasible) assignment
This function generates a random feasible solution to the specified QMKP. The algorithm works as follows
Generate a random permutation of the items
For each item \(i\) do
Determine the possible knapsacks \(\mathcal{K}_i\) that could support the item
Random and uniformly select a choice from \(\mathcal{K}_i \cup \{\text{skip}\}\).
This way, a feasible solution is generated without the guarantee that every item is assigned (even if it could still be assigned).
- 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}\).weights (
list
) – List of weights \(w_i\) of the \(N\) items that can be assigned.capacities (
list
) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined asK=len(capacities)
.
- 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.algorithms.round_robin(profits: array, weights: Iterable[float], capacities: Iterable[float], starting_assignment: Optional[array] = None, order_ks: Optional[Iterable[int]] = None) array
Simple round-robin algorithm
This algorithm follows a simple round-robin scheme to assign items to knapsacks. The knapsacks are iterated in the order provided by
order_ks
. In each round, the current knapsack selects the item with the highest value density that still fits in the knapsack.- 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.capacities (
list
offloat
) – Capacities of the knapsacks. The number of knapsacks \(K\) is determined asK=len(capacities)
.starting_assignments (
np.array
, optional) – Binary matrix of size \(N\times K\) which represents existing starting assignments of items to knapsacks. If \(a_{ij}=1\), element \(i\) is assigned to knapsack \(j\). These assignments are not modified and will only be completed. If it is None, no existing assignment is assumed.order_ks (
list
ofint
, optional) – Order in which the knapsacks select the items. If none is given, they are iterated by index, i.e.,order_ks = range(num_ks)
.
- 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