OR-TOOLS google 如何告诉求解器在达到某个结果时停止

Question

我有一个简单的 3d 分配问题。我正在为成本矩阵随机生成 0 到 100 之间的整数。

我注意到，当问题的规模足够大时，比如 40 个分配。（40X40X40 成本矩阵）。总成本达到 0。这是有道理的。

随着矩阵变大，我假设有更多方法可以达到预期的结果，我不希望求解时间呈指数增长。但 id 确实如此。

我认为这是因为算法在绝对确定其最优之前不满足于零结果。

我的问题是有没有办法告诉求解器在达到一定的总成本时停止？我没有在文档中找到该选项

当我尝试限制时间时

solver.SetTimeLimit(TIME)

求解器根本找不到解决方案。

我尝试添加其中一个答案中建议的约束（总成本>=0），但没有效果。

为 20X20X20 问题添加以下行时

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

求解器无法找到解决方案但是当添加

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

它找到总成本为 4 的解决方案为什么它不能找到与第一个约束相同的解决方案？

以及如何让它在达到 0 时停止？

Answer 1

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

没有达到您的预期。 solver.Objective() 是 MPObjective 类型的 class。在其上调用 Value() 检查是否已找到解决方案，如果未找到解决方案，则 returns 0。

所以在实践中，你正在执行：

solver.Add(0 >= 0)

这是一个无操作。

为了限制objective，你应该创建一个整数变量new_var从0到sum(cost_coefficients)，然后添加new_var = sum(cost_coefficients * bool_vars)，最后最小化new_var.

Answer 2

有一个 link 解决方案 - https://github.com/google/or-tools/issues/1439

您需要设置 RoutingMonitor Class 并连接 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)

并连接到求解器：

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

solution = routing.SolveWithParameters(search_parameters)

OR-TOOLS google 如何告诉求解器在达到某个结果时停止

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

python

or-tools