我正在利用CP-SAT求解器(ortools(解决整数编程问题。查看日志，我注意到求解器找到了实际上是最优的(稍后证明(解决方案，但在证明最优性方面花费了大量时间。从本质上讲，最佳现有解决方案和最佳界限之间的差距慢慢缩小。
如果MIP间隙%：(abs(objective-best_bound(/objective(<0.05，但没有帮助。由于收敛缓慢。
from ortools.sat.python import cp_model as cp
import time
class PrinterClass(cp.CpSolverSolutionCallback):
def __init__(self):
cp.CpSolverSolutionCallback.__init__(self)
self.__solution_count = 0
self.__start_time = time.time()
def on_solution_callback(self):
current_time = time.time()
objective = self.ObjectiveValue()
best_bound = self.BestObjectiveBound()
print("Solution %i, time = %f s, objective = %i, best_bound = %i" %
(self.__solution_count, current_time - self.__start_time,
objective, best_bound))
self.__solution_count += 1
if (abs(objective - best_bound) / objective) < 0.05:
print('Stop search')
self.StopSearch()
def total_num_solutions(self):
return self.__solution_count
我想尝试的是：如果最好的现有解决方案在10秒内没有改变(比如(，那么我想输出这个特定的可行解决方案并停止搜索。而不是求解者花费200秒(比如(试图缩小现有解决方案和最佳边界之间的差距。
例如，如果你看下面的日志，求解器会找到一个可行的解决方案(实际上是最优的，稍后会证明(，2.75秒时的解决方案#13，
Solution 13, time = 2.745947 s, objective = 2032, best_bound = 1479
然后再花费约25秒来证明它实际上是最优的，当求解器花费额外的10秒并且无法改进当前的现有解决方案时，我可以停止搜索并获得解决方案吗。低于点
#Bound 12.14s best:2032 next:[1532,2030] pseudo_costs
我只是想尝试一下，至少为了我的学习，有人能帮我吗？
以下是生成的日志：
Starting Search at 0.28s with 8 workers.
6 full subsolvers: [default_lp, no_lp, max_lp, reduced_costs, pseudo_costs, quick_restart]
Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, routing_random_lns_default, routing_path_lns_default, routing_full_path_lns_default, rins_lns_default, rens_lns_default]
#1 0.44s best:4884 next:[0,4883] no_lp fixed_bools:1/931
Solution 0, time = 0.435596 s, objective = 4884, best_bound = 0
#Bound 0.45s best:4884 next:[0,4882] no_lp
#2 0.46s best:4336 next:[0,4335] no_lp fixed_bools:1/935
Solution 1, time = 0.466841 s, objective = 4336, best_bound = 0
#Bound 0.47s best:4336 next:[0,4334] no_lp
#Bound 0.48s best:4336 next:[1278,4334] max_lp initial_propagation
#3 0.54s best:3972 next:[1278,3971] no_lp fixed_bools:1/939
Solution 2, time = 0.544969 s, objective = 3972, best_bound = 1278
#Bound 0.55s best:3972 next:[1278,3970] no_lp
#4 0.55s best:3492 next:[1278,3491] routing_random_lns_default(d=0.50 s=12 t=0.10 p=0.00)
Solution 3, time = 0.560597 s, objective = 3492, best_bound = 1278
#Bound 0.56s best:3492 next:[1278,3490] no_lp
#5 0.57s best:2968 next:[1278,2967] no_lp fixed_bools:1/944
Solution 4, time = 0.576220 s, objective = 2968, best_bound = 1278
#Bound 0.58s best:2968 next:[1278,2966] no_lp
#6 0.62s best:2944 next:[1278,2943] no_lp fixed_bools:1/949
Solution 5, time = 0.632293 s, objective = 2944, best_bound = 1278
#Bound 0.64s best:2944 next:[1278,2942] no_lp
#Bound 0.65s best:2944 next:[1352,2942] max_lp
#7 0.65s best:2876 next:[1352,2875] no_lp fixed_bools:1/950
Solution 6, time = 0.663560 s, objective = 2876, best_bound = 1352
#Bound 0.66s best:2876 next:[1352,2874] no_lp
#8 0.67s best:2648 next:[1352,2647] no_lp fixed_bools:1/954
Solution 7, time = 0.679179 s, objective = 2648, best_bound = 1352
#Bound 0.68s best:2648 next:[1352,2646] no_lp
#9 0.70s best:2420 next:[1352,2419] no_lp fixed_bools:1/957
Solution 8, time = 0.710431 s, objective = 2420, best_bound = 1352
#Bound 0.71s best:2420 next:[1352,2418] no_lp
#10 0.72s best:2396 next:[1352,2395] no_lp fixed_bools:1/958
Solution 9, time = 0.726056 s, objective = 2396, best_bound = 1352
#Bound 0.73s best:2396 next:[1352,2394] no_lp
#Bound 0.91s best:2396 next:[1356,2394] pseudo_costs
#11 0.94s best:2260 next:[1356,2259] no_lp fixed_bools:1/960
Solution 10, time = 0.960437 s, objective = 2260, best_bound = 1356
#Bound 0.96s best:2260 next:[1399,2259] max_lp
#Bound 0.97s best:2260 next:[1399,2258] no_lp
#12 0.98s best:2192 next:[1399,2191] no_lp fixed_bools:1/960
Solution 11, time = 0.991691 s, objective = 2192, best_bound = 1399
#Bound 0.99s best:2192 next:[1399,2190] no_lp
#Bound 1.46s best:2192 next:[1450,2190] reduced_costs
#Bound 1.87s best:2192 next:[1461,2190] reduced_costs
#13 2.18s best:2168 next:[1461,2167] default_lp fixed_bools:1/931
Solution 12, time = 2.183427 s, objective = 2168, best_bound = 1461
#Bound 2.19s best:2168 next:[1461,2166] no_lp
#Bound 2.24s best:2168 next:[1473,2166] pseudo_costs
#Bound 2.50s best:2168 next:[1479,2166] pseudo_costs
#14 2.74s best:2032 next:[1479,2031] no_lp fixed_bools:2/968
Solution 13, time = 2.745947 s, objective = 2032, best_bound = 1479
#Bound 2.75s best:2032 next:[1479,2030] no_lp
#Bound 2.83s best:2032 next:[1484,2030] reduced_costs
#Bound 3.23s best:2032 next:[1491,2030] pseudo_costs
#Bound 3.50s best:2032 next:[1493,2030] pseudo_costs
#Bound 3.73s best:2032 next:[1494,2030] pseudo_costs
#Bound 4.89s best:2032 next:[1498,2030] pseudo_costs
#Bound 5.36s best:2032 next:[1500,2030] pseudo_costs
#Bound 8.63s best:2032 next:[1503,2030] pseudo_costs
#Bound 8.85s best:2032 next:[1508,2030] pseudo_costs
#Bound 9.93s best:2032 next:[1514,2030] pseudo_costs
#Bound 10.18s best:2032 next:[1518,2030] pseudo_costs
#Bound 10.80s best:2032 next:[1523,2030] pseudo_costs
#Bound 11.05s best:2032 next:[1527,2030] pseudo_costs
#Bound 11.25s best:2032 next:[1531,2030] pseudo_costs
#Bound 12.14s best:2032 next:[1532,2030] pseudo_costs
......
......
......
#Bound 26.09s best:2032 next:[1647,2030] pseudo_costs
#Bound 26.60s best:2032 next:[1719,2030] pseudo_costs
#Bound 26.76s best:2032 next:[1720,2030] pseudo_costs
#Bound 26.94s best:2032 next:[1724,2030] pseudo_costs
#Done 26.94s pseudo_costs
#Done 26.96s default_lp
您应该阅读这个线程。
特别是来自stradivari96@的回调代码
from threading import Timer
from ortools.sat.python import cp_model
class ObjectiveEarlyStopping(cp_model.CpSolverSolutionCallback):
def __init__(self, timer_limit: int):
super(ObjectiveEarlyStopping, self).__init__()
self._timer_limit = timer_limit
self._timer = None
self._reset_timer()
def on_solution_callback(self):
self._reset_timer()
def _reset_timer(self):
if self._timer:
self._timer.cancel()
self._timer = Timer(self._timer_limit, self.StopSearch)
self._timer.start()
def StopSearch(self):
print(f"{self._timer_limit} seconds without improvement")
super().StopSearch()