search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.18k stars 2.12k forks source link

learning from external solution during search #1782

Closed gregy4 closed 4 years ago

gregy4 commented 4 years ago

Hello, my problem is modeled in a constraint solver and cp-sat solver so I receive valid solutions from both solvers. I see that solvers are weak in different areas. Constraint solver has problem to find better results no matter how much time computation time is given, cp-sat solver is much more sensitive to a horizon (how long schedule can be) so bad estimate can lead to no solution is found or iteration close to optimum takes too much time.

The problem with a horizon in cp-sat can be for me solved by an event "find only solutions that are shorter than given value" when I try to minimize makespan and execute solvers in parallel. Something that is already done for parallel execution of search workers.

Is it possible to implement this variant ? For long computations it makes sense to me to learn new bounds minimally for objective function during search when alternative solver find some solutions faster.

Thanks, Jan

lperron commented 4 years ago

Short answer, you can launch the CP and CP-SAT in parallel, then restart the CP-SAT model with a new upper bound on the makespan if the CP solver finds an interesting solution. You can also use this solution as a hint for the next CP-SAT search.

Long answer, injecting objective bounds is on our roadmap. This is already part of the protocol between workers, but the API is not ready for prime time. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 13 déc. 2019 à 10:22, gregy4 notifications@github.com a écrit :

Hello, my problem is modeled in a constraint solver and cp-sat solver so I receive valid solutions from both solvers. I see that solvers are weak in different areas. Constraint solver has problem to find better results no matter how much time computation time is given, cp-sat solver is much more sensitive to a horizon (how long schedule can be) so bad estimate can lead to no solution is found or iteration close to optimum takes too much time.

The problem with a horizon in cp-sat can be for me solved by an event "find only solutions that are shorter than given value" when I try to minimize makespan and execute solvers in parallel. Something that is already done for parallel execution of search workers.

Is it possible to implement this variant ? For long computations it makes sense to me to learn new bounds minimally for objective function during search when alternative solver find some solutions faster.

Thanks, Jan

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1782?email_source=notifications&email_token=ACUPL3K4TIIQ2TE7C4RBXWLQYNH6ZA5CNFSM4J2KGC3KYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IAIUODQ, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3K4GEVG24DDMZRW44DQYNH6ZANCNFSM4J2KGC3A .

gregy4 commented 4 years ago

Thanks Laurent To clarify it, by restart you mean start cp-sat solver again with new bound ? I like to answer this kind of questions by myself, but do you have some estimate when injecting of bounds will be available ? 2020 or later ?

lperron commented 4 years ago

yes for the first question.

For the timeline, I simply do not know. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 13 déc. 2019 à 13:12, gregy4 notifications@github.com a écrit :

Thanks Laurent To clarify it, by restart you mean start cp-sat solver again with new bound ? I like to answer this kind of questions by myself, but do you have some estimate when injecting of bounds will be available ? 2020 or later ?

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1782?email_source=notifications&email_token=ACUPL3KFJAEFLGVT7SPZ6ELQYN32XA5CNFSM4J2KGC3KYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEGZZ7DQ#issuecomment-565419918, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3PN23GNQYW6UAXIRHDQYN32XANCNFSM4J2KGC3A .