Terminating cp-sat search (python) when no new solution for specified timeout

Simon Jesenko

unread,

May 14, 2019, 8:16:37 AM5/14/19

to or-tools-discuss

Hi,

is there a way to terminate cp-sat search in Python if no improved solution is obtained for some predefined timeout? I am using individual solver runs for local search, and if no improvement is found for some time, I would like to stop current search and start new search in new neighbourhood.

`max_time_in_sec` is not well suited as I do not know in advance how solution will progress in each neighbourhood. There is `StopSearch()` in CpSolverSolutionCallback.OnSolutionCallback, which can however only be called when new solution is obtained. I would like to stop search before next solution is obtained...

Is it maybe possible to store reference to SolutionCallback and call `StopSearch()` after some timeout from another thread? I tried using `Timer`, and delayed call to `StopSearch` worked for small timeouts (e.g. 1 sec), however for larger timeouts, solver just stops responding and does not terminate...

Best regards,

Simon

Simon Jesenko

unread,

May 14, 2019, 8:46:43 AM5/14/19

to or-tools-discuss

I did some more testing and uncovered an unrelated bug in my threading code that called `StopSearch` on timeout. Now the solution outlined above (ie. calling StopSearch from another thread) does indeed work for my use case!

Thank you for this great library!

Best regards,

Simon

Laurent Perron

unread,

May 14, 2019, 9:27:22 AM5/14/19

to or-tools-discuss

So, short answer, yes you can call StopSearch() asynchronously.

--
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/da88bab7-c12f-4f8a-af01-4d422fa6e240%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Simon Jesenko

unread,

May 14, 2019, 1:45:18 PM5/14/19

to or-tools-discuss

I guess my solution does not work after all...

Python interpreter seems to be paused when solver is running, so method that should stop solver from another thread is executed only when next solution is found. Probably something related to GIL and SWIG? I have build or-tools from source, 7.1 on python 3.7.1, mac os.

EXAMPLE (this should print "Worker %i" every half second, however it prints only when new solution is found):

def worker():

i = 0

while True:

print('Worker: %s' % i)

i = i + 1

time.sleep(0.5)

t = threading.Thread(target=worker, args=())

t.start()

solver.SolveWithSolutionCallback(model, solution_callback)

On Tuesday, May 14, 2019 at 3:27:22 PM UTC+2, Laurent Perron wrote:

So, short answer, yes you can call StopSearch() asynchronously.

Le mar. 14 mai 2019 à 14:46, Simon Jesenko <simon....@gmail.com> a écrit :

I did some more testing and uncovered an unrelated bug in my threading code that called `StopSearch` on timeout. Now the solution outlined above (ie. calling StopSearch from another thread) does indeed work for my use case!

Thank you for this great library!

Best regards,
Simon

On Tuesday, May 14, 2019 at 2:16:37 PM UTC+2, Simon Jesenko wrote:
Hi,

is there a way to terminate cp-sat search in Python if no improved solution is obtained for some predefined timeout? I am using individual solver runs for local search, and if no improvement is found for some time, I would like to stop current search and start new search in new neighbourhood.

`max_time_in_sec` is not well suited as I do not know in advance how solution will progress in each neighbourhood. There is `StopSearch()` in CpSolverSolutionCallback.OnSolutionCallback, which can however only be called when new solution is obtained. I would like to stop search before next solution is obtained...

Is it maybe possible to store reference to SolutionCallback and call `StopSearch()` after some timeout from another thread? I tried using `Timer`, and delayed call to `StopSearch` worked for small timeouts (e.g. 1 sec), however for larger timeouts, solver just stops responding and does not terminate...

Best regards,
Simon

--
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...@googlegroups.com.

Simon Jesenko

unread,

May 14, 2019, 5:07:55 PM5/14/19

to or-tools...@googlegroups.com

Adding threading support to SWIG wrapper does enable concurrent execution of python threads, allowing stopping solver from other thread.

ortools/sat/python/sat.i:

<%module(directors="1) operations_research_sat

>%module(directors="1",threads="1") operations_research_sat

Not sure about other performance implications - according to SWIG docs, multithreading support has some performance implications, I guess only at the wrapper level, which should matter only for methods that are called many times. Solve* methods are probably non-issue, however for model building methods which might be called many times it might matter…

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/IQVyGoJTe9w/unsubscribe.
To unsubscribe from this group and all its topics, 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/964a39c7-8e25-4caa-af7b-e8b6c6ec23c8%40googlegroups.com.

Laurent Perron

unread,

May 14, 2019, 5:32:00 PM5/14/19

to or-tools-discuss

Thanks for the investigation.

I need to check for the implication of this flag.

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

De : Simon Jesenko <simon....@gmail.com>
Date : mar. 14 mai 2019 à 23:07
À : <or-tools...@googlegroups.com>

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/24391BCF-7C7E-464F-9957-327B19CD762C%40gmail.com.

Evann Smith

unread,

Jun 13, 2019, 2:45:35 PM6/13/19

to or-tools-discuss

I have a similar issue as the OP, where I am using individual solvers for local search. Similarly, I cannot well estimate in advance the required time. Do you:

1) Have any further thoughts on the suggestion of being able to stop search in between solutions?

2) Do you have recommendations for how to (ballpark) estimate search time based on inputs, particularly if (1) is not a good option?

Thanks,

Evann

To unsubscribe from this group and all its topics, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/964a39c7-8e25-4caa-af7b-e8b6c6ec23c8%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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...@googlegroups.com.

Simon Jesenko

unread,

Jun 13, 2019, 4:45:31 PM6/13/19

to or-tools...@googlegroups.com

Hi Evann,

I have been running custom build of or-tools with threading support for SWIG wrapper in production for a month now and noticed no performance penalty or other issues…Stoping of solver between solutions with enabled threading support works flawlessly.

Regards,

Simon

To unsubscribe from this group and all its topics, 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/8813a1a2-9323-4c26-8320-a22322c5d56d%40googlegroups.com.

Laurent Perron

unread,

Jun 14, 2019, 3:05:31 AM6/14/19

to or-tools-discuss

Thanks, I will add the flag for 7.2.

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/6AD5BE13-055C-4F57-8766-6DD66E79578E%40gmail.com.

Simon Jesenko

unread,

Jun 14, 2019, 3:11:39 AM6/14/19

to or-tools...@googlegroups.com

Great, thanks!

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeYtAp0Y-7_uW-MEEQ91xQ28MPGHyXZH_Zk%2B4zGbCQR4sg%40mail.gmail.com.

Evann Smith

unread,

Jun 14, 2019, 8:42:32 AM6/14/19

to or-tools-discuss

Thanks all!

On Friday, June 14, 2019 at 3:11:39 AM UTC-4, Simon Jesenko wrote:

Great, thanks!

On 14 Jun 2019, at 09:05, 'Laurent Perron' via or-tools-discuss <or-tools...@googlegroups.com> wrote:

Thanks, I will add the flag for 7.2.

Le jeu. 13 juin 2019 à 22:45, Simon Jesenko <simon....@gmail.com> a écrit :

Hi Evann,

I have been running custom build of or-tools with threading support for SWIG wrapper in production for a month now and noticed no performance penalty or other issues…Stoping of solver between solutions with enabled threading support works flawlessly.

Regards,
Simon

To unsubscribe from this group and all its topics, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8813a1a2-9323-4c26-8320-a22322c5d56d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/6AD5BE13-055C-4F57-8766-6DD66E79578E%40gmail.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/IQVyGoJTe9w/unsubscribe.

To unsubscribe from this group and all its topics, send an email to or-tools...@googlegroups.com.

Evann Smith

unread,

Sep 28, 2019, 12:53:12 PM9/28/19

to or-tools-discuss

Hi Laurent,

Was the ability to terminate when no new solution has been found for some specified time added in the new release? I've tried to look through myself, but haven't been able to sort it out.

Thanks,

Evann

On Friday, June 14, 2019 at 3:05:31 AM UTC-4, Laurent Perron wrote:

Thanks, I will add the flag for 7.2.

Le jeu. 13 juin 2019 à 22:45, Simon Jesenko <simon....@gmail.com> a écrit :

Hi Evann,

I have been running custom build of or-tools with threading support for SWIG wrapper in production for a month now and noticed no performance penalty or other issues…Stoping of solver between solutions with enabled threading support works flawlessly.

Regards,
Simon

To unsubscribe from this group and all its topics, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8813a1a2-9323-4c26-8320-a22322c5d56d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
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...@googlegroups.com.

Xiang Chen

unread,

Sep 28, 2019, 1:01:17 PM9/28/19

to or-tools-discuss

I'll leave my code for this here:

from threading import Timer
class ObjectiveEarlyStopping(cp_model.CpSolverSolutionCallback):
    def __init__(self, time_limit=10, print_objective=False):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._time_limit = time_limit
        self._print_objective = print_objective
        self._timer = None

    def on_solution_callback(self):
        if self._print_objective:
            print(self.ObjectiveValue())
        if not self._timer:
            self._timer = Timer(self._time_limit, self.stop)
            self._timer.start()
        else:
            self._timer.cancel()
            self._timer = Timer(self._time_limit, self.stop)
            self._timer.start()

    def stop(self):
        print(
            'Objective {} not changed in {} seconds, stopping solver...'.format(
                int(self.ObjectiveValue()), self._time_limit
            )
        )
        self.StopSearch()

Laurent Perron

unread,

Sep 29, 2019, 1:19:34 AM9/29/19

to or-tools-discuss

This is only called at each new solution.

What you can do is create a callback, pass it to search, and call.StopSearch() asynchronously from another thread.

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/f433e353-a2e0-432c-b57c-3f744b51ae5e%40googlegroups.com.

Evann Smith

unread,

Sep 30, 2019, 2:05:27 PM9/30/19

to or-tools...@googlegroups.com

Thanks Laurent.

Do you think you (or some other kind soul) might be able to provide a toy example?

Evann

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeb5dPTXkWLY9peui1yJEAvnuz9njgAZ2e0CMQh0ORxbEw%40mail.gmail.com.

Xiang Chen

unread,

Sep 30, 2019, 2:23:22 PM9/30/19

to or-tools...@googlegroups.com

My callback above does actually work, the thing is that it only starts the timer after the first solution has been found.

If you don't want that, you can change

self._timer = None

for

self._timer = Timer(self._time_limit, self.StopSearch)

on __init__

but feel free to try it and customize it if you want.

Xiang

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CADXFh5y7rZiYwSj12RMv%3Dm4AF3-go%3DOtgGc4Fi3VXx%3Dxk8vG_w%40mail.gmail.com.

Reply all

Reply to author

Forward