linear-programming - s_j=max{ a_j, s_i+t_ij } 可以表述为线性约束吗？

Question

我的问题是是否有技巧将以下内容表达为线性约束？

S_j=max{ a_j, S_i+t_ij }

其中 a_j 和 t_ij 是常数

提前谢谢了

Answer 1

是的，您可以通过引入一个新的二进制变量 y_j（0 或 1）和几个线性约束来做到这一点。

我们可以将您的约束重写为：

Sj = a      if a > Si + T
Sj = Si + T if a < Si + T


Sj = a y_j + (Si + T) (1 - yj)       .....(1)

假设 y_j = 0 如果 a 更大

y_j = 1 如果 a 小于 Si + T

M y_j + a - (Si + T) > 0   ....(2) 
where M is a big number, much bigger than a or Si or T.

如果 y_j 为 1，则上面的约束很容易满足，并且 Sj 将等于 a。如果 y_j 为 0，a 必须更大才能满足约束，并且Sj = Si + T

在您的公式中，只需包括 (1) 和 (2)，您将强制执行max约束。