Heuristic algorithms for symmetric TSP

[Peter Kovacs]

[7ed08f6da055] contains the implementation of five TSP heuristics (by Gabor Varga).

[Peter Kovacs]

I'm currently working on the revision and improvement of these tools.

[Alpar Juttner]

Replying to kpeter:

I'm currently working on the revision and improvement of these tools.

Just for the record, please summarize what kind of modifications do you plan to make

[Peter Kovacs]

A bundle file of 5 changesets

[Peter Kovacs]

Please skip the previous attachment [7ed08f6da055] (it is not consistent) and consider the new attachment of 5 changesets:

• [6bf84eaa22d3] Heuristic algorithms for symmetric TSP (#386)
• [8e8e162dc361] Add a function for checking metric costs (#386)
• [08d95209631b] Doc group for TSP algorithms (#386)
• [e99bbeec2d02] Document and greatly improve TSP algorithms (#386)
  • Add LEMON headers.
  • Add Doxygen doc for all classes and their members.
  • Clarify and unify the public API of the algorithms.
  • Various small improvements in the implementations to make them clearer and faster.
  • Avoid using adaptors in ChristofidesTsp.
• [de22e61d6d0c] A detailed test file for TSP algorithms (#386)

I think, after applying these patches, the TSP tools could be merged into the main branch. However, the implementation of InsertionTsp still could be made faster by a factor of n (and the doc should be adjusted accordingly). Gabor or I will implement this enhancement soon.

[Peter Kovacs]

The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced checkMetricCost() for this (see [8e8e162dc361]). I had no better idea than adding a separate header file tsp_utils.h for this function. (I the future, other tools could be put here.) Do you like this solution?

[Alpar Juttner]

Replying to kpeter:

The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced checkMetricCost() for this (see [8e8e162dc361]). I had no better idea than adding a separate header file tsp_utils.h for this function. (I the future, other tools could be put here.) Do you like this solution?

My major complain is why do you use Dijkstra for checking the triangular inequality? It should simply be checked directly for each triangle.

The tsp_utils.h header file is alright for me, assuming that the tools here are really only useful for TSP related problems.

[Alpar Juttner]

tsp_test fails to compile for me:

[ 90%] Building CXX object test/CMakeFiles/tsp_test.dir/tsp_test.cc.o
In file included from /home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:32:0:
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In member function ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::deque<lemon::FullGraphBase::Node>, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’:
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7:   instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49:   instantiated from here
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7:   instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49:   instantiated from here
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::deque<lemon::FullGraphBase::Node>’
cc1plus: warnings being treated as errors
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: At global scope:
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In instantiation of ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::deque<lemon::FullGraphBase::Node>, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’:
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7:   instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::NearestNeighborTsp, std::string = std::basic_string<char>]’
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:257:49:   instantiated from here
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:126:12: error: unused parameter ‘tour’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: In member function ‘lemon::Opt2Tsp<CM>::Cost lemon::Opt2Tsp<CM>::run(const Path&) [with Path = std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >, CM = lemon::GraphExtender<lemon::FullGraphBase>::EdgeMap<double>, lemon::Opt2Tsp<CM>::Cost = double]’:
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:193:7:   instantiated from ‘void tspTest(const std::string&) [with TSP = lemon::GreedyTsp, std::string = std::basic_string<char>]’
/home/alpar/projects/LEMON/hg/386/test/tsp_test.cc:258:30:   instantiated from here
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:141:33: error: no type named ‘ArcIt’ in ‘class std::vector<lemon::FullGraphBase::Node, std::allocator<lemon::FullGraphBase::Node> >’
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h: At global scope:
/home/alpar/projects/LEMON/hg/386/lemon/opt2_tsp.h:126:12: error: unused parameter ‘tour’
Linking CXX executable suurballe_test

[Peter Kovacs]

Replying to alpar:

Replying to kpeter:

The doc of TSP algorithms refer to the notion of "metric cost function". Therefore, we introduced checkMetricCost() for this (see [8e8e162dc361]). I had no better idea than adding a separate header file tsp_utils.h for this function. (I the future, other tools could be put here.) Do you like this solution?

My major complain is why do you use Dijkstra for checking the triangular inequality? It should simply be checked directly for each triangle.

You're right, it should be improved.

The tsp_utils.h header file is alright for me, assuming that the tools here are really only useful for TSP related problems.

I'm not sure about it. Checking whether a cost function is metric or not could be useful in other use cases, too. What do you think?

Should we call this header as metric_cost.h? Or should we think of a header file, in which this function could be placed along with other similar tools, e.g. checkConervativeCost() (in the future)?

[Peter Kovacs]

Replying to alpar:

tsp_test fails to compile for me:

I will check this.

[Peter Kovacs]

I attached a new bundle file that replaces the previous attachments. It contains the follwing 6 changesets:

• [ae0b056593a7] Heuristic algorithms for symmetric TSP (#386)
• [62ba43576f85] Doc group for TSP algorithms (#386)
• [9a51db038228] Document and greatly improve TSP algorithms (#386)
• [ef200e268af2] Unifications and improvements in TSP algorithms (#386)
• [07682e24c4e8] A detailed test file for TSP algorithms (#386)
• [dff32ce3db71] Make InsertionTsp much faster and improve docs (#386)

Four of these changesets are the rebased versions of previously attached ones. The other two make significant improvements:

• [ef200e268af2] fixes the compilation issue.
• [dff32ce3db71] makes the InsertionTsp algorithm faster by a factor of n.

In this new bundle file, the checkMetricCost() utility function is omitted. Currently, I don't find it so important and I don't have a good idea for the name of the corresponding header file.

[Alpar Juttner]

I went through the changesets, it looks good. But, I started thinking of an alternative interface - instead of a FullGraph, the input would be just a set of nodes of a (probably empty) graph plus the cost function (this is something like FullGraph::EdgeMap<>, I know) and the would be the the graph containing the arcs of the tour. This is a very rough idea, not sure if it make any sense. What do you think?

If you say it's a nonsense, I will just merge the current version as is.

[Peter Kovacs]

Replying to alpar:

I went through the changesets, it looks good. But, I started thinking of an alternative interface - instead of a FullGraph, the input would be just a set of nodes of a (probably empty) graph plus the cost function (this is something like FullGraph::EdgeMap<>, I know) and the would be the the graph containing the arcs of the tour. This is a very rough idea, not sure if it make any sense. What do you think?

If you say it's a nonsense, I will just merge the current version as is.

What advantages would this solution have? Could we describe use cases in which it would be much easier or clearer to use? E.g. if you have a connected graph with non-negative edge costs and define the nodes as shortest path distances, then this design could be used in combination with an all-pair shortest path algorithm (see #346). Would it be much easier than mapping the nodes of the original graph to the nodes of a full graph of the same number of nodes? (Anyway, all pair shortest path algorithms could generate a transitive closure graph as a full graph with an edge map plus node reference map(s) similarly to graph copy tools.)

In fact, I don't think that this proposal is nonsense, but I also don't see major advantages.

[Peter Kovacs]

The attached patch [d3dcc49e6403] improves the API of the TSP algorithms: an output iterator is required instead of a container in the tourNodes() functions.

[Alpar Juttner]

All the relevant changesets are now in the main branch.