OR-TOOLS google how to tell the solver to stop when reaching a certain result

Question

I have a simple 3d assignment problem. I'm randomly generating integer numbers between 0 and 100 for a cost matrix.

I've noticed that when the size of the problem is large enough say 40 assigments.(40X40X40 cost matrix).The total cost reaches 0. which makes sense.

as the matrix grows bigger I assume there are more ways to reach the desired results and I Don't expect the solve time to rise exponentially. But id does.

I assume this is because the algorithm isn't satisficed with a zero result until it is absolutely sure its optimal.

My question is is there a way to tell the solver to stop when it reaches a certain total cost? I haven't found that option in the docs

when I try to limit the time

solver.SetTimeLimit(TIME)

the solver simply cant find a solution.

I tried adding the constraint suggested in one of the answers (total cost>=0) but it had no effect.

when adding the following line for a 20X20X20 problem

solver.Add(solver.Objective().Value() >= 1)

the solver cant find a solution but when adding

solver.Add(solver.Objective().Value() >= 0)

it find a solution with total cost of 4 why can't it find the same solution with the first constraint?

and how do I tell it to stop when reaching 0?

Answer 1

 solver.Add(solver.Objective().Value() >= 0)

does not do what you expect. solver.Objective() is a class of type MPObjective. Calling Value() on it checks is a solution has been found, and returns 0 if this is not the case.

So in practice, you are executing:

solver.Add(0 >= 0)

which is a no op.

In order to limit the objective, you should create one integer variable new_var from 0 to sum(cost_coefficients), then add new_var = sum(cost_coefficients * bool_vars), and finally minimize new_var.

Answer 2

there is a link to solution - https://github.com/google/or-tools/issues/1439

You need to set RoutingMonitor Class and connect with AddAtSolutionCallback.

def make_routing_monitor(routing_model: pywrapcp.RoutingModel, stop_objective: int, failure_limit: int) -> callable:
    
    class RoutingMonitor:
        def __init__(self, model: pywrapcp.RoutingModel):
            self.model = model
            self._counter = 0
            self._best_objective = float('inf')
            self._counter_limit = failure_limit
            self._stop_objective = stop_objective

        def __call__(self):
            if self._stop_objective==self.model.CostVar().Min():
                self.model.solver().FinishCurrentSearch()
    
                        
    return RoutingMonitor(routing_model)

And connect to the solver:

routing_monitor = make_routing_monitor(routing, data['total_distance'] ,0)
routing.AddAtSolutionCallback(routing_monitor)

solution = routing.SolveWithParameters(search_parameters)