Custom decision builders for CP-SAT solver?

[christoph...@ksb.com]

On Stack Overflow, a user posted a question on how to generate "math puzzles" using OR-Tools. See https://stackoverflow.com/questions/69225141/make-or-tools-find-values-and-operators-for-math-puzzles

I posted an answer which required using a custom decision builder, so I had to use the old ConstraintSolver, since the CP-SAT solver doesn't support them. (If anyone has an alternative solution to that puzzle builder that works without a custom decision builder, I'd be happy to hear about it.)

Now, that question on SO might not be the "killer app" that alone justifies introducing custom decision builders, but their lack is the reason that we cannot migrate to the new solver with our real-world product modelling application in a product configuration software used by hundreds of concurrent users preparing customer quotations.

We need custom decision builders for two main reasons:

• There is a hierarchy of more important to less important features of the product and decisions need to be taken to assign preferred values to the features in order of their priority. 
• When user decisions result in a conflict, we need to use custom decision builders to activate / deactivate constraints during minimal conflict search.

It would be great if support for custom decision builders would be added to the new CP-SAT solver. Are there any plans or deliberations about doing this?

[Laurent Perron]

Why do you need custom builders ? 

Can you send us a problem that does not solve well enough?

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/d8a47939-99c3-4c37-8281-a0e4b8e53753n%40googlegroups.com.

[christoph...@ksb.com]

It's not a problem of not finding solutions well enough, but of finding the right solutions.

Our application is for product configuration to prepare customer quotations. A typical product model has around 500 features with 4 values on average but up to several hundred for a few features, 150 conditional assignments and about 600 restriction tables ("AllowedAssignments") with 1 to 10 columns (features)  each and containing 140,000 lines in total for all tables. Of the restriction tables about half are to be only conditionally enforced based on a comparison expression involving the product features.

The model is too complex for users to find valid solutions manually, so we use Google OR-Tools to look for solutions. The tool is being used to find solutions only, not to optimize.

The product model represents the background, and additional constraints result from user decisions on certain features. The user proceeds by selecting values feature by feature. After each user decision, a request for a solution is generated to assign the rest of the features their preferred default values that are compatible with the decisions made so far. Since the solution request is done after each "user click" and has to finish before the user can proceed, it needs to return quickly.

Since the propagation is quite strong, the solutions are usually found with no or minimal backtracking (60% with no backtracking, only 10% having more than 8 failures during search).

One of the main requirements for the solutions is that they set the preferred default values. There is a ranking of features from most important to least important, and a ranking of the values from most preferred to least preferred. The ranking is not always such that the most preferred values of each feature lead to a consistent solution. For example, although the values for motor power are ranked from smallest to largest, smaller motor power being preferred, there may be another more important feature "motor type" which prevents the absolute smallest motor from being selected. If the motor power is decided first, selecting the absolute smallest motor, then the more important feature "motor type" can't get its preferred value since it has been propagated out of its domain.

I had addressed this problem in the past in the forum (e.g. https://groups.google.com/g/or-tools-discuss/c/AealBKhjxUU/m/3N1cujnkBgAJ) and had received suggestions to either define an objective function or to instantiate the variables one by one in the preferred order.

Although it would be mathematically possible to define an objective function-- e.g. make an 800-bit number whose highest order bits represent the values for the most important feature, the next most significant the second most important, etc. and try to maximize the number during the solution-- such an objective will not fit in a long variable and probably more importantly, will turn the problem from a simple constraint propagation with little backtracking into an optimization problem. Our suspicion is that this would drive up the solution time, which directly affects the reaction time per click for the user.

The other suggestion, to instantiate the variables one by one in the preferred order, would entail that we worry about the backtracking in case of conflict on our side,  where it certainly won't profit from the optimization of exactly this function in the solver.

We also use the custom decision builders to generate conflict resolution suggestions when the user decisions are not compatible with the model. The algorithm is described in the attachment, which we presented at the OR2021 International Conference on Operations Research hosted by the University of Bern. We use a technique similar to the one I described in the SO answer to turn constraints on and off. During the minimal conflict search, sets of constraints are tried using Assignments to their enforcement variables. We need to control exactly which constraints are active or not, turning them off and on, at each step of the algorithm.

- 

[Laurent Perron]

Have you tried with solution hinting ?

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/8718fc77-7e7f-4cbf-9ea6-2cef53c454d7n%40googlegroups.com.

[christoph...@ksb.com]

How exactly would we do that?

We could provide a hint in which each (or an important subset) of the features is given its preferred value.  In most cases, taken together with the user decisions, the hint will be infeasible. How can we guide the solver on which features to change to achieve feasibility?  In my example above, how would the solver be instructed to change motor power to achieve feasibility instead of removing the preferred value from the more important "motor type"?

[Laurent Perron]

Hints are processed in order.

In general, I like the model to be self contained. 

so if x == 2 is preferred over y == 3, then I suggest adding the two encoding literals to the objective with different weights.

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/e34c3f62-e951-4190-b758-2271f9089136n%40googlegroups.com.

[christoph...@ksb.com]

Up until now we haven't had an objective to optimize but simply looked for one solution. With an objective, won't the solution times be higher?

Or will a lexicographically designed objective (i.e. feature weighting for decisions for x always overweigh those for y) be able to be quickly optimized?