Issue578

Title Limit time spent in iPDB dominance pruning
Priority feature Status chatting
Superseder Nosy List florian, jendrik, malte, silvan
Assigned To Keywords
Optional summary

Created on 2015-10-08.21:56:13 by florian, last changed by malte.

Messages
msg6725 (view) Author: malte Date: 2017-12-05.13:51:21
Based on issue735, we know that there are still some cases where dominance
pruning is time-critical, and this issue would be quite easy to implement.
msg4650 (view) Author: florian Date: 2015-10-08.21:56:13
On 08.10.2015 17:35, Santiago Franco wrote:
> I noticed that in problem Woodworking-17, sequential optimal, ipc 2011, 
>   iPDB is finishing after around 760 secs even though I set the max_time 
> to 200.  When I looked at the code, I noticed that it did exit the hill 
> climbing phase at around 200 seconds, but then it goes ,without checking 
> the global timer, into dominance prunning.  Dominance prunning did not 
> prune anything but it took around 500 secs.
> [...]
> In my code, I am now checking the global timer before iPDB does 
> dominance pruning.  Just wanted to know what you think about that, and 
> whether dominance pruning should be done even after iPDB has reached the 
> specified max_time.

Dominance pruning is currently called after catching the timeout exception, so
it is not affected by the time limit for hill-climbing. I think it would make
sense to give it its own time limit: its not really part of hill-climbing and
could still be time-effective to run, even if hill-climbing took to long, but we
don't want to run it for too long. Instead of not running it at all, I would
suggest to add a separate time limit just for dominance pruning and change the
pruning code so it still does something useful based on the information it has
at the time it reaches the time limit (half the pruning might still have a
significant impact).
History
Date User Action Args
2017-12-05 13:51:21maltesetstatus: unread -> chatting
messages: + msg6725
2015-10-09 10:02:39silvansetnosy: + silvan
2015-10-08 22:00:06jendriksetnosy: + jendrik
2015-10-08 21:56:13floriancreate