在線性編程中將條件約束轉換爲線性約束

Question

我有兩個變量：x> = 0和y二進制（0或1），並且我有一個常數z> = 0。如何使用線性約束來描述以下條件：

If x = z then y = 1 else y = 0. 

我試圖通過定義另一個二元變量i和一個足夠大的正的常數U和添加約束

y - U * i = 0; 
x - U * (1 - i) = z; 

這是正確的解決這個問題？

Answer 1

真的有兩類約束，你是問：

1. 如果y=1，然後x=z。對於一些大的常M，你可以添加以下兩個約束來實現這一目標：

x-z <= M*(1-y) 
z-x <= M*(1-y) 

如果y=1那麼這些限制等同於x-z <= 0和z-x <= 0，這意味着x=z，如果y=0，那麼這些制約因素是x-z <= M和z-x <= M，如果我們選擇了足夠大的值，則不應該具有約束力。

1. if y=0 then x != z。從技術上講，您可以通過添加另一個二進制變量q來強制執行此約束，該變量控制是否x > z（q=1）或x < z（q=0）。然後，你可以添加以下的限制，其中m是一些小的正值和M是一些大的正值：

x-z >= mq - M(1-q) 
x-z <= Mq - m(1-q) 

如果q=1那麼這些限制必然x-z的範圍[m, M]，如果q=0然後這些約束將x-z約束到範圍[-M, -m]。

在實際使用求解器時，通常不會確保x != z，因爲通常允許小的邊界違例。因此，不要使用這些約束，我會建議不要爲您的模型添加任何約束來執行此規則。然後，如果您得到的最終解決方案爲y=0和x=z，則可以調整x以取值x+epsilon或x-epsilon，其值爲無限小的值epsilon。

Answer 2

所以我改變條件制約

if x = z then y = 0 else y = 1 

那麼答案將是

x - z <= M * y; 
x - z >= m * y; 

其中M是一個足夠大的正數，m是一個足夠小的正數。