COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 7 years ago

#386 closed task (done)

Heuristic algorithms for symmetric TSP

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description


Attachments (4)

386-tsp-7ed08f6da055.patch (29.8 KB) - added by Peter Kovacs 9 years ago.
386-tsp-6bf84eaa22d3--de22e61d6d0c.bundle (18.0 KB) - added by Peter Kovacs 9 years ago.
A bundle file of 5 changesets
386-ae0b056593a7--dff32ce3db71.bundle (20.6 KB) - added by Peter Kovacs 9 years ago.
386-out-iterator-d3dcc49e6403.patch (9.5 KB) - added by Peter Kovacs 7 years ago.

Download all attachments as: .zip

Change History (19)

Changed 9 years ago by Peter Kovacs

Attachment: 386-tsp-7ed08f6da055.patch added

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

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

comment:2 Changed 9 years ago by Peter Kovacs

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

comment:3 in reply to:  2 Changed 9 years ago by 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

Changed 9 years ago by Peter Kovacs

A bundle file of 5 changesets

comment:4 Changed 9 years ago by 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.

comment:5 Changed 9 years ago by 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?

comment:6 in reply to:  5 ; Changed 9 years ago by 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.

comment:7 Changed 9 years ago by 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

comment:8 in reply to:  6 Changed 9 years ago by 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)?

comment:9 in reply to:  7 Changed 9 years ago by Peter Kovacs

Replying to alpar:

tsp_test fails to compile for me:

I will check this.

Changed 9 years ago by Peter Kovacs

comment:10 Changed 9 years ago by Peter Kovacs

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

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

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.

comment:11 Changed 8 years ago by Peter Kovacs

Type: enhancementtask

comment:12 Changed 7 years ago by 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.

comment:13 in reply to:  12 Changed 7 years ago by 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.

Changed 7 years ago by Peter Kovacs

comment:14 Changed 7 years ago by 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.

comment:15 Changed 7 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

All the relevant changesets are now in the main branch.

Note: See TracTickets for help on using tickets.