"DecisionBuilder" for CP-SAT solver?

[christoph...@ksb.com]

We're using Google OR-Tools for a complex product modelling problem. The solver is to provide default product configurations that satisfy all the constraints. This is equivalent to finding a single feasible solution of the problem. The problem is described by a basic product model (hundreds of constraints) plus user selections of values that are added as additional constraints.

Up until now, we've been using the older ConstraintSolver (working with c#) but we are investigating migrating to the highly touted CP-SAT Solver.

In the older ConstraintSolver, we use a custom DecisionBuilder for the following reasons:

1) We require that certain more important variables be decided first, so their domains are not restricted by unimportant variable's decisions. 

2) The prefered value to be selected for some features depends on values of other features that may have been decided or become bound before the decision is made. A simple strategy like "select minimum value" won't work here.

3) Our custom DecisionBuilder also does some internal logging to be able to answer the question "why was that value chosen for feature X?". It keeps track of what values were still available at the time of the decision, and which variables had already been decided or become bound that restrict the domain. This assists the product modelers and end users.

In the new CP-SAT I see a method CpModel.AddDecisionStrategy(System.Collections.Generic.IEnumerable<Google.OrTools.Sat.IntVar>, Google.OrTools.Sat.DecisionStrategyProto.Types.VariableSelectionStrategy, Google.OrTools.Sat.DecisionStrategyProto.Types.DomainReductionStrategy)

with which the decision strategy can apparently be controlled.

The DecisionStrategyProto class has enum's VariableSelectionStrategy (e.g. DecisionStrategyProto.Types.VariableSelectionStrategy.ChooseFirst) and DomainReductionStrategy (e.g. DecisionStrategyProto.Types.DomainReductionStrategy.SelectMinValue)  which look like they could be used to fulfill our first requirement.

I've been unable to find any examples of an extended or overloaded custom version of the decision strategy classes to be able to implement the second and third requirement.

Is there any way to make an equivalent of the custom DecisionBuilder for the CP-SAT solver?  Are there any examples?

[Frederic Didier]

Short answer: there is no support for custom decision builders. 

Now to address your points in more details:

for 1 & 2) If not all solutions are equivalent (i.e. you prefer some more than others) then you should consider adding an objective to your problem. Otherwise, you can just let the solver do its thing and see if it works better than the old CP with custom decision, if it does, then it is certainly less code for you. And as you noted, you can specify some simple strategy via the mentioned function.

3) This could be done in a post processing step, once you have a solution, you can instantiate the variables one by one in your favorite order and see what the propagation engine propagates at each step.

--
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/01966a5b-4409-4eca-a42b-4ba2d4bb09ebn%40googlegroups.com.

[christoph...@ksb.com]

Thank you Frederic Didier for your very quick response!  

It was the answer I had feared.

We are reluctant to add an objective function because we believe it would greatly increase the processing time. The solutions we get (for the current models!) are very well behaved. Solutions are usually found with no or very minimal backtracking, so if the solver had to start performing an optimizing search it would need to explore many more branches. What do you think?

Perhaps your suggestion for point 3 could be done as an alternative to custom decisions. If after constructing the model, we started adding decisions one by one in the preferred order as additional constraints  for the variables that are still unbound, it would have the same effect as custom decisions. Would the pre-solve discover failures immediately during these attempts, or would we need a real solution attempt at each step? Do you think this would work well?

 In this implementation we'd have to worry about failures and backtracking ourselves, though, instead of letting the solver do its (presumably well-optimized) thing.

[Jan Gregor]

Cp-sat solver is not direct replacement for constraint solver. It is in many areas much better and in few areas simply worse. Some months ago there was comparison of cp-sat solver with constraint solver from Ibm and results were slightly better with Ibm solver.

In your case you compare performance of incrementral sat solver + special propagators with classical constraint solver and your custom search strategy. With nearly no backtracking I think constraint solver should win. On other side with objective function you can be suprised by better results with cp-sat since it doesn't traverse classical decision tree of constraint solvers.

Jan