# 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