Optimize holds queue building using the Hungarian Algorithm

Optimize holds queue building using the Hungarian Algorithm

Status:	Under development
Sponsored by:	yes
Developed by:	Andreas Jonsson <andreas.jonsson@kreablo.se>
Expected for:	2024-01-17
Bug number:	Bug 35826
Work in progress repository:
Description:	There are several problems when building the holds queue which makes it hard for the libraries to predict the outcome for how items are allocated based on their configured policy.

Problem

There are several problems when building the holds queue which makes it hard for the libraries to predict the outcome for how items are allocated based on their configured policy.

1. The allocation of items should be done by optimizing on transport cost. Currently a greedy algorithm is applied when building the holds queue which doesn't always produce optimal results.
2. The allocation of items should not fall back to some default allocation if an allocation by using the transport cost matrix fails. If no allocation can be found that satisfies the configured constraints it is a violation of the configured policies to proceed with an allocation.

3. Although items at the local library have transport cost 0, assigning local items should not be given absolute precedence. It is simply false that assigning local items "is obviously the least costly" as the comment says.

   (That we hard code the cost to 0 for local items is also an arbitrary restriction in Koha, there is no technical reason as to why we shouldn't allow the libraries to set a cost for allocating local items.)

Solution

The Hungarian algorithm, also known as the Munkres algorithm, assigns agents to task, where each there is a cost of each agent/task pairing. In the context of building the holds queue the agents are the items available and the tasks are the holds that needs to be filled and the cost is determined by the transport cost matrix. The runtime complexity is O(min(H, I)² x I) where H is the number of holds that needs to be filled and I is the number of items available.

The Hungarian algorithm may at first seem to have some restrictions that makes it impractical: 1. the cost matrix must be a square 2. the weights must be integers 3. all pairs of agents/tasks must have a finite cost. However, after a deeper analysis I have concluded that these restrictions aren't a problem:

1. When applying the Hungarian algorithm on a non-square matrix the result is precisely what you expect: an optimal pairing is done for the agents or tasks that are available, while the remaining agents or tasks remains unallocated. When pairing items with holds it makes sense to input all available items to the algorithm even if there are fewer holds waiting to be filled, but not the other way around, as this would mean that newer holds in the queue would skip ahead if the transport cost is lower. There is an implementation available for Perl (https://metacpan.org/pod/Algorithm::Munkres) that unfortunately performs a zero-padding to produce a square cost matrix when inputted a non-squared one. With zero-padding, excess items are allocated to non-existing holds, whereas operating directly on a non-square matrix just sets the allocations of non-existing items to an undefined hold. The important thing is that it is possible to identify which assignments are valid assignments, which is possible both with and without zero-padding. But zero-padding always produce an NxN matrix if there are N available items, even if there is only a single hold to fill, which is unnecessary. But Algorithm::Munkres version 0.08 is established both as a CPAN-module and as is distributed with both Debian and Ubuntu. So it is tempting to just use this package even if the performance isn't optimal, although I have made an updated version which does not zero-pad.
2. The justification for restricting the costs to integers seems based in a worry about rounding errors potentially causing comparison to 0 to fail, which would result in the algorithm never terminating. However, the algorithm gradually subtracts the smallest weight from the weights in the cost matrix to produce a value that is 0. This means that the subtractions that are expected to produce 0 are the result of subtracting the exact value of a weight with itself so the result must be exactly 0 even in floating point arithmetic. So, this restriction is bogus.

3. The transport cost matrix can be configured to disallow certain item transfers. Also circulation rules and branch transfer restrictions may prohibit the allocation of a certain item to a certain hold. We can say that the transport cost of such allocations is infinite. IEEE-754 does allow for the value "infinity", but we cannot use this as a cost because the algorithm would not terminate if there is no finite cost solution.

   But infinity can instead be represented by a value that is larger than any sum of finite cost assignments. Then any possible finite cost assignments will be selected before any infinite cost assignment. We could even use different large values to represent infinity in order to bias the selection of infinite cost holds towards the end of the queue. Otherwise the algorithm may reach a point where several infinite cost assignments are considered simultaneously with no particular preference. To be specific, let M be the largest cost in the cost matrix and H the number of holds that we are trying to fill.  We can choose a base value for representing infinity INF = M x H + 1 (which clearly is larger than any possible total cost).  We can then represent infinite costs (if any) for the hold h[i] with the value INF + (H - i) x C, where C is a constant value and i is the hold h's position in the queue. The constant C could be said to specify how much higher the total cost of an assignment can be before preferring to not fill hold h[i] rather than not filling h[i+1] if both cannot be filled. If C = 0, then no preference would be given to an assignment where h[i] is filled over one where h[i+1] is filled if both assignments would have the same total cost. If C = INF an assignment that fills h[i] is always preferred over one that fills h[i+1] if not both can be filled, no matter how much higher the total (finite) cost would be.

   Items that cannot be assigned to fill any current hold and holds that cannot be filled by any available item should have been sorted out before applying the algorithm, so there must be at least one item that can be assigned to one hold, and it would be unsatisfying if the algorithm failed to produce any allowed item assignment at all.

   The infinite cost assignments can be identified by the high cost and removed from the solution afterwards.

   If there are additional holds available that needs to be filled after removing infinite cost assignments, we could replace the removed holds with newer holds and rerun the algorithm. This would, however, worsen the worst case runtime complexity of the algorithm to O(min(H, I)² x H x (H - I)) so it might not be worthwhile. It might be a reasonable trade-off to limit the number of reruns to some arbitrary constant, though.