[mkgmap-dev] new splitter branch solve-parallel

Thu Jul 1 09:54:02 BST 2021

Hi Gerd

Is this of any relevance -

https://en.wikipedia.org/wiki/Branch_and_bound

Ticker

On Wed, 2021-06-30 at 16:08 +0000, Gerd Petermann wrote:
> Hi all,
> 
> I've started this branch to further improve the split results. 
> Splitter has two different algorithms to find good splits. 
> 1) Algo FULL tries first to split in the middle and then continues
> with the next positions (mid+1, mid-1, mid+2, mid-2, ...) 
> The resulting parts are split again recursively. This should find the
> best possible split but can take very long when the only good split
> starts far from the middle. 
> 
> 2) Algo SOME uses some heuristics to test only some of the possible
> splits. This is typically much faster but sometimes doesn't find any
> solution and sometimes the FULL algo finds a better solution. 
> 
> The trunk version tries first the one that is more promising and - if
> that fails to find a good split - tries the other. So, sometimes the
> FULL algo works for 2 minutes and then SOME finds a good result in a
> few seconds.
> 
> This branch executes both algorithms in parallel and uses the better
> result. 
> 
> One of the open problems is to decide under what conditions the
> execution should stop.
> If the SOME algo finds a good solution within 20 secs should we still
> continue the FULL algo to find the best solution? If yes, how long?
> I'm playing with this, any input is welcome.
> 
> Gerd
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev