CP SAT solver for vrp

[youssef kaichouh]

Hello everyone ,

since OR-tools vrp solver is single. threaded and doesn't benefit from any Xcpu vm, and the only multithreaded solver in OR-tools is CP-sat, could it be interesting to model the vrp with CP (if not what limitations plz and why). or is their any vrp solving strategies that can be parralized ?

Thank you in advance

[Vincent Furnon]

The routing solver actually supports CP-SAT as a backend, which indeed allows you to use multiple threads. However, although I am sure this will use more resources if you activate multithreading, I can't guarantee this will actually give you better solutions (it might, it might not). In general if you want to make good use of your CPUs I'd try running multiple routing solver instances in parallel on the same problem with various first solution or search strategies (why not use CP-SAT in one of them for instance). More advanced, you can try splitting your problem into smaller independent problems and solve each sub-problem in parallel (and iterate); similar to a parallelized large neighborhood search.  

Are you aiming at speeding up the solver or getting better solutions (or both) ?

Vincent

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAOtwtKUD6LSZxhMSLzknnW9sCWRU5Nv0ugXeijpbNnenKfCvcw%40mail.gmail.com.

[youssef kaichouh]

Indeed we try to run the solver in parallel with multiple strategies and also shuffles (since sometimes order of visits impact result signifactively) :

In my think the most interesting strategies are : 'PATH_CHEAPEST_ARC'  very fast but not consistant,  'GUIDED_LOCAL_SEARCH' more performance and stability, but you need to precise a time_limit which is hard to do, how could you estimate it  on what it depends beside number of visits?

We also split the probleme up stream into "independant problems" (connex components of a billateral graph with vertices {stops}U{vehicles} and edge between a vehicle that can visit some stop) i don't know if we can do better ?

How you cav activate multithreading in vrp ?  we are  aiming at both speeding up the solver and getting better result

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPz%2Bj2VFPxDVirTa6pEv0kSv%2BgCLjiktLKDa0o-Sbbm4dCyo%3DQ%40mail.gmail.com.

[blind.line]

I have a follow up question to this thread, although perhaps the answer is to look at the code and find out. When the CPSAT solver is “turned on” for the routing engine, does this mean that calls that grab the solver (model.solver(), for example) return an instance of the CPSAT solver?  

I really prefer the syntax and usage of the CPSAT solver over the old CP solver, but as was pointed out in another thread, the routing solver is better at complicated routing problems. 

James

On Sep 15, 2021, at 09:16, youssef kaichouh <youssef.k...@gmail.com> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAOtwtKXt5_fQ%3DAv3M_AfKe_Cv8-hGKkdu6UuBMw16wvbNsJ6%2Bg%40mail.gmail.com.

[Laurent Perron]

The CP-SAT solver does not grab additional constraints.

It does not yet understand all that can be expressed with just the RoutingModel.

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/652D18E9-CF09-41B6-84F1-887D2A043463%40gmail.com.