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

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

  • 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

  1. Generate a random permutation of the items

  2. For each item \(i\) do

    1. Determine the possible knapsacks \(\mathcal{K}_i\) that could support the item

    2. 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 as K=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 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).

  • 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 of int, 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