0
$\begingroup$

I am trying to solve a flexible job shop problem variant using or-tools. And in some input configuration, in general after one month of scheduling time, I am facing a weird behavior.

I am aware that the problem is NP-Hard, so I am expecting a sort of exponential growth of the time gap between the last feasible and the new one. I am enumerating all the solutions and print them, and i noticed practically that the library find all the feasible solutions 2 minutes, and actually the last one is the optimal, but the library never exists and continues in explore not finding any other solutions for days, literally days even in on 32 cores machine, and increasing the used memory day by day. The last log line is:

#Bound  24.35s best:20    next:[21,22]    bool_core num_cores:2 [core:2 mw:1 d:5] assumptions:1 depth:6 fixed_bools:0/151

The maximum score is 25, and the 20 reached is indee the best possible for this configuration. So I wonder what is the CP-SAT solver actually doing? Isn't it realizing that what it found is indeed the optimal solution? How can I help the solver to end the computation realizing the optimal?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Please double check spelling and grammar before posting your question. It's also best to split your text into paragraphs. $\endgroup$
    – Rob
    Apr 26, 2022 at 16:29

1 Answer 1

Reset to default
1
$\begingroup$

Proving optimality is where the NP-Hard part is. A lot of small job-shops are still open (meaning not proven). In your case, you have a maximization objective. You have found a feasible value with objective 20, and CP-SAT has proven that there are no solutions higher than 22.

The rest is just hard, exponential search or proof.

Improve this answer
$\endgroup$
3
  • $\begingroup$ from what can i deduce CP-SAT has proven there are no solutions higher than 22? because i am trying to find a criteria to terminate the search,currently a rough timeout is not the best solution $\endgroup$
    – Joel
    Apr 27, 2022 at 7:28
  • $\begingroup$ Yes. The best solution found is 20. The next solution, if it exists, will belong in the interval [21..22]. $\endgroup$
    – Laurent Perron
    Apr 27, 2022 at 7:40
  • $\begingroup$ thanks for your reply. yes i got that the best solution found is at 20, so if i understood correctly there is no criteria to decide stop the search there and i should reply on a smart timeout $\endgroup$
    – Joel
    Apr 27, 2022 at 7:44

Your Answer

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

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