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

Question

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

怠速没有限制，但每种运行模式会持续正好3个时间序列点，所以x_{i}= 1表示x_{i+1} = x_{i+2} = 1 (不能 post 图片，请使用下面的 link 公式） operation mode 1

同样适用于操作模式 2。

例如。 011102220 有效，但 01110220 无效。

111111 或 222222 无效，但这在其他与资源相关的约束中得到解决（系统将没有足够的资源来运行超过 3 个时间序列点），因此只要有关问题强制变量数组中三个连续的1或2是地址，应该没问题。

提前致谢，

Answer 1

让我们稍微简化一下问题：假设我们只有二进制值，也就是说，我们只关心 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 个块。因为我不完全了解您的模型，所以这是我可以提供的最通用的方法。当然，您可以根据自己的情况进一步调整！

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

Answer 2

长度恰好为三的游程可以建模为：

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) 是二进制变量。通过删除最后一个约束，可以对长度至少为 3 的游程建模：

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

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

block of consecutive variables to have same value in mixed-integer linear programming

mathematical-optimization

linear-programming

integer-programming