CODEWITHSUNDEEP
or-tools
mgencel
mgencel

Reputation: 23

Or-tools cp_sat solver is inconsistent in results

I have an optimization problem and I am using or-tools cp_sat solver. The number of variables is around 3500 (all boolean) but the number of constraints is huge (~750000). Out of 3500 variables, ~3000 are directly dependent on the other 500. There are 2 scenarios I tested:

  1. With a simple objective function depending on ~3000 constraint variables.
  2. With a complex objective function depending on ~3000*3000 new variables, where each new variable is pairwise logical_and of the variables in (1).

For each case, we seed the solver with hints for ~500 variables.

For 1, it cannot find an optimal solution in reasonable time. After around 30-45 minutes of runtime, the improvement to the objective function is negligible, but the solutions are satisfactory.

For 2, behavior is weird. Around half of the time, it claims that the problem is INFEASIBLE, half of the time, claims that it found OPTIMAL solution, but only returns back the solution implied by the hints. Only rarely (less than a couple percent of the runs), it does some optimization and returns FEASIBLE.

In addition, case 1 uses around 4-6 GB of memory but case 2 uses 100-120 GB of memory.

Is the behavior in case 2 expected? How should I approach debugging this?

Upvotes: 0

Views: 1025

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11034

For case 2, the problem become very big. You are creating 9M Boolean variables.

Are you using multithreading ?

Can you try reducing the size of the model and see if this is still flaky ?

Is the problem creation deterministic ?

Are you using large coefficient ? Is it possible you are hitting an integer overflow error ?

Thanks

Upvotes: 1

Related Questions