BestObjectiveBound - How to use it

[Kai Müller]

Hi all,

I am currently experimenting with stopping the solver early. I set a solutionlimit like in the tutorial. I then stumbled about objective value and best objective bound.

My Question:

What does the return value of bestObjectiveBound()-method mean? How does it differ from objective value?

My guess is, that this is the best possible value, which somehow got calculated. Why is the first bestObjectiveBound so high and than decreases?  How is it calculated?

Many greetings and thanks in advance!

[Priidik Vilumaa]

Hi, I assume you are talking about CP-SAT.

You're on the right track. I'd say it is the optimistic approximation of the halfway solved problem. And as the solver progresses it proves that "turns out that the previous approximation is unreachable, and the current (possibly reachable) optimistic number is somewhat lower". You could search for basics of branch and bound, plenty of videos out there showing the bounding process. 

As for the early stopping you might want to try "stopping if no improving solution has been found in X seconds". We use such an approach in practice and really like it. Couldn't find it in github any more but I believe this was posted by stradivari:
```

from threading import Timer, Lock

class EarlyStoppingLogger(cp_model.CpSolverSolutionCallback):
    """Stop solving if the solution does not improve

    Arguments:
    - early_stopping_timeout: stop solving if this many seconds pass
      without improvement

    """

    def __init__(self, early_stopping_timeout=10):
        super().__init__()
        self.early_stopping_timeout = early_stopping_timeout
        self.timer = None
        self.lock = Lock()

    def on_solution_callback(self):
        "Log solution and set next timeout"
        with self.lock:
            if self.timer:
                self.timer.cancel()
            self.timer = Timer(self.early_stopping_timeout, self.stop)
            self.timer.start()

    def stop(self):
        "Stop solving"
        self.StopSearch()

    def clean(self):
        "Clean up timer"
        if self.timer:
            self.timer.cancel()

...

callback = EarlyStoppingLogger(early_stopping_timeout)
solver.Solve(model, callback)
callback.clean()

```

Best,

Priidik

[Laurent Perron]

In case of minimization, the best objective bound is a proven lower bound of the optimal objective value. 

When maximizing, it is an upper bound. 

--
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/ee476525-5f96-4d74-a8d1-0536443a79d4n%40googlegroups.com.

[Kai Müller]

Thank you really much for the clarification. And yes I am using the CP-SAT Solver in Java.

About the early stopping:

How do you guys use it in practice? Do you consider both values (objectiveValue and bestObjectiveBound)? I am solving many problems sequential and the objectiveValue vary by huge numbers per problem. My first guess would be to check if the objective bound doesn't increase within a certain percentage and then stop it. Do you have other ideas? Maybe how to stop it with the bestObjectiveBound?

Thanks again!

[Kai Müller]

Oh. Forgot to include my last Question. I noticed, that a problem solution can be optimal even without reaching the estimated bestObjectiveBound. How is determined if a solution is optimal?

Thank you!

Best,

Kai

[Priidik Vilumaa]

Hi,

for the early stopping we just use the objective value. I think in optimization in general, quite often the linear relaxation (best bound) is far from the actual optimal solution. Hence I personally do not typically put any emphasis on that. We currently accept any improvement to restart the early stopping timer, but we too have pondered to make only a non-insignificant improvement restart the timer. I.e. the improvement has to be big enough to be considered an improvement.

I believe there is a tolerance. I.e. if you're maximizing and have a solution that's 99.999999% of the best bound, then that's "optimal enough".

Best,

Priidik

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

For what its worth, in the transportation solver, I have also used a solution counter to stop the solver, rather than a timer. I found timers were more dependent upon hardware, while a counter was more stable. Regardless of whether I am running on my laptop or my server, 10000 repeats of no improvement to the solution (for example) will return the same final result.

And I accept any improvement as an improvement. If I want more or less tolerance, then I feel that should be built into the model formulation. No sense setting up a solver that is accurate to 1 second if I quit after not seeing an improvement of more than 1 minute. The 1 minute accuracy formulation will run faster, so if that is what I want, that is what I set up, and an improvement of 1 is an improvement.

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/ee476525-5f96-4d74-a8d1-0536443a79d4n%40googlegroups.com https://groups.google.com/d/msgid/or-tools-discuss/ee476525-5f96-4d74-a8d1-0536443a79d4n%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/731a7388-9319-4e15-bf98-720cb5d0f714n%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Kai Müller]

Hi James,

thanks for your input. Sounds interesting. In my case I don't want to give more than 3 minutes solving time. That's the most I can use. Furthermore I noticed, that in the first few solutions the objective value does huge jumps (something between 500k and 1 mio). After that the next solutions "just" provides a objective value increase of something around 1-1000. So my next try would be to setup a percentage of increasement limit. If the solution doesn't increase above the percentage of increasement limit I will stop the solver. However, there are a few more things I need to consider. Something like that it could happen, that the solution increases only 500 on the first step and than 1 mio on the next.

Anyway... Regards,

Kai