Stop if no progress in last x seconds?

[Solver Max]

I'm solving a CVRPTW model with a variety of data sets and settings. Generally the model returns a good - though perhaps not optimal - solution when given a time limit of, say, 60 seconds.

If the model has a longer time limit, then it may find a better solution. The problem is that I don't know how large a time limit to set - 5 minutes, an hour, 8 hours? I don't want to wait 8 hours to find that no progress was made after the first few minutes.

So, is there a way to instruct the solver to stop if it hasn't improved the objective function value in the last x seconds? e.g. set a time limit of 3600 seconds, with a stopping rule if there is no progress in the most recent 300 seconds.

[blind.line]

I’m pretty sure this has been answered several times on this list, or in the GitHub discussions. 

You can do exactly what you say…setup a solution callback that will quit if the solution has not improved significantly since the last callback. 

Honestly, me searching my code to recall how I do it would take just as long as you searching the mailing list. But sometimes the key phrases are polluted in the search so if you come up empty ask again. 

James

On Aug 24, 2022, at 16:20, Solver Max <con...@solvermax.com> wrote:



I'm solving a CVRPTW model with a variety of data sets and settings. Generally the model returns a good - though perhaps not optimal - solution when given a time limit of, say, 60 seconds.

If the model has a longer time limit, then it may find a better solution. The problem is that I don't know how large a time limit to set - 5 minutes, an hour, 8 hours? I don't want to wait 8 hours to find that no progress was made after the first few minutes.

So, is there a way to instruct the solver to stop if it hasn't improved the objective function value in the last x seconds? e.g. set a time limit of 3600 seconds, with a stopping rule if there is no progress in the most recent 300 seconds.

--
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/a60cd938-04f1-440a-953d-5fc7c8f08f25n%40googlegroups.com.

[Solver Max]

I haven't found anything that works with the Python routing constraint solver. I'd appreciate any pointers you can provide.

[blind.lin...@gmail.com]

I think this looks promising:

https://github.com/google/or-tools/discussions/2880#discussioncomment-1582227

Again, I think the problem is not knowing what to look for... I searched for "AddSearchMonitor" in github, but if you look for things like stop solver early etc you'll get nothing...or rather, lots of useless things

I do have a full working solution somewhere, so if this doesn't help you enough please repost and I'll dig it up.

Regards,

James

-- 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/a60cd938-04f1-440a-953d-5fc7c8f08f25n%40googlegroups.com https://groups.google.com/d/msgid/or-tools-discuss/a60cd938-04f1-440a-953d-5fc7c8f08f25n%40googlegroups.com?utm_medium=email&utm_source=footer .

-- 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/c1c8324e-0db9-4068-bf73-6fe67f8ebd72n%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Solver Max]

I saw a version of that code from 2013 https://groups.google.com/g/or-tools-discuss/c/zl76yIFHx0s/m/jtcodtx_DwAJ

However, I can't get it to work. It fails on the line:

     bestCollector.AddObjective(routing.CostVar()

with the error:

    SystemError: <built-in function SolutionCollector_AddObjective> returned NULL without setting an error

[Solver Max]

I've devised a solution, building on the code at https://groups.google.com/g/or-tools-discuss/c/P9GCXYsFi3c/m/LMKpSSsvAAAJ

The current and best objective function so far is output every ProgressIncrement seconds (or longer), and the solver stops after MaxNoChange (or longer) seconds with no improvement in the objective function.

There is also an absolute time limit, specified as a search parameter. Under either stopping condition, the detailed results are output via a solution printer.

This code has not been thoroughly tested, but hopefully it will be useful to anyone trying to do something similar. Suggestions for improvement are welcome.

import time as time

import sys

MaxNoChange = 60       # Stop searching if no improvement in objective (seconds)
ProgressIncrement = 5  # Minimum gap for objective progress output (seconds)

...

class SolutionCallback(object):
    def __init__(self, model, MaxNoChange, ProgressIncrement):
        self.model = model
        self.MaxNoChange = MaxNoChange
        self.ProgressIncrement = ProgressIncrement
        self.start_time = time.time()
        self.solution_count = 0
        self.LastTime = 0
        self.LastBestTime = 0
        self.BestObj = sys.maxsize
        print(" Time  Solution    Objective         Best")
        print("-----------------------------------------")
    def __call__(self):
        self.solution_count += 1
        CurrObj = self.model.CostVar().Max()
        CurrTime = time.time()

        if (CurrObj == self.BestObj) and (CurrTime - self.LastBestTime > self.MaxNoChange):
            print(f"{int(CurrTime - self.start_time):>5,} {self.solution_count:>9,} {CurrObj:>12,} {self.BestObj:>12,}")
            print(f"\nStopped due to no improvement for {CurrTime - self.LastBestTime:.0f} seconds\n")
            self.model.solver().FinishCurrentSearch()          
        else:
            if CurrObj < self.BestObj:
                self.BestObj = CurrObj
                self.LastBestTime = CurrTime
            if (CurrTime - self.LastTime) >= self.ProgressIncrement and (self.BestObj < sys.maxsize):
                print(f"{int(CurrTime - self.start_time):>5,} {self.solution_count:>9,} {CurrObj:>12,} {self.BestObj:>12,}")
                self.LastTime = CurrTime

def main():

...

    callback = SolutionCallback(routing, MaxNoChange, ProgressIncrement)  # Before call to routing solver
    routing.AddAtSolutionCallback(callback)

The output looks like:

 Time  Solution    Objective         Best
-----------------------------------------
    0         1    4,855,602    4,855,602
    5        36    2,355,388    2,355,388
   13        45    1,991,213    1,991,213
   19        48    1,991,213    1,991,213
   25        54    1,956,171    1,956,171
   32        59    2,145,557    1,946,457
   38        69    1,835,247    1,835,247
   44        72    1,835,247    1,835,247
   51        74    1,835,247    1,835,247
   58        76    1,835,247    1,835,247
   64        79    1,835,247    1,835,247
   71        82    1,835,247    1,835,247
   78        85    1,835,247    1,835,247
   84        87    1,835,247    1,835,247
   91        90    1,835,247    1,835,247
   94        91    1,835,247    1,835,247

Stopped due to no improvement for 61 seconds

[Fadi Younes]

I've been using your EarlyStop code above for a long time, but sometimes a problem happens that no more solutions are found, so the callback isn't even triggered to make the check and call "self.model.solver().FinishCurrentSearch()". And as a result, the VRP solver keeps running until the time limit is reached. Any idea to solve this issue? 

[sascha...@gmail.com]

In C++ world, there is https://github.com/google/or-tools/blob/v9.4/ortools/constraint_solver/constraint_solver.h#L3757 "PeriodicCheck" which should be the right abstraction/approach. This is a SearchMonitor.

But it seems, the python-wrapper does not wrap it: https://github.com/google/or-tools/blob/v9.4/ortools/constraint_solver/python/constraint_solver.i#L1305

Assuming a SearchMonitor allows to call FinishCurrentSearch like SolutionCallback does, there are enough events to somewhat move towards a periodic check: https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp

I would expect something like BeginNextDecision and co. to be called often enough.