1

当使用纸浆定义混合整数线性规划问题时，可以这样定义 sos：

x1 = LpVariable('x1', cat = LpInteger)
x2 = LpVariable('x2', cat = LpInteger)
prob.sos1['sos'] = x1 + 2*x2

（“sos”或特殊排序的集合是一种特殊约束，指定集合中只有一个变量可以是非零的）。

我们看到这允许为 sos 变量（在本例中为 1,2）指定权重。大概它们定义了每个变量的优先级，即在分支时哪些变量首先允许为非零。

但是权重究竟是如何定义的呢？

底层求解器是 coin-or-cbc，我找不到任何关于他们如何使用 SOS 权重的信息。

4

1 回答 1

2

权重可用于分支，尽管并非所有求解器都以这种方式使用它们。我相信 CBC 确实如此，但您可能需要检查源代码才能确认。

通常需要 SOS2 中的权重来指定排序（SOS2 有邻居的概念）。SOS1 没有这个问题。

最后，如果您有良好的界限，二进制变量通常比 SOS1 变量更好。求解器在使用二元变量时可以进行更好的边界并生成更好的切割。我的规则是：如果您可以使用良好的 big-M 值来制定具有二进制变量的 SOS1 结构，请使用二进制变量。如果找不到好的大 M 值，请考虑 SOS1。

于 2018-09-16T07:49:09.347 回答