等價製劑

Question

等價製劑

9

我有一個簡單的模型，例如：

">開始{align} \ max＆\ quad z = X_1 + X_2 + X_3 + X_4 \\\ text {st}＆\ quad y_1 + y_2 + y_3 + y_4 = 2\\＆\ quad X_1 \ leq y_1 \\ && \ quad X_2 \ leq y_1 + y_2 \\ && \ quad X_3 \ leq y_2 + y_3 \\ && \ quad X_4 \ leq y_1 + y_4 \\ && \ quad x，y\ in \ {0,1 \}。\ end {align}

可以通過刪除 $ X_1 $ 變量 $ X_1 \ leq y_1 $ 來簡化上述公式約束，然後在目標函數中添加 $ y_1 $ 以獲得：

">開始{align} \ max＆\ quad z = y_1 + X_2 + X_3 + X_4 \\\ text {st}＆\ quad y_1 + y_2 + y_3 + y_4 = 2\\＆\ quad X_2 \ leq y_1 + y_2 \\＆\\ quad X_3 \ leq y_2 + y_3 \\＆\\ quad X_4 \ leq y_1 + y_4 \\＆\ quad x，y \ in \ {0,1 \}\ end {align}

因為

優化的方向是最大化，
目標函數係數為 $ 1 $ ，
$ y $ 的邊界是 $ x $ 的和
變量都是二進制的。

是否有可能評估這兩種製劑的多表位或（多表位的極點）的任何結果，例如"這兩個多表位是等效的，因為它們產生具有該目標函數的相同最優解"？您將用什麼方法證明這兩種公式的等效性？

來源分享

創建於2019-12-19 15:45:112019-12-19 15:45:11 Evren Guney

1 答案

Nikos Kazazakis · Answer 1 · 2019-12-20T00:43:27Z

This kind of depends on how one defines "equivalent", but in my opinion these formulations are not equivalent. Notice that in the original expression $X_1$ can be $0$ when $y_1=1$. By performing that substitution, you effectively fix that degree of freedom because now your objective will be incremented by $1$ if $y_1=1$, which was not necessarily the case in the original formulation.

While this might or might not give you the same optimal value, there is no guarantee that your active set will be the same (and although it's hard to tell without solving the problem in this case I suspect they will not be).

In terms of the polytope, you created a different polytope which possibly shares one or more vertices with the original one.

等價製劑

1 答案