What do limit and symmetry mean in ortools?

user_18726774 0
Viewed 149

I have a problem I am trying to optimize with about 1 million variables and 10 million constraints. CP-SAT takes a long time to find a feasible solution. I was reading the output and I see a few things I don't understand.

  • It tells me that I need to increase symmetry to at least 3. Looking at this link (and assuming it is relevant to the latest version of CP-SAT and using Python) it says

// Whether we try to automatically detect the symmetries in a model and // exploit them. Currently, at level 1 we detect them in presolve and try // to fix Booleans. At level 2, we also do some form of dynamic symmetry // breaking during search.

But it doesn't say anything about symmetry at 3 or above. What does it do if you set it to 3?

  • I tried setting symmetry to 3 and now that message has gone but I am left with

[Symmetry] GraphSymmetryFinder error: During the initial refinement.

Is this something I should try to resolve, and if so how?

  • There is also a line like:

[Probing] deterministic_time: 1.00001 (limit: 1) wall_time: 1.21766 (Aborted 10197/201810)

Is that something to worry about and can I increase limit to make the probing complete rather than abort? limit isn't one of the parameters in solver.parameters it seems. Is limit setting a cap on the number of seconds Probing can run for? What is happening in this probing step?

or-tools constraint-programming python
1 Answers

Symmetry detection and probing are optional, potentially costly, phases during presolve.

Symmetry detection is nice, but does not yet support all constraints. So it can fails. The solver will silently ignore this failure.

For probing, the best way to improve perf is to use multiple workers (8 or more). Continuous probing is enabled if you have more that 12 workers. Of course, it is best if your computer has that many cores.

user_99717590
Related