CP Metaheuristics

[Thomas 1234]

1. How can I call a metaheuristic to be used in the model?

There is an example for C++ but I can't transfer it to Python as the noob I am.

https://acrogenesis.com/or-tools/documentation/user_manual/manual/metaheuristics/SA.html#sa-first-results

Does anybody have an example where it is used?

2. Where can I find a list with the possibilities for First solution strategies?

Thank you.

[Laurent Perron]

https://developers.google.com/optimization/routing/routing_options

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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1049df12-7765-4ed5-af63-5807bfb4edb7n%40googlegroups.com.

[Mizux Seiha]

1) to set it take a look at any sample .py here: https://github.com/google/or-tools/tree/stable/ortools/constraint_solver/samples

e.G. 

    # Setting first solution heuristic (cheapest addition).

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) 

    search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.time_limit.FromSeconds(3)

    # Solve the problem.

    solution = routing.SolveWithParameters(search_parameters)

[Thomas 1234]

Thanks for the replies.

Aren't those implementations for Routing problems only?

Maybe I didn't make clear that I want to do constraint programming.

I am looking for an example like this one 

Found it here.

[Laurent Perron]

For pure cp, us CP-SAT.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ec36ef51-f353-4377-9eaa-f28fc03bc3ffn%40googlegroups.com.

[Thomas 1234]

Okay thanks,

 but I can't find an example with CP-SAT and parameters for a first solution strategy. For the old CP-Solver I found an example, and I found out that you can call metaheuristics with solver.SimulatedAnnealing() for example, but I can't figure out how to use it.

[Laurent Perron]

There are no meta heuristics for CP-SAT. Just LNS if you use more than 6 workers.

Still, on CP problems, it outperforms the original CP dramatically.

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/dfee91eb-a020-4e15-9888-4516b820ab9an%40googlegroups.com.

[Thomas 1234]

Isn't the routing library uses the CP solver too? Why does it use the old Solver?

What if I implement a VRP without the routing library? Could I just use the old CP Solver?

[Laurent Perron]

The routing library uses a lot of techniques (simplex, CP-SAT, flow, LS, constraint programming)

The bulk of it is local search, which does not use anything. 

The goal of the routing team when working on the local search is to avoid calling the CP layer.

It uses the CP layer as a checker, and sometimes to solve a scheduling problem. But this part is being converted to CP-SAT.

To answer your question, it uses the original CP solver because it was implemented that way, and it is a substantial piece of code.

Now you are free to use it as you wish. I do not think it is a good idea :-)

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/a22729a4-0776-4ab5-9d30-691ae1d7184dn%40googlegroups.com.