4
$\begingroup$

Question 1: Is ortool's CP-SAT sensitive to the order in which a model is constructed?

In other words, does it matter which variables and constraints come first?

I am seeing a high performance variance for some models which, unless I messed up, should be "the same" (isomorphic), and wonder if this should all be attributed to the non-determinism and heuristics in CP-SAT, or whether I could improve things by "normalizing" my model construction somehow.

Question 2: If so, are there best practices on which variables/constraints to list first?

$\endgroup$

1 Answer 1

7
$\begingroup$

This is a well know behavior of all MIP/CP solvers. Presolve and search are heavily heuristics based (to limit the complexity of the underlying algorithms), and thus are dependent on variables and constraints orders

The impact is known to be very large. And there is no way to define a canonical order.

See https://pubsonline.informs.org/doi/pdf/10.1287/educ.2013.0112

$\endgroup$
5
  • $\begingroup$ Thank you Laurent. What about rules of thumb that CP-user can apply to adjust the order in which they supply variables and constraints? I'm not looking for a hard formal rule -- otherwise I assume it would be automated and implemented -- but something informal that helps me make the right choices based on the intuition I have for the problem at hand. E.g. "Identify what is [or what you believe to be] the hardest part of the model, and name that first ..." or similar. $\endgroup$
    – Hanno
    Mar 6, 2023 at 13:27
  • $\begingroup$ Not clear. Try to have variable that are close semantically be created around the same time. For constraints, the impact is less clear. $\endgroup$ Mar 6, 2023 at 14:07
  • $\begingroup$ is it possible to provide an example showing how different orders change the performance ? $\endgroup$ Mar 6, 2023 at 21:01
  • $\begingroup$ I have added a link to the original work. $\endgroup$ Mar 6, 2023 at 21:31
  • $\begingroup$ Thanks @LaurentPerron! $\endgroup$
    – Hanno
    Mar 12, 2023 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.