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)

aが大きい場合、y_j = 0としましょう

a が Si + T より小さい場合、y_j = 1

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制約が適用されます。