Local Search in CP-SAT

[C8504]

Hi Experts,

Do we have local search algorithms[NOT LNS] and parameter to control it in CP-SAT? Thanks.

John

[lperron]

No. For a simple reason, this is hard.

A good illustration is that there are no LS implementation in MIP solvers, and CP-SAT is a superset of a MIP solver.

We welcome any idea that has a decent chance of success.

[lperron]

We now have. It is violation based, and inspired by the paper feasibility jump. It is on be default starting v9.7 to find initial solution. You can specify how many workers to allocate with the num_violation_ls parameter. The default is 0. It is disabled for models containing no_overlap_2d. It is only optimized for the linear case (linear, bool_or, bool_and, at_most_one, exactly_one).

[ofek]

It looks like there is a new state-of-the-art technique that performs better than feasibility jump in all circumstances https://drops.dagstuhl.de/storage/00lipics/lipics-vol307-cp2024/LIPIcs.CP.2024.19/LIPIcs.CP.2024.19.pdf

[lperron]

I ran some comparison. it is not better than what we have in CP-SAT. And incidentally, they did not compare to violationLS at the conference. Le mar. 26 nov. 2024, 18:01, Ofek Lev ***@***.***> a écrit :

…

It looks like there is a new state-of-the-art technique that performs better than feasibility jump in all circumstances https://drops.dagstuhl.de/storage/00lipics/lipics-vol307-cp2024/LIPIcs.CP.2024.19/LIPIcs.CP.2024.19.pdf — Reply to this email directly, view it on GitHub <#3387 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3P3Z7WENOKG7SCK2YT2CSZQZAVCNFSM6AAAAABSRBEFTOVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCMZYGY3DMMQ> . You are receiving this because you modified the open/close state.Message ID: ***@***.***>

[ofek]

Oh very interesting, thanks for the heads up! I'm in the process of researching optimization software and trying to figure out what is most performant (use case is healthcare employee scheduling). All of the quotes I've gotten for proprietary solutions have been extraordinarily high (Gurobi, Cardinal Optimizer, Hexaly, Timefold) and I can't find any benchmarks for the proprietary solutions except for Hexaly which they publish themselves. I found these benchmarks from a researcher but they don't include proprietary solutions nor or-tools.

[lperron]

Look at shift_schedulinh_sat.py example. Very popular in nurse rostering Le mar. 26 nov. 2024, 18:22, Ofek Lev ***@***.***> a écrit :

…

Oh very interesting, thanks for the heads up! I'm in the process of researching optimization software and trying to figure out what is most performant (use case is healthcare employee scheduling). All of the quotes I've gotten for proprietary solutions have been extraordinarily high (Gurobi, Cardinal Optimizer, Hexaly, Timefold) and I can't find any benchmarks for the proprietary solutions except for Hexaly which they publish themselves. I found these benchmarks <https://plato.asu.edu/bench.html> from a researcher but they don't include proprietary solutions nor or-tools. — Reply to this email directly, view it on GitHub <#3387 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3KK3EK3YKWHE5YYWHL2CS4ADAVCNFSM6AAAAABSRBEFTOVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCMZYGY4DQNI> . You are receiving this because you modified the open/close state.Message ID: ***@***.***>

[Mizux]

https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py

[ofek]

Yes thank you. That was the first thing that I tried but on my machine it takes approximately 10 seconds for that very small example.