scheduling - 变量分支与约束分支

Question

有人可以向我解释一下，变量分支和约束分支（Ryan 和 Foster）有什么区别？

我正在阅读这篇文章：

DM Ryan (J. Op1 Res. Soc. Vol. 4) 的“Aircrew Rostering 中大规模广义集分区问题的解决方案”

在我看来，这与作为集合分区问题的工作人员调度或护士排班问题完全相同。

两种分支方法都在 1 个变量上分支，有什么区别？

我正在尝试使用 SCIP 在 Python 中实现 Branch-and-Price。

Answer 1

我还没有阅读您所指的文本，但希望能够对约束分支为何是一种强大的技术有一个模糊/手动的理解。

考虑一个安排护士的大集合划分问题。如果我们用变量分支来解决这个问题，每个分支都类似于说“护士 1,543 可以/不能工作轮班 16,325”。在这种情况下，每个分支对整个解决方案的影响很小。

相反，我们可以使用约束分支，它允许我们在每个分支上进行许多更改。我们这样做是为了迫使解决方案更加完整。

我们自己定义和分支的“虚变量”y_ij 可以从行覆盖表中选择。假设我们有一组 x 变量的小数，y_ij 是我们同时满足约束 i 和 j 的小数。虽然您说这是我们正在研究的“一个变量”是对的，但它会对解决方案产生更大的影响。

例如，如果我们在 y_12 上进行1 分支，那么我们将所有不满足约束 1 和 2 的列一起禁止。选择 y_ij 进行分支的方法是最接近整数（但仍然是小数），首选1-branches到0-branches。