Notes on performance

[OndrejNepozitek]

Too much backtracking when there is a problem with the earlier chains

It sometimes happens that the way the earlier chains are laid out causes problems in the later stages of the algorithm.

Solution 1: Improve chain decomposition

It should not happen that later chains are connected e.g. to the first chain. But it sometimes happens.

Solution 2: Limit the branching factor of simulated annealing

Currently, the branching factor is set to 5. This may be too much if we have to backtrack really far. From some initial results, it seems like some inputs do not benefit from decreasing the branching factor at all. But if the result is improved decreasing the branching factor, it seems like it benefits the most from branching factor of 2.

branching_results.txt

Chain decomposition improvements

DFS probably better than path components

Start DFS with all neighbors instead of multiple dfs from individual neighbors