Or-tools: CP Sat: Maximize/Minimize early stopping on good solution

[Phibedy]

I searched the source and could not find any method to stop the solver if the cost function meets a threshold or a BoolVar is true (related to #651).

Does adding an objective function change the search strategy, or does it just brute force all solutions?
Adding an objective function causes the CpSolverSolutionCallback to only be called if the objective is optimized and then only once, even if some results have the same objective value.

If it just brute forces the "optimal" solution, adding a IntVar(INT_MIN,INT_MAX) which represents objective instead of calling model.Minimize(...) function and a CpSolverSolutionCallback which evaluates the objective (terminates the process if threshold is reached) for each solution would be the way to go? My problem has a lot of solutions so finding a "optimal" solution is not possible. I just want a "good" one.

Adding a constraint like model.Add(objective < threshold) isn't something I would like to do as I still want a result if there are only bad solutions.

[lperron]

Stopping early is doable in C++.
Look at:

https://github.com/google/or-tools/blob/master/ortools/flatzinc/cp_model_fz_solver.cc#L950

Basically, you register a std::atomic on a time limit attached to the
model.
Setting that to true will stop the search.

For the threshold, just add a constraint obj >= theshold - 1 and minimize.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le sam. 11 août 2018 à 04:16, Phibedy [e-mail] a écrit :

I searched the source and could not find any method to stop the solver if
the cost function meets a threshold or a BoolVar is true (related to #651
https://github.com/google/or-tools/issues/651).

Does adding an objective function change the search strategy, or does it
just brute force all solutions?
Adding an objective function causes the CpSolverSolutionCallback to only
be called if the objective is optimized and then only once, even if some
results have the same objective value.

If it just brute forces the "optimal" solution, adding a
IntVar(INT_MIN,INT_MAX) which represents objective instead of calling
model.Minimize(...) function and a CpSolverSolutionCallback which
evaluates the objective (terminates the process if threshold is reached)
for each solution would be the way to go? My problem has a lot of solutions
so finding a "optimal" solution is not possible I just want a "good" one.

Adding a constraint like model.Add(objective < threshold) isn't something
I would like to do as I still want a result if there are only bad solutions.

—
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/804, or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17aCyMZ5a3J-X_rkm5R6CrN7Wizz9ks5uPrzxgaJpZM4V5Ies
.

[Phibedy]

@lperron that's nice, didn't know one could add external bools. Never checked the C++ interface before but it seems to be more powerful. But I think I am or there is something missing:

What I would like to do:

while(timer < time_limit):
    state = solve(...)
    if objective(state) < threshold:
        break

• If I minimize the objective, the solution callback is not called so I can't trigger the std::atomic<bool> on a threshold, so it would run till timer >= time_limit
• If I add a constraint obj >= threshold - 1 I would still need to stop it somehow if the threshold is satisfied if I use minimize, so I would just need to call solve? In addition I would not get a feasible solution if the threshold can't be satisfied in time.

A workaround I could think of is calculating the solution step by step (decrease the threshold). But I think it would be rather slow as it would always start with a new solution instead of reusing the old solution. Is it possible to reuse a solution?

model = ...
objective = ...
start = timer()
while True:
    time_limit = timer()-start
    #set time limit (C++ needed as not possible in python)
    state = solver.Solve(model)
    if state != 2: #no new feasible solution
      break
    obj_val = solver.Value(objective)
    model.Add(objective<obj_val)

[lperron]

This is not optimal as you loose the state of the sat solver after adding the new objective part.
The model do support hinting. You need to access the underlying cp_model proto inside the CpModel class. But even then, you loose the conflicts learned previously.

Why don't you just add

model.add(objective >= threshold)

This will stop as soon as objective < threshold. It is a bit weaker than what you proposed, but could do the trick.

The correct solution is to implement StopSearch() in the cp solution callback. I need to to it correctly.

[Phibedy]

Thank you for the explanation. The hinting sounds good, I will give it a try. The problem is, I don't know a "good" threshold. It's more like, after some time, the threshold is good enough.

[lperron]

I have pushed StopSearch in java, C#
I need to tweak the python layer to make it work, it should happen this
week.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le jeu. 30 août 2018 à 11:20, Phibedy [e-mail] a écrit :

Thank you for the explanation. The hinting sounds good, I will give it a
try. The problem is, I don't know a "good" threshold. It's more like, after
some time, the threshold is good enough.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/804#issuecomment-417250929,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17Xllcq5kOw2j6OgMMO41MYxJD_5rks5uV65NgaJpZM4V5Ies
.

[Phibedy]

Thank you very much :+1:

[lperron]

Implemented and documented in all 4 languages.

[(https://github.com/google/or-tools/blob/master/ortools/sat/doc/solver.md#stopping-search-early)]

Closing the issue.

[Phibedy]

That's great, when will the pip package be updated?

[lperron]

early september I guess.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le jeu. 30 août 2018 à 18:49, Phibedy [e-mail] a écrit :

That's great, when will the pip package be updated?

—
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/804#issuecomment-417388838,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17WCqTBQ2uLYDLv8PFVNJREv1Hv1Zks5uWBevgaJpZM4V5Ies
.