CP_SAT Callback types

[Nara Torres Moreira]

Hi, is there any other type of callback available in CP-SAT other than SolutionCallback?

I'm trying to find a way to interrupt the optimizer in case X seconds have passed without having found any new solution (including any solution at all).

Thanks!

[Laurent Perron]

You do not need a callback for this.

Which language ?

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

--
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/89fd2de0-4d51-43b7-b59a-e440a69880d1n%40googlegroups.com.

[Laurent Perron]

For instance, there is a StopSearch() method on CpSolver.

https://google.github.io/or-tools/python/ortools/sat/python/cp_model.html#CpSolver.StopSearch

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

[Nara Torres Moreira]

I'm using Python.

I currently use StopSearch if I want to stop when reaching a certain number of solutions, but that is done inside a callback that implements OnSolutionCallback, which is called only when new solutions are found. So I guess that doesn't work for me.

The only think I could imagine from what you said is that I need to do some parallelisation so that one thread can interrupt the CpSolver.Solve() call? Am I over complicating it?

[Laurent Perron]

No, this is the way to go.

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/6b62ee29-3237-4e36-9695-3301ab3f12b3n%40googlegroups.com.

[Louie Hext]

Something like this can work - https://github.com/stradivari96/ortools-utils/blob/master/ortools_utils/callbacks.py

It utilisws the Timer() function from threading to call a StopSearch() method after a desired time. 

The timer starts in the initialisation of the call back so it should work even if no solutions are found.

[Nara Torres Moreira]

Hi, thanks, but I don't see how this callback in the link using Timer could work for my purpose. The StopSearch() cannot be inside the SolutionCallback. Maybe I'm missing something?

I tried the following simple threading code, but it didn't work as I expected. The model continues after calling StopSearch(). I don't have much experience with parallelisation though, so I was wondering if anyone could spot something wrong I'm doing. Or should I use multi processing instead of multi threading?

Thank you!

    import time
    from threading import Thread    

    # more code here...

    def solve_with_ortools(self):
        self.solver = cp_model.CpSolver()
        solution_printer = SolutionPrinter(algorithm=self)
        self.solver.Solve(self.model, solution_printer)

    def solve_with_time_stop_control(self):
        thread = Thread(target=self.solve_with_ortools)
        thread.start()
        start = time.time()
        while True:
            elapsed = time.time() - start
            if elapsed > 30:
                print(f"Stopping thread after {elapsed} seconds")
                self.solver.StopSearch()
                break
        thread.join()

[Kai Müller]

Hi,

why don't you just set the maxTimeInSeconds? Solver will then stop when time is reached.

[Kai Müller]

Sorry for another answer:

In java it's done like this: https://google.github.io/or-tools/javadoc/com/google/ortools/sat/SatParameters.Builder.html#setMaxTimeInSeconds(double)

[Nara Torres Moreira]

Sorry, I know that my code is not complete yet for what I want, at this stage I just want to know how to force or-tools from another thread. Simply setting the time limit doesn't work for me because ultimately what I want is to "stop if X seconds have passed since the last solution improvement", which should be an easy condition to add given the StopSearch works.

[Pracheer Gupta]

If setMaxTimeInSeconds doesn’t work because you do not how long it will be before you stop seeing significant progress (per your original message), one possible option could be to send a termination signal such as SIGINT to the solver thread whenever you see fit. (The behavior should be similar to pressing ctrl-c in which case you should see a graceful shutdown of the solver).

On Oct 4, 2022, at 4:20 PM, Kai Müller <kai.m...@soobr.ch> wrote:

Sorry for another answer:

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/af3829f4-58cf-4f63-b1b9-94170ce0514cn%40googlegroups.com.

[Laurent Perron]

It could be another problem, that is the solver slow to stop.

If you launch search (without this extra code), and type Ctrl-C. Does the search stop fast ?

Do you see the solver exit search cleanly ?

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/0067b187-3d9d-4d11-b5d9-cceb2118dc52n%40googlegroups.com.

[Louie Hext]

The StopSearch() is not called by the call back but by the Timer() function, this calls a function after a given number of settings. So in this case you pass the StopSearch() to the Timer() with X of seconds ( "stop if X seconds have passed since the last solution improvement ") . If a solution is found in under X seconds, the Timer() will be restarted, if not the  StopSearch()  will be called from another thread. 

Its been a while since i've used that code but its intended to solve your exact issue.

[Xiang Chen]

Here is an example with a simple callback that works (you can ignore the code that is grayed out):

from threading import Timer
from itertools import permutations

from ortools.sat.python import cp_model


class ObjectiveEarlyStopping(cp_model.CpSolverSolutionCallback):
    def __init__(self, timer_limit: int):
        super(ObjectiveEarlyStopping, self).__init__()
        self._timer_limit = timer_limit
        self._timer = None
        self._reset_timer()

    def on_solution_callback(self):
        self._reset_timer()

    def _reset_timer(self):
        if self._timer:
            self._timer.cancel()
        self._timer = Timer(self._timer_limit, self.StopSearch)
        self._timer.start()

    def StopSearch(self):
        print(f"{self._timer_limit} seconds without improvement")
        super().StopSearch()


if __name__ == "__main__":
    model = cp_model.CpModel()
    nodes = range(1, 100)
    all_arcs = []

    literals = {}
    for i in nodes:
        literals[0, i] = model.NewBoolVar(f"0 -> {i}")
        literals[i, 0] = model.NewBoolVar(f"{i} -> 0")
        all_arcs.append([0, i, literals[0, i]])
        all_arcs.append([i, 0, literals[i, 0]])

    for i, j in permutations(nodes, 2):
        literals[i, j] = model.NewBoolVar(f"{i} -> {j}")
        all_arcs.append([i, j, literals[i, j]])

    model.AddCircuit(all_arcs)
    model.Maximize(sum(literals[i, j] * abs(i - j) for i, j in permutations(nodes, 2)))

    solver = cp_model.CpSolver()
    solver.parameters.cp_model_presolve = False
    solver.parameters.num_search_workers = 1
    solver.parameters.log_search_progress = True

    solver.SolveWithSolutionCallback(model, ObjectiveEarlyStopping(5))

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/071456f0-9213-4e70-b077-a6a210d131d2n%40googlegroups.com.

[Nara Torres Moreira]

Ohh brilliant! Super thank you both, that works indeed (the solution proposed by louie and xiang10 was the same)!

You saved my day :)

[Sysjack]

How would I cancel the timer if the optimal solution is reached first? I haven't been able to figure it out.

[Xiang Chen]

The program would just continue after the solve, but if you really need to cancel it:

callback = ObjectiveEarlyStopping(5)
solver.SolveWithSolutionCallback(model, callback)
callback._timer.cancel()

you can also add an attribute to the callback class to check if it was cancelled or not, etc.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ce10f38d-e63b-4be8-9349-b4cb589c3445n%40googlegroups.com.

[harryh...@gmail.com]

Hi,

why don't you just set the maxTimeInSeconds? Solver will then stop when time is reached.

[PC See]

Her original question is "...  in case X seconds have passed without having found any new solution  ... "

Let say solutions found is already S1, S2, S3, .... [then, if take longer than time limit, X] ... break

It could be taking somewhere near to X in between S1---S2, S2---S3. Setting maxTimeInSeconds = X will yield a different outcome