Title Do not ignore bounds of iterated search components.
Priority bug Status chatting
Superseder Nosy List clemens, florian, jendrik, malte, silvan
Assigned To Keywords
Optional summary

Created on 2024-01-08.09:38:26 by clemens, last changed by clemens.

msg11533 (view) Author: clemens Date: 2024-01-22.11:42:36
I have talked about the issue with Malte offline. He agreed that this change seems reasonable. I've added a document note about the semantics of using bounds in an iterated search. Could somebody please read it in the pull request and if they are happy confirm that this is ready to merge?

By the way I did not write on Discord to give people time to react because I don't like the trend that progress is reported both on Discord and the issue tracker. I also don't think this change is too big of a deal, so it shouldn't be necessary for everybody to be aware of it in my opinion.
msg11509 (view) Author: clemens Date: 2024-01-08.15:21:09
I have done some checks locally and everything seems to work as expected, i.e., the current search uses the minimum of its bound specified in the command line options and *best_bound*.
msg11508 (view) Author: florian Date: 2024-01-08.13:19:20
I don't think we need experiments but try running it locally with different combinations of bounds set (or not set) on the overall and component searches to see if the behavior is as expected.

I would wait with merging a bit to give people a chance to object to the new semantics. Maybe announce it on Discord with a deadline. Something like "we plan to merge something that changes the semantics like this. If anyone has any objections, speak up until X."
msg11507 (view) Author: clemens Date: 2024-01-08.12:31:00
Thanks Florian. I've created a pull request: Do you think we need to run experiments for this? Since none of our aliases or other recommended configurations use bounds in an iterated search, nothing should change in terms of search behavior. I expect the additional check in the if-clause to have no visible effect in terms of runtime.

If no experiment is needed, is this already fine to be merged or should we wait for somebody else's approval?
msg11504 (view) Author: florian Date: 2024-01-08.11:18:26
Makes sense to me. The current behavior indeed seems like a bug.
msg11503 (view) Author: clemens Date: 2024-01-08.09:38:26
In the Discord server there was a question about bounds in connection with iterated search. When I looked into it, I had the feeling the current behavior looks like a bug, but I'm not sure. I'm opening this issue to discuss whether there's need to change something.

So when using iterated search with the *pass_bound=true* option, it will always set the bound of its component search algorithms to *best_bound* which represents the cost of the best solution found in previous iterations. *best_bound* is initialized to the bound set for the iterated_search (infinity by default). Now if iterated search has no bound specified, but the first component search algorithm does, then the bound of the component is overwrtitten with infinity before the search starts. This seems confusing to me (and to the person asking on Discord, apparently). I argue we'd rather want to use the minimum of *best_bound* and the bound of the component in such a case. My suggested change is to change the condition under which the component bound is overwritten from

    if (pass_bound) {


    if (pass_bound && best_bound < current_search->get_bound()) {

(lines 66-68 of src/search/search_algorithms/ in today's main branch).

Does this make sense? Or is there a good reason for the way it is implemented now?
Date User Action Args
2024-01-22 11:42:36clemenssetmessages: + msg11533
2024-01-08 15:21:09clemenssetmessages: + msg11509
2024-01-08 13:19:20floriansetmessages: + msg11508
2024-01-08 12:31:00clemenssetmessages: + msg11507
2024-01-08 11:18:26floriansetnosy: + florian
messages: + msg11504
2024-01-08 09:38:26clemenscreate