Tips for solving highly constrained problems

[Kyle Booth]

Hello all,

I have a problem with ~37k boolean variables that is highly constrained. So much so, that OR-Tools CPSAT with 60+ workers struggles to find a feasible solution in less than a couple hours (and sometimes takes upwards of 4 hours).

For data privacy reasons I cannot share the model here, but I wanted to hear if the community had any ideas for better approaches to these types of highly constrained problems. One idea I had is potentially taking some of these hard constraints and "softening" them via enforcement literals (and then minimizing the literals in the objective function), but I am not sure if this will help.

Appreciate any advice you can offer.

Kyle

[N L]

Hi!

I worked on a production planner application, and the model contained nearly 8-10 thousand logical variables.

I spent weeks optimizing my model and constraints. Although I did not find the correct solution, I have some hints.

First of all, the problem often is not the number of boolean variables (but obviously that's not good either), but constraints you use. 
For example: model.Add(LinearExpr.Sum(booleans) == 1) so much faster than built-in constraints for boolean variables. My model became much faster when I replaced the built-in constraints with equations. 
Second: more workers does not mean your solver will be faster. Number of workers determines which searching algorithms will be used during the solving method, so when I decreased the number of workers from 12 to 6, I got a better result faster.
Good decision strategy can also help. And lastly: you must decrease your boolean values. Refactor your model, do preprocessing or split your model into two or three subproblems. 
These are my experiences and advice without your code. I hope some of them will help you!

--
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 visit https://groups.google.com/d/msgid/or-tools-discuss/2cb62204-a5cd-4fde-9aff-868fc09e692cn%40googlegroups.com.

[N L]

Or you can try other solverss, such as Hexaly. I haven't worked with Hexaly, but its performance is impressive.

[jean-guillaume Fages]

Hi Kyle,

Yes, softening constraints is a very good approach in this situation. 

If helpful, my team and I at Cosling have experience optimizing OR-Tools models in similar workforce-planning contexts.
We can provide a short consulting engagement (a few days) to review your model and help improve performance.
And of course, we can work under an NDA if your data or constraints are sensitive.

Feel free to reach out if that could be useful!

Have a good weekend.

Best,

Jean-Guillaume
jg.f...@cosling.com

[grego...@gmail.com]

Is it possible for you to create a solution by yourself and give it to cp-sat solver as a hint? Or to fix considerable part of a model to get some valid solution?  How the solver performs after first solution? Cp-sat solver has often a problem to find first solution for too constrained problems.

You give us not enough information.

Jan