Hi,

in the example CPLEX_Studio1263\opl\examples\opl\models\TravelingSalesmanProblem the TSP problem is solved with Integer Programming

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

I provide here a skeleton that does the same but with CPO (Constraint Programming)

Why could that be interesting ?

• This can be a starting point to add more business constraints that would be harder to add with a linear model
• This shows again the expressiveness of CPO
• Unlike the linear approach, we have a solution any time and do not have to wait for the end of the remove circuit algorithm
• This can be a starting point to a hybrid approach CP-MIP like https://www.ibm.com/developerworks/community/forums/html/topic?id=72359501-c169-4215-9dc0-1c87e653b584&ps=25

The model is

minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);    // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
}

regards

NB: Integer Programming generally gives better results than CPO but useful to have 2 tools instead of 1. (Why not adding a screwdriver to the hammer sometimes ?)

Alex Fleischer

PS:

Many how to with OPL at https://www.linkedin.com/pulse/how-opl-alex-fleischer/

Many examples from a very good book : https://www.linkedin.com/pulse/model-building-oplcplex-alex-fleischer/

Making optimization simple : https://www.linkedin.com/pulse/making-decision-optimization-simple-alex-fleischer/

Originally posted by: DavidGravot

One can see that after 2 seconds, we get the distance 7909 that will not change at time limit of 60 seconds

Do you know what's the best known distance for this instance ?

Thanks

Hi,

instead of CPO, you may use the MIP model tsp.mod

http://www.ibm.com/support/knowledgecenter/SS6MYV_3.3.0/ilog.odms.ide.odme.help/examples/html/opl/models/TravelingSalesmanProblem/tsp.mod.html

that is in CPLEX_Studio1263\opl\examples\opl\models\TravelingSalesmanProblem

and then you get 7542 after 1s

Regards

Originally posted by: AndyHam

I was looking for TSP model for drone scheduling. This sample code gives me a great starting point. Thanks!

Many how to with OPL at https://www.linkedin.com/pulse/how-opl-alex-fleischer/