1
00:00:04,180 --> 00:00:09,549
欢迎参加本次网络讲座（本字幕根据声音翻译，发现问题请联系help@gurobi.cn)

2
00:00:07,760 --> 00:00:11,480
讲座的内容是关于数值计算问题

3
00:00:11,480 --> 00:00:17,899
Gurobi 已经有十年的发展时间

4
00:00:14,300 --> 00:00:19,550
Gurobi 团队在优化方面有超过20多年

5
00:00:19,550 --> 00:00:24,800
丰富的数值计算和优化经验

6
00:00:21,919 --> 00:00:27,469
实际上我们不断在帮助客户日常

7
00:00:24,800 --> 00:00:31,010
使用Gurobi中积累更多的经验

8
00:00:31,010 --> 00:00:37,129
客户的应用范围很广

9
00:00:34,039 --> 00:00:40,310
从会计到程序编制

10
00:00:37,129 --> 00:00:43,310
无所不包

11
00:00:40,310 --> 00:00:46,310
今天的讲座得益于这些经验

12
00:00:43,310 --> 00:00:48,170
让我们先看一下Gurobi 关于数值问题的建议

13
00:00:48,170 --> 00:00:55,339
或者说发生问题的原因

14
00:00:51,920 --> 00:00:57,530
更重要的是，如何避免

15
00:00:55,339 --> 00:01:00,530
什么是数值问题

16
00:00:57,530 --> 00:01:03,379
比较难确切定义

17
00:01:00,530 --> 00:01:05,290
每当用户发现与预期不符的结果

18
00:01:03,379 --> 00:01:08,330
或者同一个问题出现不一致的结果

19
00:01:05,290 --> 00:01:10,940
就会想到可能是数值问题

20
00:01:10,940 --> 00:01:17,570
但造成问题的原因有很多

21
00:01:13,880 --> 00:01:24,510
最常见原因是这四个，可以容易处理

22
00:01:24,050 --> 00:01:29,510
首先是四舍五入

23
00:01:26,270 --> 00:01:36,020
然后是理论上的数值和计算机能够理解并且表征的数值之间的巨大差异

24
00:01:38,780 --> 00:01:46,280
这个差异反映出我们容易忘记这些数值都有局限性

25
00:01:46,280 --> 00:01:51,770
而这些局限性带来了精度预期的差异

26
00:01:51,770 --> 00:01:57,590
最后我们讨论不恰当的条件设置

27
00:01:53,720 --> 00:02:01,600
首先我们先理解这些问题的源头

28
00:02:02,930 --> 00:02:07,970
做容易发生的是系数的四舍五入

29
00:02:05,510 --> 00:02:11,660
可以用一个例子说明，这个问题可以很严重

30
00:02:11,660 --> 00:02:16,369
这是一个简单的例子

31
00:02:13,909 --> 00:02:17,480
我假设你输入了二个约束条件

32
00:02:17,480 --> 00:02:21,560
看看这二个约束条件

33
00:02:20,030 --> 00:02:24,019
你也许会说他们看一起来一样

34
00:02:24,019 --> 00:02:30,099
数值非常接近, 1/3 和 0.333 一样

35
00:02:33,789 --> 00:02:40,429
优化器解读你提供的数值是真实的数值

36
00:02:43,250 --> 00:02:46,849
通过简单的代数替换

37
00:02:45,230 --> 00:02:49,550
你会发现这二个约束条件意味着

38
00:02:49,550 --> 00:02:57,110
x=0, y=1 是唯一的结果

39
00:02:57,110 --> 00:03:02,719
你提供的系数是优化器解读的确切数值

40
00:03:02,719 --> 00:03:08,569
换一种更高的近似精度

41
00:03:08,569 --> 00:03:14,090
例如用这二个约束条件

42
00:03:11,899 --> 00:03:16,519
描述了不同的故事

43
00:03:14,090 --> 00:03:19,399
简单的代数替换产生这样的表达式

44
00:03:21,890 --> 00:03:29,029
这样的表达式非常非常非常接近1

45
00:03:33,439 --> 00:03:38,300
优化器认为等于1，因此二个约束条件冗余，删除其中一个

46
00:03:40,849 --> 00:03:47,149
只要满足这个条件都是可行的

47
00:03:47,149 --> 00:03:52,279
如果你采用之前的精度，那告诉优化器只能选择

48
00:03:52,279 --> 00:03:58,069
x=1,y=0

49
00:03:58,069 --> 00:04:02,989
但往往这不是你希望的结果

50
00:04:00,289 --> 00:04:05,149
因此寻找问题首先考虑模型中的数值是不是全精度的

51
00:04:08,659 --> 00:04:15,200
也就是16位小数

52
00:04:13,099 --> 00:04:17,809
这是我采用的标准精度

53
00:04:15,200 --> 00:04:20,809
一个好问题可以问自己

54
00:04:20,809 --> 00:04:26,839
为什么 2*1E-16这个数值如此特殊

55
00:04:26,839 --> 00:04:32,019
以致于Gurobi 会忽略它

56
00:04:29,420 --> 00:04:34,219
这就说明这些浮点数据不是真正的实数

57
00:04:34,219 --> 00:04:39,979
或者不是计算机处理的方式

58
00:04:39,979 --> 00:04:43,219
有一个简单的验证方法

59
00:04:43,219 --> 00:04:47,929
打开 Python 环境，输入这个表达式

60
00:04:44,869 --> 00:04:51,380
会得到一个 True的结果，但看起来

61
00:04:51,380 --> 00:04:54,919
不应该为 True

62
00:04:53,119 --> 00:04:58,249
但这就是计算机理解的

63
00:04:54,919 --> 00:05:01,309
也许你认为这可以是由于数值太小

64
00:05:01,309 --> 00:05:07,160
近似为1不会有太大错误

65
00:05:03,980 --> 00:05:09,049
如果数值很大的话就不会出现这个问题

66
00:05:09,049 --> 00:05:14,029
但并非如此

67
00:05:12,049 --> 00:05:17,779
做另外一个实验将 1E16 加 1 与 1E16 对比

68
00:05:17,779 --> 00:05:24,889
Python 又一次说这是相等的

69
00:05:21,799 --> 00:05:28,309
但奇怪这些都不是小数值

70
00:05:24,889 --> 00:05:31,910
简而言之

71
00:05:28,309 --> 00:05:34,790
这些和Python 无关

72
00:05:31,910 --> 00:05:38,589
在 Excel,C,R,Java 等任何编程语言中也如此

73
00:05:38,589 --> 00:05:45,019
只要使用标准的浮点表达式，结果都为True

74
00:05:47,569 --> 00:06:01,589
这似乎与我们在学校中学习的基本代数规则相悖

75
00:06:02,449 --> 00:06:08,239
再例如代数中的结合律规则

76
00:06:05,269 --> 00:06:10,699
1 加上这个很小的数值之后再加上这个很小的数值

77
00:06:08,239 --> 00:06:12,769
并不等同于这二个很小的数值相加之后再加1

78
00:06:12,769 --> 00:06:18,649
人们的理解和计算机硬件存储数值的方式大相径庭

79
00:06:14,600 --> 00:06:21,529
造成期望的结果和实际结果不一致

80
00:06:23,540 --> 00:06:31,669
我相信有些变通的方法

81
00:06:27,230 --> 00:06:35,389
例如 GNU-MP 和其他一些工具

82
00:06:39,319 --> 00:06:44,389
但是这些工具依赖软件实现，速度会慢

83
00:06:46,800 --> 00:06:53,040
你也许知道局限性的来源

84
00:06:53,040 --> 00:06:58,710
在 Python 中，你输入 import system

85
00:06:56,430 --> 00:07:01,230
然后打印出浮点信息

86
00:06:58,710 --> 00:07:05,820
可以看到这里有个数值 epsilon， 非常小的数值

87
00:07:08,969 --> 00:07:14,300
这个数值是可以加到 1 数值上，但仍然和 1 可以区分开的最小数值

88
00:07:16,559 --> 00:07:22,920
比这个数值再小就无法存在计算机里，我们无法使用

89
00:07:22,920 --> 00:07:29,219
这就是我说的避开不了的地方

90
00:07:26,610 --> 00:07:30,870
也就是我说的实数不实的地方，至少在计算机里是这样

91
00:07:35,339 --> 00:07:41,070
因此我们需要比较谨慎

92
00:07:37,800 --> 00:07:43,830
在计算机里进行数学计算

93
00:07:41,070 --> 00:07:46,830
稍微解释一下，这意味着

94
00:07:43,830 --> 00:07:55,510
大多数系统提供了硬件实现数值近似的方法

95
00:07:55,920 --> 00:08:02,100
这些硬件是取得好结果的关键

96
00:08:02,100 --> 00:08:06,390
这些硬件处理可以比其他软件方法快10，100甚至1000倍

97
00:08:10,920 --> 00:08:17,700
所以如果你在意性能

98
00:08:14,219 --> 00:08:20,309
应该在限度内使用这些数值

99
00:08:20,309 --> 00:08:26,519
这也是 Gurobi 采用的64位双精度数值原因

100
00:08:23,999 --> 00:08:30,029
效果还不错

101
00:08:30,029 --> 00:08:34,980
我可以演示给你看，如果合理使用

102
00:08:34,980 --> 00:08:43,079
99.999% 的情况下结果有效

103
00:08:43,079 --> 00:08:49,949
还有最后一点，正因为这些数据不是确切数值

104
00:08:49,949 --> 00:08:55,860
将他们加在一起不是一个精确的运算

105
00:08:55,860 --> 00:09:00,240
每当进行数值比较时

106
00:08:58,440 --> 00:09:07,970
利用等式比较不一定准确，需要考虑到可能出现的精度误差

107
00:09:07,680 --> 00:09:15,330
一个可行的方法是利用客户数值范围上的容差量 Tolerance

108
00:09:15,210 --> 00:09:21,030
再强调一下，之前说过，Gurobi 认为

109
00:09:21,030 --> 00:09:27,060
所有客户提供的数值都是准确的数值

110
00:09:27,060 --> 00:09:33,390
如果有用户在模型中输入了1 加 1E-7 再乘以 x 小于或等于 1

111
00:09:35,670 --> 00:09:42,540
x 是一个 0-1 变量

112
00:09:40,980 --> 00:09:45,210
Presolve 也许会检测到这点，因为这个是不可见的

113
00:09:42,540 --> 00:09:48,950
然后决定这意味着 x 只能等于0

114
00:09:45,210 --> 00:09:51,870
从传给优化器的数值来看这个决定不错

115
00:09:51,870 --> 00:10:00,620
我需要强调的是这种检测只是可能会发生，并不是一定发生

116
00:10:00,990 --> 00:10:05,940
原因是在 Presolve 和 切平面时

117
00:10:03,060 --> 00:10:08,460
我们需要限制花费在这种检测上的时间

118
00:10:08,460 --> 00:10:18,980
不是任何时候都会做全部检测

119
00:10:21,680 --> 00:10:30,030
但是当找到一个可行解，需要检测这个可行解是否真正可行

120
00:10:30,030 --> 00:10:35,550
之前是说过，不能在约束条件上用等式检测

121
00:10:35,550 --> 00:10:40,740
需要引入容差量 Tolerance 的概念

122
00:10:40,740 --> 00:10:45,660
每当有一个可行解

123
00:10:43,320 --> 00:10:48,120
至少需要检测三个方面

124
00:10:48,120 --> 00:10:53,220
第一个检测是否是整数

125
00:10:50,850 --> 00:10:59,880
我们定义了 IntInfTol

126
00:10:59,270 --> 00:11:07,830
用于检测是否满足整数条件

127
00:11:07,830 --> 00:11:11,740
同样，原始单纯形可行性检测引入了容差量 FeasibilityTol

128
00:11:11,740 --> 00:11:17,650
每当检测不等式或者等式是否成立时

129
00:11:21,090 --> 00:11:28,480
我们都留有一定空间用于判断

130
00:11:28,480 --> 00:11:34,300
同样，用于检测对偶可行时引入了 OptimalityTol

131
00:11:36,610 --> 00:11:43,930
这三个参数用户是可以调整的

132
00:11:43,930 --> 00:11:50,800
但这些调整比较精细，需要谨慎说明

133
00:11:50,800 --> 00:11:59,420
首先这些容差量都是绝对数值，不依赖输入的系数而改变

134
00:12:00,220 --> 00:12:05,829
如果你改变了放大或缩小了约束和变量的系数倍数

135
00:12:08,259 --> 00:12:12,639
你需要小心，这些容差量的含义也发生变化

136
00:12:10,780 --> 00:12:16,319
同时也意味着一个可能满足之前容差量的可行解

137
00:12:12,639 --> 00:12:38,150
可能会被 Presolve 或者切平面认为是不可行解而切掉

138
00:12:39,730 --> 00:12:45,910
为什么这样会带来麻烦

139
00:12:43,210 --> 00:12:49,540
因为这意味着对于数值比较敏感和具备挑战性的模型

140
00:12:45,910 --> 00:12:52,990
最优解可能会随着算法的选择而变化

141
00:12:57,940 --> 00:13:01,780
这意味着对于很难获得准确解的问题

142
00:13:01,780 --> 00:13:06,040
存在一个灰色地带

143
00:13:06,040 --> 00:13:13,800
在灰色地带里有时会被认为是可行解，有时则不可行

144
00:13:13,930 --> 00:13:24,360
也就是说那些严格可行的仍然可行，那些在容差量之外的则判为不可行

145
00:13:25,000 --> 00:13:32,350
每当问题存在一个较大的灰色地带时

146
00:13:32,350 --> 00:13:38,650
往往容易出现数值问题

147
00:13:34,960 --> 00:13:41,110
但到底这种情形会有多槽糕

148
00:13:41,110 --> 00:13:46,030
目前为止听我说得似乎很糟糕

149
00:13:43,450 --> 00:13:48,340
但使用优化器的人并不经常遇到这个问题

150
00:13:48,340 --> 00:13:53,260
怎么会这样？应该有什么原因

151
00:13:53,260 --> 00:13:59,740
的确是

152
00:13:55,170 --> 00:14:02,079
首先Gurobi 默认的原始和对偶容差量是 1e-6

153
00:13:59,740 --> 00:14:04,930
整数是1e-5

154
00:14:04,930 --> 00:14:12,510
假设你定义的模型右端数值在 1e4 和 1e3 级别

155
00:14:12,940 --> 00:14:22,680
意味着，有时可行有时不可行的灰色地带会很小

156
00:14:23,740 --> 00:14:29,139
大概只有 1e-9 或者说十亿分之一

157
00:14:26,350 --> 00:14:31,990
这个数值很小，对于大部分问题无足轻重

158
00:14:32,800 --> 00:14:38,500
灰色地带不起什么作用

159
00:14:35,259 --> 00:14:40,420
这就是我说的scaling（系数缩放）很关键

160
00:14:38,500 --> 00:14:49,200
因为你来决定约束和变量的系数和变化范围

161
00:14:49,240 --> 00:14:55,960
这里的容差量是绝对数值，而不是相对数值

162
00:14:55,960 --> 00:15:02,620
如果你的约束变化范围很窄

163
00:14:58,570 --> 00:15:05,530
优化器可能认为是等式

164
00:15:05,530 --> 00:15:10,590
例如解在 1e-10 和 1e-9 之间移动

165
00:15:10,590 --> 00:15:16,750
优化器可能就无法检测到

166
00:15:16,750 --> 00:15:29,610
所以约束变化范围要明显一些，除非他们的确就是等式

167
00:15:30,430 --> 00:15:38,080
对于变量而言，同样适用

168
00:15:40,770 --> 00:15:45,910
变量范围不能太小

169
00:15:43,600 --> 00:15:48,340
这些范围会限制原始单纯形约束的边界

170
00:15:51,190 --> 00:15:56,680
同样变化范围也不要太大

171
00:15:53,800 --> 00:15:58,780
特别对于整数变量

172
00:15:58,780 --> 00:16:03,610
例如范围是100万

173
00:16:01,150 --> 00:16:05,320
最好处理为连续变量

174
00:16:05,320 --> 00:16:10,240
移动一个单位，对于百万级别而言效果微不足道

175
00:16:13,720 --> 00:16:24,460
但优化需要付出的代价却是很高

176
00:16:25,530 --> 00:16:31,120
对于目标函数而言，这些规则也适用

177
00:16:31,120 --> 00:16:37,240
当你检测可行解的时候

178
00:16:35,170 --> 00:16:40,030
也在检测对偶条件

179
00:16:37,240 --> 00:16:44,500
确保线性最优性

180
00:16:44,500 --> 00:16:50,110
我的建议是将问题处理成

181
00:16:47,950 --> 00:16:53,080
最优目标取值范围在 -1e4 和 1e4 之间

182
00:16:53,080 --> 00:16:58,540
否则在对偶可行性上需要增加很多计算负担

183
00:16:58,540 --> 00:17:05,020
例如假设我们在处理百亿美金级别的问题

184
00:17:01,150 --> 00:17:07,389
一个好的处理方法是改变目标函数中单位量级

185
00:17:07,389 --> 00:17:13,030
比如以千或者万为单位

186
00:17:09,610 --> 00:17:15,910
而不是元或者分为单位

187
00:17:15,910 --> 00:17:21,430
否则目标函数将失控

188
00:17:17,889 --> 00:17:23,230
造成优化困难

189
00:17:21,430 --> 00:17:25,869
和之前所述约束变动范围不要太小的原因一样

190
00:17:25,869 --> 00:17:31,780
尽量避免有意义的目标函数取值太小

191
00:17:34,630 --> 00:17:39,550
我建议要么取值大于1或者小于-1

192
00:17:43,960 --> 00:17:50,410
避免太接近0

193
00:17:46,870 --> 00:17:53,410
这样的话在对偶部分容易处理一些

194
00:17:50,410 --> 00:17:59,060
除非你的问题是约束满足问题，所有目标函数系数都为0

195
00:17:59,260 --> 00:18:05,440
这样的话也不会牺牲性能

196
00:18:05,440 --> 00:18:11,170
以上这些规则并不难实现

197
00:18:07,870 --> 00:18:13,570
完全取决于你在行、列和目标函数中

198
00:18:11,170 --> 00:18:21,540
如何调整系数缩放和单位

199
00:18:22,720 --> 00:18:26,020
之前说过，Gurobi不会自动做这些工作

200
00:18:25,660 --> 00:18:31,080
用户需要自己定义合适的范围

201
00:18:32,680 --> 00:18:39,450
那么如何定义紧凑合适的约束和变量范围呢

202
00:18:39,450 --> 00:18:46,750
首先需要利用模型中没有包含的信息

203
00:18:41,920 --> 00:18:50,290
让约束和变量更紧凑

204
00:18:53,140 --> 00:18:59,590
例如需要优化一个快递问题

205
00:18:59,590 --> 00:19:07,030
理论上车辆的数量可以取任何数值

206
00:19:07,030 --> 00:19:11,710
但如果我了解问题背景，知道只有三个地点可以存放车辆

207
00:19:11,710 --> 00:19:15,610
每个地点不能容纳超过100辆车

208
00:19:15,610 --> 00:19:20,680
就可以将这个信息输入给优化器

209
00:19:18,730 --> 00:19:24,190
优化器就可以很好的利用这个信息缩小搜索

210
00:19:20,680 --> 00:19:26,980
让优化快起来

211
00:19:26,980 --> 00:19:32,320
如果没有这个信息

212
00:19:29,860 --> 00:19:42,410
优化器不得不考虑各种可能情况，而有些情况现实中根本不会出现

213
00:19:43,470 --> 00:19:49,210
因此首要事情是获得额外的信息

214
00:19:49,210 --> 00:19:55,020
缩小变量的变化范围

215
00:19:52,090 --> 00:19:58,620
然后设置合适的量纲

216
00:19:55,020 --> 00:20:00,840
例如从以吨为单位到以2000吨为单位

217
00:19:58,620 --> 00:20:03,800
以元为单位到以千元为单位

218
00:20:03,800 --> 00:20:09,660
合适的量纲可以让约束和变量具有合适的变动范围

219
00:20:09,660 --> 00:20:16,410
希望不会超过 1E4

220
00:20:12,930 --> 00:20:20,850
最后还有一种情形，在目标函数中容易设置很大或者很小的系数

221
00:20:23,700 --> 00:20:28,110
就是当用户处理多个层级目标时

222
00:20:28,110 --> 00:20:32,810
将这些目标混在一起

223
00:20:32,810 --> 00:20:37,290
最重要的目标给予非常大的系数

224
00:20:35,490 --> 00:20:38,940
次重要的目标给予小的系数

225
00:20:40,500 --> 00:20:45,120
会造成目标函数中差异很大的二个部分

226
00:20:45,120 --> 00:20:50,010
现在 Gurobi 直接支持多目标优化

227
00:20:50,010 --> 00:20:56,130
每个目标函数可以设置合理的数值

228
00:20:52,860 --> 00:20:59,460
合理的系数

229
00:20:56,130 --> 00:21:04,680
而且容易处理

230
00:21:04,680 --> 00:21:12,330
我再强调一下为什么缩放很重要

231
00:21:09,090 --> 00:21:14,700
可以快速做一个试验

232
00:21:14,700 --> 00:21:19,620
这是一个模型，我将系数都缩放一个随机比例

233
00:21:19,620 --> 00:21:24,870
理论上优化值不会变化

234
00:21:24,870 --> 00:21:31,920
这里是修改目标函数的系数

235
00:21:29,040 --> 00:21:36,980
这是缩放变量的上下界，如果是有限的话

236
00:21:37,460 --> 00:21:42,270
运行这个代码，这部分是一个普通模型程序

237
00:21:42,270 --> 00:21:50,530
这里是说明缩放比例是小于1的随机数

238
00:21:51,900 --> 00:21:57,060
启动优化，会马上看到一个警告

239
00:21:57,060 --> 00:22:08,840
提示最小系数和最大系数的差异过大

240
00:22:08,920 --> 00:22:16,750
但Gurobi 可以很好求解

241
00:22:13,420 --> 00:22:20,380
找到最优解，经过了1000次左右迭代

242
00:22:16,750 --> 00:22:23,320
最优值是4.49等等这个数值

243
00:22:23,320 --> 00:22:31,170
现在我放大系数到1000

244
00:22:31,170 --> 00:22:37,870
矩阵系数差放大到 1e18 次方

245
00:22:37,870 --> 00:22:44,670
仍然会看到警告

246
00:22:40,960 --> 00:22:49,060
我们仍然可以得到同样最优解

247
00:22:44,670 --> 00:22:52,140
但是，关键是，需要迭代的次数增加了

248
00:22:52,140 --> 00:22:59,530
如果我放大更多，比如说100万

249
00:23:01,690 --> 00:23:07,840
矩阵系数波动范围更疯狂

250
00:23:04,090 --> 00:23:11,979
Gurobi 仍然可以获得最优值，但时间更长

251
00:23:11,979 --> 00:23:17,190
同时，会出现更多警告信息

252
00:23:13,930 --> 00:23:22,640
提示说尽管很努力处理非缩放时的约束违反

253
00:23:23,650 --> 00:23:31,229
但在优化后无法找到更小的原始和对偶违反

254
00:23:32,890 --> 00:23:37,810
对于这个例子这属于极限情况

255
00:23:35,590 --> 00:23:39,880
最优目标值仍然正确，只是迭代次数又增加

256
00:23:39,880 --> 00:23:45,340
无法找到一个让约束违反更小的结果

257
00:23:45,340 --> 00:23:54,700
如果我们再走一步，缩放范围到1亿

258
00:23:55,570 --> 00:24:00,670
这时候问题彻底崩溃

259
00:23:57,400 --> 00:24:03,940
Gurobi 无法求解，只能显示不可行

260
00:24:05,280 --> 00:24:12,030
Gurobi 信任模型中用户提供的数据

261
00:24:09,359 --> 00:24:14,880
理论上缩放不会影响最优结果

262
00:24:16,650 --> 00:24:22,290
但是数值精度的存储方式决定了缩放数值改变了这些数值的含义

263
00:24:23,849 --> 00:24:29,820
面临着无法获得可行解的风险

264
00:24:29,820 --> 00:24:35,190
同时请记住放大范围会让问题变得更难求解

265
00:24:37,500 --> 00:24:44,240
第一次虽然Gurobi 可以求解，但花费时间更长了

266
00:24:45,270 --> 00:24:52,219
所以再强调一下，合适地缩放模型

267
00:24:48,510 --> 00:24:56,130
可以带来更快的优化速度

268
00:24:52,219 --> 00:24:59,099
用户可以做的事情包括

269
00:24:59,099 --> 00:25:04,109
对行和列做合适的缩放，设定合适的系数

270
00:25:04,109 --> 00:25:07,590
我举例说明

271
00:25:07,590 --> 00:25:16,170
请看这个问题

272
00:25:16,859 --> 00:25:24,450
我可以用 1e4x' 替换掉 x

273
00:25:24,450 --> 00:25:31,080
替换后的第一个约束条件如下

274
00:25:27,240 --> 00:25:41,710
同样，可以简化第二个约束条件

275
00:25:42,500 --> 00:25:54,740
这样可以从系数矩阵指数差10个级别降到4个级别

276
00:25:56,000 --> 00:26:02,190
同时精度和容许值是绝对数值

277
00:26:02,190 --> 00:26:13,290
所以即便问题一样，求解缩放后的问题更容易一些

278
00:26:14,969 --> 00:26:19,060
因为缩放前的指数差更高

279
00:26:18,209 --> 00:26:22,750
但我要求的容差量只有1e-6

280
00:26:22,750 --> 00:26:27,040
而对于这个约束而言

281
00:26:25,060 --> 00:26:29,440
1e-6 容差量就容易让优化器找到 x'和 z

282
00:26:29,440 --> 00:26:36,310
不要骗自己。一个普适的原则就是

283
00:26:33,190 --> 00:26:40,830
缩小行和列系数的变化范围

284
00:26:41,770 --> 00:26:46,120
下次遇到这样的问题，很容易和自己说

285
00:26:43,810 --> 00:26:48,880
我可以耍些小技巧，消除掉那些巨大数值

286
00:26:48,880 --> 00:26:54,730
与其有 1e6 这样的数值，而我只有1和10

287
00:26:51,670 --> 00:26:57,490
这样公式看起来更不错，不是吗

288
00:26:57,490 --> 00:27:02,710
但是，你没有改变任何东西

289
00:27:00,220 --> 00:27:05,320
同样不可行解的 epsilon 仍然存在于模型中

290
00:27:05,320 --> 00:27:10,510
Presolve 会检测到这点，改写为原来的样子

291
00:27:08,050 --> 00:27:12,700
所以这个小手段并没有改变问题

292
00:27:14,950 --> 00:27:25,270
你可以采用的方式是

293
00:27:18,750 --> 00:27:28,150
用 Y' 替换 Y

294
00:27:25,270 --> 00:27:30,370
这是他们之间的表达式

295
00:27:28,150 --> 00:27:36,430
系数矩阵的指数差降到3，但变量范围变大

296
00:27:37,750 --> 00:27:46,180
这样好处是如果 Y'有epsilon 误差

297
00:27:46,180 --> 00:27:53,560
则 X 的可能误差会很小，只有 1e-3，这很好

298
00:27:53,560 --> 00:27:58,420
这会改善数值状况

299
00:27:58,420 --> 00:28:02,830
而前面的简单替代对问题没有丝毫帮助

300
00:28:02,830 --> 00:28:08,710
关于大M 约束

301
00:28:06,040 --> 00:28:10,600
原则上如果你合适缩放约束和变量

302
00:28:08,710 --> 00:28:12,880
就不应该有大M，因为变量限制在1e4范围内

303
00:28:14,260 --> 00:28:20,320
计算处理一切良好

304
00:28:16,540 --> 00:28:22,870
但出于某种原因避免不了

305
00:28:20,320 --> 00:28:26,710
例如这里大的系数

306
00:28:22,870 --> 00:28:31,820
而你无法重新缩放 x 的含义

307
00:28:32,410 --> 00:28:38,680
你可以采取提升数值准确度的方法是

308
00:28:35,500 --> 00:28:41,770
定义这些约束为 SOS 约束或者广义指标约束

309
00:28:41,770 --> 00:28:46,950
这些 Gurobi 7.5 都支持

310
00:28:46,950 --> 00:28:53,160
但是，虽然你会得到更可靠的结果

311
00:28:50,140 --> 00:28:56,410
事实上这里意味着如果Y是0，则X也为0

312
00:28:53,160 --> 00:29:00,340
这个条件也会满足

313
00:28:56,410 --> 00:29:02,620
代价是需要花费额外的计算时间

314
00:29:02,620 --> 00:29:12,950
所以保证数值稳定性的代价，是额外的计算时间

315
00:29:13,330 --> 00:29:19,270
让我们做一个快速总结

316
00:29:16,210 --> 00:29:24,930
变量取值一般来说不要超出 -1e4 到 1e4 范围

317
00:29:25,240 --> 00:29:30,070
同样适用于约束条件

318
00:29:28,240 --> 00:29:32,530
意味着约束条件在这个范围内移动

319
00:29:30,070 --> 00:29:35,170
也适用于目标值，不应该超出这个范围太多

320
00:29:36,969 --> 00:29:44,170
你也不应该比较二个绝对值差异极大数值

321
00:29:46,719 --> 00:29:53,800
例如比较1e-10 和 1

322
00:29:49,300 --> 00:29:56,290
会带来计算上的麻烦

323
00:29:58,660 --> 00:30:05,469
尽量避免这些

324
00:30:02,859 --> 00:30:07,570
如果你按此修改模型

325
00:30:05,469 --> 00:30:09,700
你也许会惊喜发现性能有了提升

326
00:30:11,890 --> 00:30:19,030
这是因为Gurobi每当发现数值问题

327
00:30:15,640 --> 00:30:22,120
会努力解决，或者用更高的精度

328
00:30:19,030 --> 00:30:25,750
或者内部调整算法

329
00:30:22,120 --> 00:30:31,170
例如关闭一些原来让求解更快的代码而解决数值问题

330
00:30:33,700 --> 00:30:40,240
所以选择合适的数值范围是改善性能的关键

331
00:30:42,729 --> 00:30:46,290
一定要试试

332
00:30:46,290 --> 00:30:53,829
接下来，如果你已经有了模型，怎么检查是否有数值问题

333
00:30:51,189 --> 00:30:57,010
这是一个重要的问题

334
00:30:57,010 --> 00:31:04,859
第一件事情是将模型和参数分开

335
00:31:05,290 --> 00:31:11,260
设置这个参数 GURO_PAR_DUMP 等于1

336
00:31:07,630 --> 00:31:13,240
在调用optimize()函数前设置

337
00:31:11,260 --> 00:31:18,910
优化器会产生二个文件 REW 和 PRM

338
00:31:19,660 --> 00:31:25,449
REW 是隐去所有变量和约束名称的模型文件

339
00:31:22,809 --> 00:31:28,359
PRM是非默认取值的参数文件

340
00:31:25,449 --> 00:31:31,630
这些参数很重要

341
00:31:33,429 --> 00:31:41,290
用于指导优化器管理和选择何种算法，如何去优化

342
00:31:42,010 --> 00:31:46,270
这二个文件可以让优化结果重现

343
00:31:46,270 --> 00:31:52,390
获得这二个文件之后

344
00:31:52,390 --> 00:31:58,599
可以在 Python 交互界面读入模型

345
00:31:55,959 --> 00:32:00,520
输入 printStats 命令打印模型统计数据

346
00:31:58,599 --> 00:32:03,640
会显示矩阵和目标系数范围等信息

347
00:32:05,949 --> 00:32:10,990
你可以判断这些范围是否合理，是否有异常情况

348
00:32:10,990 --> 00:32:19,150
如果看起来合理

349
00:32:16,079 --> 00:32:21,699
可以读入PRM 参数文件

350
00:32:19,150 --> 00:32:23,349
然后启动优化

351
00:32:23,349 --> 00:32:31,030
这时候观察输出日志

352
00:32:26,020 --> 00:32:32,910
Gurobi 输出日志提供了很多有用的信息

353
00:32:32,910 --> 00:32:38,140
很多情况下提示了很多警告信息

354
00:32:38,140 --> 00:32:43,300
常见的警告信息有这些

355
00:32:40,270 --> 00:32:46,540
矩阵系数或者目标系数看起来不太对

356
00:32:46,540 --> 00:32:52,630
或者你看到 Markowitz Tolerance tightened 到某个数值

357
00:32:49,780 --> 00:32:57,120
这是一个明确信号，Gurobi 在努力寻找稳定解

358
00:32:58,800 --> 00:33:02,110
这也提示模型的确有数值问题

359
00:32:59,920 --> 00:33:04,600
如果看到 switch to quad precision

360
00:33:04,600 --> 00:33:09,700
意味着Gurobi不但通过调整算法无法求解

361
00:33:07,360 --> 00:33:13,060
还不得不扩展浮点精度

362
00:33:13,060 --> 00:33:16,380
我稍后还会讲这个

363
00:33:14,950 --> 00:33:19,180
当然如果你看到 Numeric error

364
00:33:19,180 --> 00:33:24,250
或者 numerical trouble encountered

365
00:33:21,130 --> 00:33:27,070
或者 restart crossover 这意味着

366
00:33:24,250 --> 00:33:30,960
内点算法(障碍算法）遇到了困难

367
00:33:31,030 --> 00:33:39,840
还有其他这些警告信息（请看PPT)

368
00:33:40,000 --> 00:33:48,270
意味Gurobi无法满足容差设置

369
00:33:49,060 --> 00:33:58,820
这些警告信息都是强烈信号，你应该看看模型哪里有问题

370
00:33:59,670 --> 00:34:05,710
同时，你可以输入 printquality() 检测解的质量

371
00:34:02,470 --> 00:34:08,860
检查边界违反的最糟糕情况

372
00:34:05,710 --> 00:34:10,360
最糟糕的约束违反情况

373
00:34:08,860 --> 00:34:11,950
最糟糕的整数条件违反情况

374
00:34:11,950 --> 00:34:17,710
对于这个例子

375
00:34:13,900 --> 00:34:20,230
边界情况不错，只有 1e-8

376
00:34:17,710 --> 00:34:24,960
但是约束违反达到了 1e-4 接近 1e-3

377
00:34:25,150 --> 00:34:30,190
这很糟糕

378
00:34:27,940 --> 00:34:32,500
整数条件还不错

379
00:34:30,190 --> 00:34:36,520
这说明得到的解不是特别的贴合

380
00:34:32,500 --> 00:34:40,830
Gurobi 在努力找到一个解

381
00:34:41,020 --> 00:34:46,210
用于满足容差数值

382
00:34:43,890 --> 00:34:48,820
你也可以查看条件值 KappaExact

383
00:34:46,210 --> 00:34:51,340
我稍后会讲

384
00:34:48,820 --> 00:35:00,730
条件值如果很大，也是一个优化器遇到数值问题的信号

385
00:35:01,030 --> 00:35:08,590
其他一些症状包括

386
00:35:05,650 --> 00:35:10,960
修改参数，导致解发生变化，优化值发生变化

387
00:35:08,590 --> 00:35:13,610
问题从不可行变成可行

388
00:35:13,610 --> 00:35:19,940
这些都是强烈的信号说明你的模型有数值问题

389
00:35:19,940 --> 00:35:28,280
绝大部分问题的性质都是数值方面的

390
00:35:24,280 --> 00:35:34,010
意味着一般不是 Gurobi的 bugs

391
00:35:35,780 --> 00:35:42,740
而是模型中的数值问题

392
00:35:39,170 --> 00:35:45,470
可以通过一个小实验看到

393
00:35:42,740 --> 00:35:48,080
就是缩小容差值的范围

394
00:35:45,470 --> 00:35:50,030
例如从 1e-6 缩小为 1e-8

395
00:35:50,030 --> 00:35:55,970
优化器可以稳定求解

396
00:35:55,970 --> 00:36:02,000
这是一个强烈信号说明你的模型在缩放系数方面有欠缺

397
00:36:02,000 --> 00:36:08,600
虽然减少容差值可以增强求解的稳定性

398
00:36:05,480 --> 00:36:13,480
但代价是需要花费额外的数值计算时间

399
00:36:14,780 --> 00:36:21,490
这点不要忘了

400
00:36:16,790 --> 00:36:24,350
如果你已经改善了各种缩放比例

401
00:36:21,490 --> 00:36:26,690
模型看起来不错

402
00:36:24,350 --> 00:36:28,940
仍然出现很奇怪的问题

403
00:36:26,690 --> 00:36:33,950
可以联系我们

404
00:36:28,940 --> 00:36:35,810
以上是关于如何检测和评估模型数值问题

405
00:36:35,810 --> 00:36:40,850
如果发现数值问题，你可以做些什么

406
00:36:40,850 --> 00:36:45,590
Gurobi 也有一些参数可以帮助这些问题

407
00:36:43,400 --> 00:36:48,920
但不是解决这些问题，而是变通化解

408
00:36:48,920 --> 00:36:56,650
付出的代价就是额外的优化时间

409
00:36:57,470 --> 00:37:04,580
首先说一下 Presolve(预优化)

410
00:37:00,410 --> 00:37:07,490
Presolve可能会带来负面影响

411
00:37:04,580 --> 00:37:11,660
检测的方法是导入Presolve 之后的模型

412
00:37:07,490 --> 00:37:14,930
然后打印出模型统计参数

413
00:37:14,930 --> 00:37:21,380
如果统计参数现实系数看起来很奇怪

414
00:37:18,530 --> 00:37:24,470
那么Presolve作用是负面的

415
00:37:21,380 --> 00:37:26,180
这种情况不经常发生，但有时会出现

416
00:37:26,180 --> 00:37:30,310
如果出现这种情况

417
00:37:27,820 --> 00:37:32,410
可以关闭掉 Presolve

418
00:37:32,410 --> 00:37:36,730
或者将 Aggregate 设置为0

419
00:37:34,630 --> 00:37:38,800
Aggregration(聚合)就是我们之前提到的那个自欺欺人的例子

420
00:37:36,730 --> 00:37:43,110
通过多个约束条件，隐藏过大的系数

421
00:37:43,660 --> 00:37:49,120
聚合的效果就是将这些多个约束整合在一起

422
00:37:46,200 --> 00:37:52,540
改写为整合后的系数

423
00:37:52,540 --> 00:37:55,660
你可以关闭这个参数

424
00:37:54,700 --> 00:37:58,390
但是你需要记住，关闭参数没有消除模型本质上的过大系数

425
00:37:58,390 --> 00:38:02,380
仍需谨慎

426
00:38:02,380 --> 00:38:08,290
或者将 AggFill 关闭

427
00:38:08,290 --> 00:38:13,680
Gurobi 有时会改写约束

428
00:38:11,080 --> 00:38:17,560
也许会引入一些不合适的系数

429
00:38:17,560 --> 00:38:22,480
如果是这样的话，关闭这个参数

430
00:38:20,320 --> 00:38:26,080
看看是否有帮助

431
00:38:22,480 --> 00:38:28,840
同时，考虑采用合适的算法

432
00:38:26,080 --> 00:38:31,420
通常来说内点法（障碍法）速度最快，但不绝对

433
00:38:31,420 --> 00:38:35,380
但它对数值问题比较敏感

434
00:38:33,160 --> 00:38:38,050
所以你可以尝试原始、对偶和内点各种方法

435
00:38:35,380 --> 00:38:41,170
看看是否有帮助，可以得到稳定一些的结果

436
00:38:38,050 --> 00:38:48,550
可以采用这些参数选择根节点的算法

437
00:38:49,930 --> 00:38:56,600
同时你也可以让算法对数值问题不太敏感

438
00:38:57,420 --> 00:39:04,930
最简单的方法是采用参数 NumericFocus

439
00:39:02,260 --> 00:39:07,390
默认值是-1，意味着Gurobi 自动内部处理

440
00:39:07,390 --> 00:39:12,040
你可以设置为0，全部关闭

441
00:39:14,680 --> 00:39:19,390
也可以设置为1,2,3

442
00:39:16,840 --> 00:39:21,670
Gurobi 根据这些数值

443
00:39:19,390 --> 00:39:23,680
决定数值计算的保守程度，包括

444
00:39:21,670 --> 00:39:25,930
MarkowitzTol 处理单纯形算法

445
00:39:27,970 --> 00:39:33,520
也决定什么时候转到 Quad 精度

446
00:39:30,450 --> 00:39:35,920
它也会限制 GomoryPasses

447
00:39:33,520 --> 00:39:37,780
减少可能会在一些具有挑战性的数值计算问题中带来问题

448
00:39:37,780 --> 00:39:41,490
它也会限制CutPasses 和 CutAggregation

449
00:39:41,490 --> 00:39:47,849
等等

450
00:39:44,730 --> 00:39:49,740
所以这些是遇到数值计算问题时常用的方法

451
00:39:47,849 --> 00:39:51,659
可以将 NumericFocus 设置为1到3

452
00:39:54,839 --> 00:40:00,750
如果你希望改变单纯形法的定价方式，可以修改 NormAdjust

453
00:40:00,750 --> 00:40:06,990
如果内点法（障碍法）遇到麻烦

454
00:40:04,859 --> 00:40:10,080
可以采用 BarHomogeneous

455
00:40:06,990 --> 00:40:12,060
也可以尝试 CrossoverBasis

456
00:40:12,060 --> 00:40:18,750
或者关闭掉 Cuts

457
00:40:14,820 --> 00:40:22,520
在一些具有数值挑战性的问题中，这些参数可能会导致数值问题

458
00:40:23,669 --> 00:40:29,879
再重复一次，这些参数不是为了修复数值问题

459
00:40:29,879 --> 00:40:36,510
他们只是面对数值问题的变通处理方法

460
00:40:32,580 --> 00:40:43,210
真正修复数值问题的方法是回到模型中，建立一个合适的模型

461
00:40:44,639 --> 00:40:48,869
这是本次讲座的最后一部分

462
00:40:46,740 --> 00:40:52,619
关于条件数

463
00:40:48,869 --> 00:40:55,530
到目前为止问题要么来源于四舍五入

464
00:40:52,619 --> 00:40:58,230
没有提供足够多的精度

465
00:40:55,530 --> 00:41:01,859
要么计算机数值表达的局限性

466
00:40:58,230 --> 00:41:06,889
无法让一切严丝合缝

467
00:41:07,560 --> 00:41:12,990
但是还有些问题

468
00:41:12,990 --> 00:41:17,369
源自问题的几何涵义

469
00:41:16,020 --> 00:41:21,750
这就是和条件数有关

470
00:41:17,369 --> 00:41:24,570
也就是之前看到的 Kappa

471
00:41:21,750 --> 00:41:28,500
优化问题的条件数

472
00:41:24,570 --> 00:41:33,280
用来捕捉优化问题或者优化解

473
00:41:34,109 --> 00:41:41,579
对于输入数据微小变化的敏感度

474
00:41:37,980 --> 00:41:45,000
通常的定义，特别对于线性系统

475
00:41:41,579 --> 00:41:49,550
称之为 Kappa，定义为

476
00:41:50,040 --> 00:41:54,360
矩阵的范数和逆的乘积

477
00:41:54,360 --> 00:41:59,640
我更喜欢几何意义上的解释

478
00:41:56,940 --> 00:42:04,810
这和可行域圆形规整有关系

479
00:42:05,670 --> 00:42:12,810
事实上你可以想象为

480
00:42:09,360 --> 00:42:15,690
包含可行域的最小球

481
00:42:15,690 --> 00:42:22,380
和被可行域包含的最大球

482
00:42:19,200 --> 00:42:25,500
他们之间的比例关系

483
00:42:22,380 --> 00:42:28,770
举二个例子

484
00:42:25,500 --> 00:42:31,230
比如你可以通过很多很多边界线性不等式

485
00:42:28,770 --> 00:42:33,660
建立这样的模型

486
00:42:33,660 --> 00:42:38,390
条件数的几何意义就是外围淡灰色的圆

487
00:42:36,330 --> 00:42:43,910
和内圈深灰色的圆之间的比值

488
00:42:44,430 --> 00:42:49,950
这很接近1

489
00:42:47,610 --> 00:42:53,370
这个条件数说明

490
00:42:49,950 --> 00:42:56,700
如果比值很小，那么输入数据中的微小变化

491
00:42:53,370 --> 00:42:59,670
导致解的变化也会很小

492
00:42:56,700 --> 00:43:03,440
事实也如此，这是我的代码

493
00:43:04,560 --> 00:43:09,590
我用1000个不等式定义了圆形区域

494
00:43:09,590 --> 00:43:14,850
在系数上星星点点做了一点修改

495
00:43:12,000 --> 00:43:17,130
然后再优化

496
00:43:17,130 --> 00:43:23,910
看看原始单纯形解上有什么变化

497
00:43:19,350 --> 00:43:27,570
这是500次迭代后得到的

498
00:43:23,910 --> 00:43:36,550
系数的微小变化（1e-6) 导致原始解同等量级的变化

499
00:43:37,590 --> 00:43:47,040
从几何意义上也可以看出

500
00:43:47,040 --> 00:43:51,780
这也很合理

501
00:43:49,410 --> 00:43:54,720
这些问题很容易解决

502
00:43:51,780 --> 00:43:58,410
但如果我需要优化的可行域

503
00:43:54,720 --> 00:44:00,570
是一个瘦长的三角形

504
00:43:58,410 --> 00:44:03,630
可以想象如果我拉伸这个三角形

505
00:44:00,570 --> 00:44:05,190
里面的圆形会越来越小

506
00:44:05,190 --> 00:44:11,190
外面的圆形会越来越大

507
00:44:08,250 --> 00:44:14,580
比值会越来越糟糕

508
00:44:14,580 --> 00:44:18,840
我定义这个问题

509
00:44:16,800 --> 00:44:22,350
优化它

510
00:44:22,350 --> 00:44:31,399
然后在目标函数上做非常微小的变化

511
00:44:32,460 --> 00:44:37,260
虽然只有 1e-6 的变化

512
00:44:37,260 --> 00:44:42,030
但在原始单纯形解上有16次方的改变

513
00:44:39,659 --> 00:44:43,409
这并非错误结果

514
00:44:43,409 --> 00:44:49,350
其实后面这三列可以显示原始、对偶和其他边界违反的数值

515
00:44:49,350 --> 00:44:54,180
几乎接近0

516
00:44:51,840 --> 00:44:55,980
说明结果是正确的，但问题本身很糟糕

517
00:44:55,980 --> 00:45:01,830
这说明哪怕在目标函数中改变很小的数值

518
00:45:01,830 --> 00:45:09,180
都会带来原始解的巨大变化

519
00:45:09,180 --> 00:45:15,000
这个和数值问题无关

520
00:45:12,330 --> 00:45:16,820
这是和几何形态有关

521
00:45:15,000 --> 00:45:19,710
这又回到之前提到的模型缩放问题

522
00:45:16,820 --> 00:45:21,990
如果你的模型缩放合适

523
00:45:19,710 --> 00:45:24,750
那么会看起来四四方方，很规整

524
00:45:21,990 --> 00:45:27,570
那么一切就容易优化

525
00:45:24,750 --> 00:45:30,960
如果你有一个很狭长的区域

526
00:45:27,570 --> 00:45:34,110
那么你可能面临结果不稳定的情况

527
00:45:34,110 --> 00:45:43,619
我们做一个总结

528
00:45:39,659 --> 00:45:45,840
事实上数值稳定性源头不仅仅来自于数值

529
00:45:43,619 --> 00:45:48,869
也可能来自于几何形态

530
00:45:45,840 --> 00:45:50,909
Gurobi 不会对用户的数据进行猜测

531
00:45:48,869 --> 00:45:53,760
用户提供什么精度，Gurobi 就采用什么精度

532
00:45:50,909 --> 00:45:57,330
大部分情况下，处理数值问题最好的方式

533
00:45:53,760 --> 00:45:59,520
是审视模型做恰当的缩放

534
00:45:57,330 --> 00:46:02,190
或者改写模型公式

535
00:46:05,200 --> 00:46:10,140
感谢你关注这个讲座（本字幕根据声音翻译，发现问题请联系help@gurobi.cn)