new splitter branch solve-parallel
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
I feel of all tiles are 85 percent of max then stop. If 5percent of tiles are less the 75 percent max then maybe stop after 30 seconds. If more then 10 percent AND more then 10 tiles are less then 75 percent continue. On Wed, 30 Jun 2021, 19:09 Gerd Petermann <GPetermann_muenchen@hotmail.com> 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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Felix, yes, sounds reasonable to wait a while if result is not very good. In some cases both algos don't find a good solution, e.g. norway with polygon-file, search-limit=1000000 and --max-nodes=1200000 seems to be stressing, it results in 210 tiles. With search-limit 10 mio it finds a good split with 135 tiles. Maybe I should simply use a much higher initial search-limit and implement an option to set the maximum time for the search. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Felix Hartmann <extremecarver@gmail.com> Gesendet: Mittwoch, 30. Juni 2021 21:21 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] new splitter branch solve-parallel I feel of all tiles are 85 percent of max then stop. If 5percent of tiles are less the 75 percent max then maybe stop after 30 seconds. If more then 10 percent AND more then 10 tiles are less then 75 percent continue. On Wed, 30 Jun 2021, 19:09 Gerd Petermann <GPetermann_muenchen@hotmail.com<mailto:GPetermann_muenchen@hotmail.com>> 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@lists.mkgmap.org.uk<mailto:mkgmap-dev@lists.mkgmap.org.uk> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd, well setting initial search limit to 1000000 solves already loads of bad solutions and is still quite fast. Albeit using v 408 it was the best universal value I felt. Not much slower but in many cases getting better results. Going for much bigger initial value actually then caused also worse splits. I do not know how right now it determines the max value. but maybe increasing it would be good. And I feel it should increase/wait if the split obviously is not good. If it is good (all tiles except one within 80% of maxnodes) or very good (all except one 85%) it could stop earlier in order not to waste resources. I do not know how easy such a solution is to be implemented however. So far most bad splits are really realy bad (e.g. Norway 210 vs 135 tiles - in such cases a much longer time taken to find a good split is reasonable. Also as mkgmap will run faster if the split is better, compressing the maps will produce a smaller overall size if the split is better. On Thu, 1 Jul 2021 at 11:54, Ticker Berkin <rwb-mkgmap@jagit.co.uk> wrote:
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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- Felix Hartman - Openmtbmap.org & VeloMap.org
Hi Ticker, yes, I think splitter implements something like that. A a start we have a grid with a given resolution and a single rectangle that covers (part of) this grid. Several criteria tell us if this "tile" has to be split or not. A split can be horizontal or vertical, but only where the grid is. A simple straightforward approach is to always split in the middle, but that will produce (almost) empty areas in the sea or in deserts. Therefore other splits have to be tested. Goal is to find a good split in a reasonable time. One problem: It is not clear if a valid solution exists unless one is found. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 1. Juli 2021 10:54 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] new splitter branch solve-parallel 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@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (4)
-
Felix Hartmann -
Gerd Petermann -
Gerd Petermann
-
Ticker Berkin