SAT solver vs. CP solver

[Lars Lütjens]

Hi all,

what is the difference between the SAT solver interface and the CP solver?

I read in one of the last posts (source) that the CP (constraint programming / from ortools.constraint_solver import pywrapcp) solver is deprecated and should not be used anymore. Can this be confirmed or are there release notes about this move?

Because all examples on the website are still described with the CP solver. But by looking at the examples, it seems that both solvers have interchangeable features sets.

Can somebody please shed some light on this matter.

Best regards,

Lars

[Laurent Perron]

The CP solver was developed 10 years ago.

3-4 years ago, we started the SAT/CP solver.  Its performances are way better than the CP one.

We are in the process of migrating the examples from the website to the new solver. The code is already in examples/python/*sat.py, we just need to rewrite the doc around.

In term of features, the biggest difference is that the SAT/CP solver has a closed model. Writing extension (new constraints) is extremely difficult, and not exposed or documented.

Apart from that, the both propose integer constraints, interval variables, scheduling, some TSP/VRP support.

I hope this clarifies it.

Thanks

--
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.

[Lars Lütjens]

Thanks for your prompt reply. It clarifies the relation of CP and SAT solvers.

I saw that most scheduling and pure CP examples have been ported to SAT and SAT is now the recommended solver for scheduling and assignment problems. Which solver would you recommend for TSPs and VRPs, especially for VRP variants (with time windows, with pickup and delivery, multiple depot, ...)?

Regards,

Lars

[Laurent Perron]

Definitely the routing library. 

[Shaun Rowan]

Hi Laurent,

Are there any techniques available in the SAT solver to replace these behaviors which are available in the CP Solver?

1)  DisjunctiveContraint.SetTransitionTime

2)  MakeIntervalVarRelationWithDelay  

I'd love to make the switch, but I'm not sure if these can be done...

Thanks,

Shaun

[Laurent Perron]

So, 

for the second part, you directly have access to the start and end variables of the intervals.

It is then easy to add a linear constraint between start, end...

For the first, first create a circuit constraint with a depot node, and a dense graph with 1 node per interval + the depot.

You create one literal per arc.

And then you add a bunch of semi-reified constraint:

literal_i_j => start(j) >= end(i) + transit_time(i -> j).

I hope this helps.

--Laurent

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

[Jonas Frank]

Hi Laurent,

does this mean that if I implement Routing-Problems like in the Routing-Examples shown, there will be no problem with the deprecated constraint solver?

In my special case, I'm using a RoutingModel as shown in the example. Due to the fact that I need a rank-constraint (some stations have to be visited before other stations but it doesn't matter what is visited between those two stations) I had to implement a custom dimension with a constraint like this:

Solver solver = routingModel.solver();

            //Creates a dimension where the transit variable is constrained to be equal to evaluator(i, next(i)); 'slack_max' is the upper bound of the slack variable (movement) and 'capacity' is the upper bound of the cumul variables. 'name' is the name used to reference the dimension; this name is used to get cumul and transit variables from the routing model.Returns false if a dimension with the same name has already been created(and doesn't create the new dimension). Takes ownership of the callback 'evaluator'.

            const string rank_name = "rank";

            routingModel.AddConstantDimension(1, stationNumber + 1, false, rank_name);

            //Precedence Constraints hinzufügen

            //mat(i,j)=1 if i is ranked before j

            for (int rows = 0; rows < stationNumber; rows++)

            {

                for (int columns = 0; columns < stationNumber; columns++)

                {

                    if (precedenceMatrix[rows, columns] == true)

                    {

                        solver.Add(solver.MakeLess(routingModel.CumulVar(rows + 1, rank_name), routingModel.CumulVar(columns + 1, rank_name)));//+1 in cumulVar because depot is included

                    }

                }

            }

            RoutingDimension rank_dimension = routingModel.GetDimensionOrDie(rank_name);

Due to this, the constraint solver is used directly, will I have to update this code (what do I have to do?) or will this be updated on the library side?

[Laurent Perron]

Hi, 

The routing solver including the CP subset is maintained. You can use it safely.

Apart from the routing code, I have not touched the CP solver for nearly 3 years. I will still fix bugs, but I will not improve performance, nor add new constraints.

All CP effort is directed towards the SAT/CP solver, which IMO is much better, although a bit restricted.

--Laurent

[Jonas Frank]

OK, so this means we can solve routing problems like it's shown in the examples with cp-solver.?

Is it planned to change the routing library in the long term to use the sat-solver as underlaying solver, so it can benefit from the performance-improvements?

[Laurent Perron]

Yes for the first.

For the second, this is the long term plan.

We have no plan/resource to do it short term.

This being said, performance improvement will be minimal. The design of the local search part of the routing library is geared towards not calling the CP solver.

Thus even if we speed up the CP part by 2, we will not speed up the routing library by 2, for from it :-)

Thanks

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

Le mer. 16 mai 2018 à 12:48, Jonas Frank <jonasf...@gmail.com> a écrit :

OK, so this means we can solve routing problems like it's shown in the examples with cp-solver.?

Is it planned to change the routing library in the long term to use the sat-solver as underlaying solver, so it can benefit from the performance-improvements?

--

[Laurent Perron]

I meant far from it.

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

[Jonas Frank]

Hi Laurent,

are ther news on this topic. 

Especially with the new SAT-CP-Solver?

[Laurent Perron]

Nothing to report, we are working hard on the CP-SAT solver, but not on the routing part, mostly the MIP part.

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