ILPの論理的制約

Question

次の制約を記述したいと思います。

しましょう $z$ 次のような整数変数である $0\le z\le M$、および $t$ バイナリ変数であるここで $M$big-Mを示します。論理的な制約は次のとおりです。

• もし $z \leq M$ そして $z > 0$ その後 $t=1$;

• もし $z=0$ その後 $t=0$。

これは $z≤Mt$十分？ザ・$t$ そして $z$ 変数は私の目的関数ではなく変数です $t$ 目的関数の別の変数に接続されていますか？

どうもありがとうございました、私はあなたの助けに感謝します。

Answer 1

big-M制約 $z \le M t$ 強制します $z > 0 \implies t = 1$、同等にその対偶 $t = 0 \implies z = 0$、しかしその逆ではありません $$z = 0 \implies t = 0. \tag1$$ 実施するために $(1)$、その対偶を考慮してください $$t = 1 \implies z > 0 \tag2,$$ これはbig-M制約を介して適用できます $$\epsilon - z \le (\epsilon - 0)(1 - t),$$ 同等に、 $$z \ge \epsilon t,$$ どこ $\epsilon > 0$ の最小値を表す許容値です $z$ あなたが前向きであると考えるだろうと。