对于一个MIP问题来说，找初始可行解是一个比较费时的过程，如果我们能够在求解开始时就为问题提供一个较好的初始解（不一定是可行的），那么可以大大减少求解器找初始可行解的计算量，加快求解速度。从我们提供的初始解开始进行问题求解，这就叫做热启动。
需要注意的是，在MIP的精确求解过程中，热启动并不保证能够缩小求解器的搜索范围，因此如果我们提供的初始解并不可行甚至离可行域相去甚远，那么并不会有好的加速效果。
下面我们用一个例子来看如何为CPLEX求解器添加热启动，并且简单对比一下热启动和冷启动时的求解速度。
例子与初始解
还是以背包问题为例，先进行初始问题的构建和求解：
# 导入包
from docplex.mp.model import Model
import pandas as pd
import numpy as np
# 创建数据
np.random.seed(0)
n_knapsack = 5
n_item = 20
def create_data() -> dict:
data = dict()
data["KnapsackRange"] = [i for i in range(n_knapsack)]
data["ItemRange"] = [j for j in range(n_item)]
data["ItemWeight"] = np.random.randint(n_knapsack, n_item, len(data["ItemRange"]))
data["KnapsackCapacity"] = np.random.randint(20, 50, len(data["KnapsackRange"]))
data["Lambda1"] = 1.0
data["Lambda2"] = 0.0
return data
data = create_data()
# 定义约束和目标函数
class MaxWeightObj(object):
def __init__(self):
pass
def add(self, model, data):
total_weight_item = model.sum(data["Var"][(i,j)] * data["ItemWeight"][j] for i in data["KnapsackRange"] for j in data["ItemRange"])
load_balance_item = model.sum(model.abs(
model.sum(data["Var"][(i,j)] * data["ItemWeight"][j] for j in data["ItemRange"]) - 30)
for i in data["KnapsackRange"])
model.maximize(data["Lambda1"] * total_weight_item + data["Lambda2"] * load_balance_item)
class CapacityConstraint(object):
def __init__(self):
pass
def add(self, model, data):
model.add_constraints((model.sum(data["Var"][(i, j)] * data["ItemWeight"][j]
for j in data["ItemRange"])<=data["KnapsackCapacity"][i]
for i in data["KnapsackRange"]), names = "CapacityConstraint")
class CountConstraint(object):
def __init__(self):
pass
def add(self, model, data):
model.add_constraints((model.sum(data["Var"][(i, j)] for j in data["ItemRange"]) >= 1
for i in data["KnapsackRange"]), names = "CountConstraint")
class UniquenessConstraint(object):
def __init__(self):
pass
def add(self, model, data):
model.add_constraints((model.sum(data["Var"][(i, j)] for i in data["KnapsackRange"]) <= 1
for j in data["ItemRange"]), names = "UniquenessConstraint")
# 建立模型
mdl = Model("Test model", cts_by_name=True)
### Change the floats to check the outcomings
data["Lambda1"] = 1.0 # Relative weight of total assigned parcels
data["Lambda2"] = 1.0 # Relative weight of load balance
data["Var"] = mdl.binary_var_dict([(i, j) for i in data["KnapsackRange"] for j in data["ItemRange"]], name='x')
constraints = [MaxWeightObj(), CapacityConstraint(), CountConstraint(), UniquenessConstraint()]
for cons in constraints:
cons.add(mdl, data)
# Output model info
mdl.print_information()
# Solve model
sol_run1 = mdl.solve(log_output = True)
求解过程如下：
Model: Test model
- number of variables: 120
- binary=100, integer=0, continuous=20
- number of constraints: 45
- linear=45
- parameters: defaults
- objective: maximize
- problem type is: MILP
Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de
CPXPARAM_Read_DataCheck 1
Tried aggregator 1 time.
MIP Presolve eliminated 10 rows and 10 columns.
Reduced MIP has 35 rows, 110 columns, and 410 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 5 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.23 ticks)
Probing time = 0.00 sec. (0.07 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 35 rows, 110 columns, and 410 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 5 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.29 ticks)
Probing time = 0.00 sec. (0.07 ticks)
Clique table members: 27.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.00 sec. (0.17 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 unbounded 113
0 2 unbounded 118
Elapsed time = 0.02 sec. (1.15 ticks, tree = 0.02 MB, solutions = 0)
* 24+ 9 164.0000 0.00%
* 34+ 13 180.0000 0.00%
* 45 25 integral 0 184.0000 193 0.00%
* 46+ 13 186.0000 0.00%
* 76 15 integral 0 200.0000 272 0.00%
* 99 15 integral 0 204.0000 353 0.00%
* 148+ 18 216.0000 0.00%
* 162 23 integral 0 218.0000 226.0000 590 3.67%
* 292 28 integral 0 222.0000 226.0000 720 1.80%
* 329 22 integral 0 226.0000 226.0000 793 0.00%
Cover cuts applied: 33
Root node processing (before b&c):
Real time = 0.02 sec. (1.13 ticks)
Parallel b&c, 16 threads:
Real time = 0.05 sec. (4.54 ticks)
Sync time (average) = 0.03 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.07 sec. (5.67 ticks)
CPU times: user 481 ms, sys: 76.6 ms, total: 557 ms
Wall time: 156 ms
为了进行对比，我们将问题稍作变换，修改一下目标函数：
# 修改目标函数中两项的相对权重，并且修改模型中的目标函数total_weight_item = mdl.sum(data["Var"][(i,j)] * data["ItemWeight"][j] for i in data["KnapsackRange"] for j in data["ItemRange"])
load_balance_item = mdl.sum(mdl.abs(
mdl.sum(data["Var"][(i,j)] * data["ItemWeight"][j] for j in data["ItemRange"]) - 30)
for i in data["KnapsackRange"])
data["Lambda1"] = 2.0
data["Lambda2"] = 3.0
mdl.set_objective("max", data["Lambda1"] * total_weight_item + data["Lambda2"] * load_balance_item)
添加初始解，进行热启动
将原问题的解作为初始解，传入修改之后的问题中，进行求解：
%%time
# 添加热启动之后，进行求解
mdl2 = mdl.clone()
mdl2.add_mip_start(sol_run1)
mdl2.solve(log_output = True, clean_before_solve=True)
求解过程如下：
Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de
CPXPARAM_Read_DataCheck 1
1 of 1 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 512.0000.
Tried aggregator 1 time.
MIP Presolve eliminated 20 rows and 20 columns.
Reduced MIP has 40 rows, 120 columns, and 520 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 10 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.28 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 40 rows, 120 columns, and 520 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 10 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.35 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Clique table members: 27.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.00 sec. (0.21 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 512.0000 0.00%
0 0 unbounded 512.0000 123
0 2 unbounded 512.0000 147
Elapsed time = 0.02 sec. (1.57 ticks, tree = 0.02 MB, solutions = 1)
* 520+ 37 513.0000 0.00%
* 572+ 18 514.0000 0.00%
* 633 20 integral 0 515.0000 7775 0.00%
* 886+ 16 519.0000 0.00%
Cover cuts applied: 11
Root node processing (before b&c):
Real time = 0.02 sec. (1.44 ticks)
Parallel b&c, 16 threads:
Real time = 0.08 sec. (16.46 ticks)
Sync time (average) = 0.04 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.10 sec. (17.90 ticks)
CPU times: user 639 ms, sys: 42.6 ms, total: 682 ms
Wall time: 143 ms
可以看到，在639ms之后，得到了新问题的解。
冷启动进行求解
我们复制一下问题，清除保存的求解过程（否则CPLEX会自动从保存的求解过程继续向下寻找最优解），然后在冷启动的情况下求解：
%%time
# 冷启动进行求解
mdl3 = mdl.clone()
mdl3.solve(log_output = True, clean_before_solve=True)
求解过程如下：
Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de
CPXPARAM_Read_DataCheck 1
Tried aggregator 1 time.
MIP Presolve eliminated 20 rows and 20 columns.
Reduced MIP has 40 rows, 120 columns, and 520 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 10 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.28 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 40 rows, 120 columns, and 520 nonzeros.
Reduced MIP has 100 binaries, 0 generals, 10 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.35 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Clique table members: 27.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 16 threads.
Root relaxation solution time = 0.00 sec. (0.21 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 unbounded 123
0 2 unbounded 147
Elapsed time = 0.04 sec. (1.50 ticks, tree = 0.02 MB, solutions = 0)
* 98 29 integral 0 416.0000 578 0.00%
* 281+ 44 442.0000 0.00%
* 372 70 integral 0 464.0000 3591 0.00%
* 604 60 integral 0 467.0000 5497 0.00%
* 609+ 52 469.0000 0.00%
* 640 34 integral 0 472.0000 7543 0.00%
* 651 33 integral 0 476.0000 7548 0.00%
* 657 32 integral 0 477.0000 7572 0.00%
* 675 34 integral 0 479.0000 7767 0.00%
* 881 41 integral 0 507.0000 8011 0.00%
* 1048+ 27 509.0000 519.0000 1.96%
* 1089+ 24 513.0000 519.0000 1.17%
* 1106 16 integral 0 518.0000 519.0000 10449 0.19%
* 1226 16 integral 0 519.0000 519.0000 10476 0.00%
Cover cuts applied: 32
Mixed integer rounding cuts applied: 1
Root node processing (before b&c):
Real time = 0.02 sec. (1.42 ticks)
Parallel b&c, 16 threads:
Real time = 0.15 sec. (20.18 ticks)
Sync time (average) = 0.08 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 0.17 sec. (21.59 ticks)
CPU times: user 1.21 s, sys: 66.4 ms, total: 1.27 s
Wall time: 232 ms
可以看到，在没有热启动的情况下，1.21s之后我们得到了解。这比使用热启动的求解要慢上不少。
网友评论