混合整数线性规划中具有相同值的连续变量块 [英] block of consecutive variables to have same value in mixed-integer linear programming

问题描述

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

I am trying to model the operation of a system component, the component will have two operating modes, let's call them 1 and 2, plus the idle mode 0

空转没有限制，但是每种操作模式都将持续3个时间序列点，因此x_ {i} = 1表示x_ {i + 1} = x_ {i + 2} = 1(无法发布图片，请使用下面的公式链接) 操作模式1

There is no limit on idling, but each operating mode will last for exactly 3 time-series points, so x_{i}= 1 means x_{i+1} = x_{i+2} = 1 (cannot post images, please use the link below for the equation) operation mode 1

工作模式2相同.

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

For example. 011102220 is valid, but 01110220 is not.

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

111111 or 222222 are not valid, but this is taken care of in other resource related constraints (the system will not have enough resource to operate for more than 3 time-series points), so as long as the issue regarding to forcing three consecutive 1s or 2s in the variable array is address, it should be fine.

预先感谢

推荐答案

让我们稍微简化一下问题:我们假设我们只有二进制值，也就是说，我们只关心0和1.

Let's simplify the problem somewhat: we assume we have only binary values, meaning, that we only care about 0's and 1's.

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

Introduce a new auxiliary binary vector start_block. This vector mark beginnings of new blocks.

此二进制矢量中的非零值是约束的一部分，它定义了块的含义.

A non-zero value within this binary-vector is part of the constraints, which define the implication of a 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的整个决策变量维度(关注边界)执行此操作.

Do this for the whole decision-variable dimension of X (caring about borders).

请记住，这仅表示:如果X中有1，则它是大于等于3的块的一部分.可能是4块.因为我不完全了解您的模型，所以这是我可以提供的最通用的方法.当然，您可以根据自己的情况进行调整！

Keep in mind, that this only says: if there is a 1 in X, it's part of a block of size >=3. It can be a block of 4. As i don't know your model exactly, that's the most general approach i can offer. Of course you can tune this further for your case!

将其概括为整数变量应该不太难，但是可能会引入新的辅助变量.

Generalizing this for integer-variables should not be too hard, but might introduce new auxiliary variables.

这篇关于混合整数线性规划中具有相同值的连续变量块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！