Any TSP, VRP or routing problems samples using the CP-SAT solver?

[Kevin Monk]

Hi,

Loving the OR-Tools.

C'est très bon!

One of my favourite CP problems is the TSP problem of 40 European cities that are used by the - also excellent - Optaplanner in their suite of examples. The distances are in degrees of latitude and longitude and the optimal solution seems to be a distance of ~216,449. This is the optimal solution that Optaplanner gets to using First Fit Decreasing construction heuristic and Late Acceptance Hill Climbing local search. I think Optaplanner is slightly slower.

I've put the data into the tsp example from the guide and it's blisteringly fast! Good job! However, I have a couple of questions:

1. Is there a way to see intermedia solutions when using pywrapcp ? I found SolveWithParametersAndSolutionCallback but it doesn't appear to be implemented in the python wrapper? A 40 city TSP is a great demonstration tool for the power of CP techniques and so I'd like to pipe the intermediate solutions back to a websocket based web application so the end user can see the solutions updating in realtime. 
2. All the routing examples, guides and samples appear to use the routing extension that's built on the Old CP solver (pywrapcp). Is there a plan to move TSP examples to CP-SAT? Is this even possible? Will the routing extension be moved to CP-SAT?

I've attached the 40 European city TSP code.

Thanks,

Kevin.

[Laurent Perron]

I have added the cp_model example for the pure tsp problem.

Please note that this model works because we do not need to compute cumulated distances at each node. Otherwise, it would be much slower.

this model scales to ~150 cities.

https://github.com/google/or-tools/blob/master/examples/python/tsp_sat.py

Num nodes = 40

*** starting model expansion at 0.00s

*** starting model presolve at 0.00s

- 0 affine relations were detected.

- 0 variable equivalence relations were detected.

Optimization model '':

#Variables: 1560 (1560 in objective)

 - 1560 in [0,1]

#kCircuit: 1

*** starting to load the model at 0.03s

*** starting sequential search at 0.06s

#1       0.07s  obj:[0,225342]  num_bool:1561 

#ObjLb   0.08s  obj:[216259,225342]  

#ObjLb   0.08s  obj:[216449,225342]  

#2       0.08s  obj:[216449,216449]  num_bool:1561 

CpSolverResponse:

status: OPTIMAL

objective: 216449

best_bound: 216449

booleans: 1561

conflicts: 0

branches: 3477

propagations: 122884

integer_propagations: 128776

walltime: 0.087024

usertime: 0.087024

deterministic_time: 0.0159506

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kevin Monk]

Oh no! You've ruined my demo by making it solve too quickly! :D

Just kiddin' - thanks for this. That's an amazing speed increase over local search techniques. I can see how it would quickly fall over though with more cities. It really highlights how important it is to understand the model you're trying to solve. Very appreciative of you taking the time to construct an example.

Kind regards,

Kevin.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Mohamed Salem Baira]

Hello,

Awesome CP-SAT solution for TSP. I'm now looking for a CP-SAT solution to a VRP with single depot and no particular maximum distance per vehicle.

Could anyone help me out ?