linear-programming - 在特殊有序集合中使用什么权重？

Question

我目前正在研究一个 MIP 问题，在那里我可以利用类型 2 (SOS2) 的特殊有序集。

我的问题是，我还没有完全理解这些集合。这样做的原因是因为我必须为我的 SOS2 中的变量分配权重。

我不确定我应该分配什么。我的集合中有一个非常明确的顺序，但我不确定权重应该是多少，我认为只分配 1,2,3 ... n 是不正确的？

所以我的问题是，有人可以向我解释特殊有序集中变量的权重是什么以及应该为它们分配什么值？

Answer 1

首先，他们定义了一个排序。特别是对于 SOS2 集合，有一个邻居的概念：在一个 SOS2 集合中，只有两个相邻变量可以是非负的。一些求解器还在他们的分支决策中使用权重。如果您有 x 值（如(1,2,3,10000). 因此，请查阅您的求解器文档。一般来说，sos 权重应该是唯一的。使用(1,2,3,...)通常是一个很好的默认值，否则使用 x 值之类的东西（假设您没有平行于 y 轴的线段）。

请注意，在许多情况下，具有二元变量的公式将优于 SOS 公式（对于可以对具有二元变量的公式应用智能切割的高端求解器尤其如此）。一些求解器甚至会尝试使用二进制变量自动将一些 SOS 集重新表述为一种形式。