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 o proceed and make 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.) I am currently working on a solution based on the Hungarian Algorithm.
Created RFC: https://wiki.koha-community.org/wiki/Optimize_holds_queue_building_using_the_Hungarian_Algorithm
(In reply to Andreas Jonsson from comment #1) > Created RFC: > https://wiki.koha-community.org/wiki/ > Optimize_holds_queue_building_using_the_Hungarian_Algorithm This all looks really great but I'm worried about: 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. I think the implication here is we must find the holdabilty of each item for each hold before we assign items to holds. I think that makes our current greedy algorithm at worst compares the first hold to all items, the second hold to all items less one, the third hold to all items less two and so forth. I tried to write the big O for these and mangled them so bad I thought it best to leave them out :) If I am correct about this, I think we need to retain the option to use the greedy algorithm. Did I miss something?
Provided that all rows with all values being "infinity" and all columns with all values being "infinity" is removed from the cost matrix beforehand and there's still something left in the matrix, then there must exist at least one pairing with finite cost that the algorithm will produce as result. And if the matrix is empty the greedy algorithm wouldn't find any allocations either. So, I'd say that we do not need the greedy algorithm. I think that my reasoning about different values to represent infinity was a bit confused. If a single large constant is used to represent infinity the result of the algorithm will still maximize the number of finite valued pairings, provided that the value representing infinity is larger than the total cost of any finite cost assignment. It might still be a good idea to use different values to represent infinity to prefer not filling holds towards the end of the queue if not all holds can be filled.
(In reply to Andreas Jonsson from comment #3) > Provided that all rows with all values being "infinity" and all columns with > all values being "infinity" is removed from the cost matrix beforehand and > there's still something left in the matrix, then there must exist at least > one pairing with finite cost that the algorithm will produce as result. > > And if the matrix is empty the greedy algorithm wouldn't find any > allocations either. > > So, I'd say that we do not need the greedy algorithm. > > I think that my reasoning about different values to represent infinity was a > bit confused. If a single large constant is used to represent infinity the > result of the algorithm will still maximize the number of finite valued > pairings, provided that the value representing infinity is larger than the > total cost of any finite cost assignment. It might still be a good idea to > use different values to represent infinity to prefer not filling holds > towards the end of the queue if not all holds can be filled. Sounds good to me!
Created attachment 161373 [details] [review] Bug 35826: optimize on transport cost when building holds queue
Can you publish a branch somewhere? Apply? [(y)es, (n)o, (i)nteractive] y Applying: Bug 35826: optimize on transport cost when building holds queue error: sha1 information is lacking or useless (C4/HoldsQueue.pm). error: could not build fake ancestor Patch failed at 0001 Bug 35826: optimize on transport cost when building holds queue hint: Use 'git am --show-current-patch=diff' to see the failed patch When you have resolved this problem run "git bz apply --continue". If you would prefer to skip this patch, instead run "git bz apply --skip". To restore the original branch and stop patching run "git bz apply --abort".
Sure: https://github.com/Kreablo/Koha/tree/feature-optimize-holds-queue-with-transport-cost-matrix
kohadev-koha@kohadevbox:koha((24874c76354...))$ hyperfine --warmup 3 --runs 100 'perl t/db_dependent/HoldsQueue.t' Benchmark 1: perl t/db_dependent/HoldsQueue.t Time (mean ± σ): 4.009 s ± 0.709 s [User: 3.218 s, System: 0.481 s] Range (min … max): 3.412 s … 5.955 s 100 runs kohadev-koha@kohadevbox:koha((24874c76354...))$ hyperfine --warmup 3 --runs 100 'perl t/db_dependent/HoldsQueue.t' Benchmark 1: perl t/db_dependent/HoldsQueue.t Time (mean ± σ): 4.193 s ± 0.798 s [User: 3.356 s, System: 0.510 s] Range (min … max): 3.449 s … 6.049 s 100 runs Not sure if we can consider HoldsQueue.t as representative of anything real world, but it does indicate performance is only slightly affected.
I have done some profiling using real library data from region libraries and the algorithm itself cannot even be seen in the flame graph. It is the setup that is costly. The setup is more costly because we are making an exhaustive search for the optimal solution. With the greedy method we don't check the restrictions beetween each hold-item pair. Memoizing validate_hold_sibling and can_be_transferred would speed up the process.
What is needed for discussion here?
I have created an RFC: https://wiki.koha-community.org/wiki/Optimize_holds_queue_building_using_the_Hungarian_Algorithm The discussion is on whether the community thinks that this is a worthwhile solution or not.
Created attachment 161956 [details] [review] Bug 35826: Fix errors in transport cost optimization
(In reply to Andreas Jonsson from comment #11) > I have created an RFC: > https://wiki.koha-community.org/wiki/ > Optimize_holds_queue_building_using_the_Hungarian_Algorithm > > The discussion is on whether the community thinks that this is a worthwhile > solution or not. I'm going to go out on a limb and say that this is absolutely worthwhile. If anyone disagrees please let us know!
More benchmarks: build_holds_queue.pl with 3364 holds ( no tcm ) Master: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.447 s ± 0.678 s [User: 4.801 s, System: 0.196 s] Range (min … max): 5.674 s … 7.588 s 10 runs Bug 35826: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.745 s ± 0.750 s [User: 4.962 s, System: 0.209 s] Range (min … max): 6.081 s … 8.219 s 10 runs build_holds_queue.pl with 3364 holds ( with tcm ) Master: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.805 s ± 0.625 s [User: 4.977 s, System: 0.232 s] Range (min … max): 6.046 s … 8.098 s 10 runs Bug 35826: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.931 s ± 0.746 s [User: 5.142 s, System: 0.216 s] Range (min … max): 5.715 s … 7.903 s 10 runs build_holds_queue.pl with 6614 holds ( with tcm ) Master:: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.991 s ± 0.545 s [User: 5.069 s, System: 0.219 s] Range (min … max): 6.529 s … 7.877 s 10 runs Bug 35826: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 7.222 s ± 0.955 s [User: 5.341 s, System: 0.234 s] Range (min … max): 5.977 s … 8.636 s 10 runs build_holds_queue.pl with 9470 holds ( with tcm ) Master: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 7.345 s ± 0.760 s [User: 5.410 s, System: 0.261 s] Range (min … max): 6.227 s … 8.432 s 10 runs Bug 35826: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.871 s ± 0.881 s [User: 5.056 s, System: 0.210 s] Range (min … max): 5.937 s … 8.221 s 10 runs build_holds_queue.pl with 17159 holds ( with tcm ) Master: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 6.862 s ± 0.643 s [User: 4.869 s, System: 0.194 s] Range (min … max): 6.034 s … 8.365 s 10 runs Bug 35826: ./misc/cronjobs/holds/build_holds_queue.pl Time (mean ± σ): 7.207 s ± 0.555 s [User: 5.132 s, System: 0.219 s] Range (min … max): 6.081 s … 7.833 s 10 runs Will run with some production data next
Tests with production data from a large library with 61661 holds on 218573 records with 1798064 items: kohadev-koha@kohadevbox:koha((fee4368cd81...))$ git checkout origin/master; hyperfine --warmup 3 --runs 10 "./misc/cronjobs/holds/build_holds_queue.pl --force"; git checkout bug35826-qa; hyperfine --warmup 3 --runs 10 "./misc/cronjobs/holds/build_holds_queue.pl --force" HEAD is now at fee4368cd81 Bug 35930: Add guards for plugins_enabled Benchmark 1: ./misc/cronjobs/holds/build_holds_queue.pl --force Time (mean ± σ): 43.093 s ± 3.282 s [User: 33.352 s, System: 1.129 s] Range (min … max): 38.749 s … 49.173 s 10 runs Previous HEAD position was fee4368cd81 Bug 35930: Add guards for plugins_enabled Switched to branch 'bug35826-qa' Your branch is ahead of 'origin/master' by 2 commits. (use "git push" to publish your local commits) Benchmark 1: ./misc/cronjobs/holds/build_holds_queue.pl --force Time (mean ± σ): 42.098 s ± 2.568 s [User: 32.566 s, System: 1.026 s] Range (min … max): 37.995 s … 45.096 s 10 runs TLDR: With real world data, not only should it route items more efficiently, it appears to be slightly faster then our current code
*** Bug 33796 has been marked as a duplicate of this bug. ***
Is there a test plan for this?
(In reply to George Williams (NEKLS) from comment #17) > Is there a test plan for this? I would say the test plan would be something along the lines of: 1) Enable the Transport Cost Matrix, set your values how you see fit 2) Place a number of holds on a number of records 3) Build the holds queue 4) Inspect what items were targeted to what holds
We have been running this in a test system of a large coalition of regional Libraries, but I think that we need a collection of unit tests to sufficiently test all aspects. It is too tedious to manually walk through all possible scenarios. I will try to find some more time to work on this.
(In reply to Andreas Jonsson from comment #19) > We have been running this in a test system of a large coalition of regional > Libraries, but I think that we need a collection of unit tests to > sufficiently test all aspects. It is too tedious to manually walk through > all possible scenarios. I will try to find some more time to work on this. Thanks Andreas!
(In reply to Kyle M Hall from comment #20) > (In reply to Andreas Jonsson from comment #19) > > We have been running this in a test system of a large coalition of regional > > Libraries, but I think that we need a collection of unit tests to > > sufficiently test all aspects. It is too tedious to manually walk through > > all possible scenarios. I will try to find some more time to work on this. Andreas, have you had any time to work on those tests?
Created attachment 163017 [details] [review] Bug 35826: Keep items on retry.
Created attachment 163018 [details] [review] Bug 35826: Add unit tests.
Created attachment 163107 [details] [review] Bug 35826: Make copy of cost matrix when substituting inf
Created attachment 163641 [details] [review] Bug 35826: optimize on transport cost when building holds queue Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com>
Created attachment 163642 [details] [review] Bug 35826: Fix errors in transport cost optimization Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com>
Created attachment 163643 [details] [review] Bug 35826: Keep items on retry. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com>
Created attachment 163644 [details] [review] Bug 35826: Add unit tests. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com>
Created attachment 163645 [details] [review] Bug 35826: Make copy of cost matrix when substituting inf Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com>
Created attachment 164501 [details] [review] Bug 35826: optimize on transport cost when building holds queue Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164502 [details] [review] Bug 35826: Fix errors in transport cost optimization Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164503 [details] [review] Bug 35826: Keep items on retry. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164504 [details] [review] Bug 35826: Add unit tests. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164505 [details] [review] Bug 35826: Make copy of cost matrix when substituting inf Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Well implemented, clear code and unit tests present. Current tests pass, new tests also passing. QA script happy, Passing QA NOTE: New dependency
Andreas, could you rebase your patch set for master? Thanks!
Created attachment 164964 [details] [review] Bug 35826: optimize on transport cost when building holds queue Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164965 [details] [review] Bug 35826: Fix errors in transport cost optimization Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164966 [details] [review] Bug 35826: Keep items on retry. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164967 [details] [review] Bug 35826: Add unit tests. Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
Created attachment 164968 [details] [review] Bug 35826: Make copy of cost matrix when substituting inf Signed-off-by: Kyle M Hall <kyle@bywatersolutions.com> Signed-off-by: Martin Renvoize <martin.renvoize@ptfs-europe.com>
You don't need to go so the way back to NSO for a rebase, thanks for the quick action. Testing to PQA so it hurts Katrins queue again. [U+1F603]
(In reply to Martin Renvoize from comment #42) > Testing to PQA so it hurts Katrins queue again. [U+1F603] Punish the RM with patches! :-D
(In reply to Nick Clemens from comment #43) > (In reply to Martin Renvoize from comment #42) > > Testing to PQA so it hurts Katrins queue again. [U+1F603] > > Punish the RM with patches! :-D I am watching you too! ;)
I also recommend bug 35899 for busy libraries with many holds.
Note: This introduces a new dependency on libalgorithm-munkres-perl.
Pushed for 24.05! Well done everyone, thank you!
(In reply to Katrin Fischer from comment #46) > Note: This introduces a new dependency on libalgorithm-munkres-perl. I have learned now that this is a bigger deal than I thought. Ideally the developer introducing a new dependency should check early on if it's OK to use it. As we support various OS versions we need to make sure it's available everywhere or if extra work would be needed. The packaging manager will need to push the dependency to the staging repo first before we push this and changes for ktd need to be made. I hope I got that all correctly. We are looking into properly updating the documentation on Monday!
hmm current master Error while loading /etc/koha/plack.psgi: Can't locate Algorithm/Munkres.pm in @INC
(In reply to Katrin Fischer from comment #48) > (In reply to Katrin Fischer from comment #46) > > Note: This introduces a new dependency on libalgorithm-munkres-perl. > > I have learned now that this is a bigger deal than I thought. Would be nice to have the module first. Now master crashes. Cant load plack.psgi
(In reply to Marcel de Rooy from comment #50) > (In reply to Katrin Fischer from comment #48) > > (In reply to Katrin Fischer from comment #46) > > > Note: This introduces a new dependency on libalgorithm-munkres-perl. > > > > I have learned now that this is a bigger deal than I thought. > > Would be nice to have the module first. Now master crashes. Cant load > plack.psgi Yes, we need to decide on how we want to handle these so we avoid breakages. Sorry for that. ktd should now work if you pull latest images, for other installations it can be installed manually. Mason was looking into it.
(In reply to Marcel de Rooy from comment #50) > (In reply to Katrin Fischer from comment #48) > > (In reply to Katrin Fischer from comment #46) > > > Note: This introduces a new dependency on libalgorithm-munkres-perl. > > > > I have learned now that this is a bigger deal than I thought. > > Would be nice to have the module first. Now master crashes. Cant load > plack.psgi Agreed. Just came to complain about the same thing heh.
(In reply to David Cook from comment #52) > (In reply to Marcel de Rooy from comment #50) > > (In reply to Katrin Fischer from comment #48) > > > (In reply to Katrin Fischer from comment #46) > > > > Note: This introduces a new dependency on libalgorithm-munkres-perl. > > > > > > I have learned now that this is a bigger deal than I thought. > > > > Would be nice to have the module first. Now master crashes. Cant load > > plack.psgi > > Agreed. Just came to complain about the same thing heh. Complaining is one way, what we need to do is build a solid workflow so we don't end up in the same situation again :) ktd should be ok again, where are you experiencing issues now?
Perhaps we should just highlight the relevant option for KTD.. or set the default differently: https://gitlab.com/koha-community/koha-testing-docker/-/blob/main/env/defaults.env?ref_type=heads#L45 By the time things get to release the packaging issues should all be resolved
Hm yes and no - instructions for developers are probably helpful, but we also need to know beforehand if a package makes sense/should be used. A check by PM could highlight issues with different Debian versions that might make us rethink implementation sometimes. I think involving them early is key.
Not backported to 23.11.x