Job Shop Scheduling : Optimal solution

[Alex Nea Kameni]

Please, how the SAT solver proves the optimality of the present value of the objective in "Job Shop Scheduling" problems ?

[Laurent Perron]

Like anybody else, by proving that optimal_value - 1 is not feasible.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le dim. 12 sept. 2021 à 12:22, Alex Nea Kameni <kameni...@gmail.com> a écrit :

Please, how the SAT solver proves the optimality of the present value of the objective in "Job Shop Scheduling" problems ?

--
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 on the web visit https://groups.google.com/d/msgid/or-tools-discuss/07eff029-b7c3-4726-b6ec-1564b8410654n%40googlegroups.com.

[Laurent Perron]

Was there a deeper question?

[Alex Nea Kameni]

Hi Laurent,

You have answered my question. I hadn't just thought of this approach

Thank you

[Alex Nea Kameni]

I was thinking more of an estimation of the optimal value and if we manage to reach it, then we have reached the optimal.

[Laurent Perron]

you mean the lower bound ? 

If yes, CP-SAT has made a lot of progress in the last year by adding better linear relaxations, and linear scheduling cuts that help a lot.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9106e071-db83-4005-9c15-43f9a641fe4fn%40googlegroups.com.