在混合整数线性规划中，连续变量块具有相同值

Question

我正在尝试对系统组件的操作进行建模，该组件将具有两种操作模式，称为1和2，以及空闲模式0。

闲置没有限制，但每个操作模式将持续恰好3个时间序列点，因此x_{i}= 1表示x_{i+1} = x_{i+2} = 1（无法发布图片，请使用下面的链接查看方程）operation mode 1 操作模式2也是如此。

例如，011102220是有效的，但01110220不是。

111111或222222无效，但在其他资源相关约束中已经处理了这个问题（系统没有足够的资源运行超过3个时间序列点），因此只要解决强制变量数组中出现三个连续的1或2的问题，就应该没问题。

提前致谢，

- BeWater

Answer 1

长度为三的运行可以建模为：

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)
1-y(t+3) >= y(t)-y(t-1)

其中 y(t) 是一个二进制变量。长度至少为三的连续运行可以通过删除最后一个约束来建模：

y(t+1) >= y(t)-y(t-1)
y(t+2) >= y(t)-y(t-1)

- Erwin Kalvelagen

---

谢谢！然而，如果y(t)=0，y(t-1)=1，则第三个约束条件将被解释为y(t+3) <= 0，这会在y值上引入不必要的0值锁定吗？（因为y(t)=0且y(t+3)=0，这迫使y(t+1)和y(t+2)为0，所以10⇒10000） - BeWater

我很抱歉，我没有听懂你的意思。如果 y(t)=0, y(t-1)=1，那么我们有 1-y(t+3) >= -1 或 y(t+3) <= 2，但这不是强制性的限制条件。 - Erwin Kalvelagen

你说得完全正确！我在计算中犯了一个愚蠢的错误。对于造成的困惑，我深表歉意。 - BeWater

Answer 2

让我们简化问题：我们假设只有二进制值，也就是说，我们只关心0和1。

引入一个新的辅助二进制向量start_block。这个向量标记了新块的开头。

在这个二进制向量中的非零值是约束条件的一部分，它们定义了块的蕴含关系。

让我们将解向量称为X。

蕴含是成对进行的。

# zero-order logic
start_block[x] -> X[x]
start_block[x] -> X[x+1]
start_block[x] -> X[x+2]

<=> 

# zero-order logic ( a->b <-> !a V b )
!start_block[x] V X[x]
!start_block[x] V X[x+1]
!start_block[x] V X[x+2]

<=>

# linear expression
(1 - start_block[x]) + X[x] >= 1
(1 - start_block[x]) + X[x+1] >= 1  
(1 - start_block[x]) + X[x+2] >= 1 

针对整个决策变量维度的 X 进行此操作（注意边界）。

请记住，这仅表示：如果 X 中有 1，则它是大小 >=3 的块的一部分。它可以是大小为 4 的块。由于我不知道您的模型确切情况，因此这是我能提供的最普遍的方法。当然，您可以进一步调整此设置以适应您的情况！

将此推广到整数变量不应该太难，但可能会引入新的辅助变量。

- sascha

---

不，它的意思是：如果start_block[x] == 1 -> 在X中的位置x、x+1、x+2将会有1。因此，如何将其纳入您的剩余模型取决于您的具体情况（一般流程是：start-block意味着X中的某些内容；因此，可能start_block是剩余模型中要使用的变量）。在代码块中，只有最后一部分是相关的。上面的两个块只是为了说明它来自哪里。 - sascha

如果您需要其他方向的效果，您可以随时对其进行建模（例如从X到start_block）。但是对于至少为3的块的这种特殊情况，这个方向非常实用。 - sascha

对于一些重复的跟进问题感到抱歉，作为新手，我认为我真的需要提高布尔代数的技能。我认为我需要的是另一种影响方向（从 x = x+1 = x+2 = 1 到强制 start_block[x] = 1）。然而，如果我只考虑另一种影响方向，那么我不会失去 X 中 1 必须以三个一组出现的控制吗？或者应该将两个方向都包含在约束条件中？ - BeWater

无法完全了解模型后回答。如何将其合并并在start_block上施加约束取决于您。我不知道您是否需要其他方向。上述方法需要您以某种方式使用start_block来引入非零值，并且约束会引起块效应。目前的公式中，如果在start_block上没有附加约束，则该方向将不起作用。相反，X-> start_vector也需要对start_vector施加一些约束才能看到一些效果。 - sascha

虽然有些泛泛，但是每个新接触整数规划的人都应该阅读像这个指南一样的东西。它可能不是你问题的答案，但会给出一些通用的想法（特别是二选一和条件约束）。 - sascha