這可以用混合整數線性規劃來形式化嗎？

我想解決一個問題，那裏有一組需要在特定時間點之間移動的對象。這可以用混合整數線性規劃來形式化嗎？

我已經能夠正式大部分的約束線性規劃的方面，即：

object1FirstDepartureTime > X 
object1FirstArrivalTime < Y 
object1FirstArrivalTime - object1FirstDepartureTime > Z 
object1SecondDepartureTime - object1FirstArrivalTime > A

而且等等等等所有對象及其所有抵港/離港。目標函數將是在運輸中花費最少或最可能的時間。

我遇到的問題是有一個額外的限制：某些對象需要伴隨其他對象的行程持續時間。例如，object1可能伴隨着object2，object3或object4。這些物體本身有一定的到達或離開限制。我想讓我的（也許是混合整數）線性程序能夠處理伴隨對象的拾取。但是，在嘗試正式確定這一點時，我無法想出一種保持線性的方法。我想到的混合整數約束樣

object2GoWIthObject1 + object3GoWithObject1 + object4GoWithObject1 < 2 
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all less than 2 
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all integers

但我無法弄清楚如何表達，如「如果對象2老毛病對象1，它會在時間X離開與對象1，並且在時間到達ÿ限制「。這看起來是非線性的，因爲我會乘以布爾變量（如果對象2伴隨着對象1）乘以旅行時間。

當然，我可以爲每個「if ... then ...」語句創建不同的線性問題，但是使用60個伴隨路徑和10個伴隨對象，這會導致10^60個線性程序來解決，這並不好。

如果有人有任何直覺如何形式化這個線性規劃問題，以便決定「會X陪Y？」可以在問題本身表達，我會非常感激！

來源

2011-12-12 user1093512

的一種方法是使用大-M方法是這樣的：

object1FirstDepartureTime - object2FirstDepartureTime > -M * object2GoWIthObject1 
object1FirstDepartureTime - object2FirstDepartureTime < M * object2GoWIthObject1

M是一個足夠大的常數。 big-M方法的問題在於它導致LP放鬆不佳。

來源

2011-12-21 20:16:49 han

是的，你可以修改公式來處理你的約束。有許多涉及「Big-M」和新0-1的標準技巧來完成這一點。（韓的反應正確地指出這一點。）

爲了滿足您的特定非線性的限制，你會引入新的變量，0-1（如您的「GoWith」變量），然後在您的配方添加額外的線性約束。

讓我們把你的陳述要求：如果對象2個老毛病對象1，將在與對象1次X離開並在時間到達Ÿ

Start1 >= X 
Arrive1 <= Y

是你已經有對象1約束。

讓我們來介紹二進制變量Z12如果Object2與Object1一起移動，則爲1，否則Z12 = 0。

所以，

If Z12 = 1, then Start2 > X 
If Z12 = 1 then Arrive2 < Y

我們可以重寫此爲：

Start2 - X >= 0 if Z12 =1 
Start2 - X >= -M if Z12 =0, where M is a large number.

它們合併成一個線性約束：

Start2 - X >= M(Z12-1)

這個約束綁定時Z12爲1，除此之外很平常。

同樣，對象2的到來，以匹配Object1的到來，你可以這樣寫：

Arrive2 < Y if Z12=1 
Arrive2 < M if Z12=0

，這已經成爲

Arrive2 < Y + M(1-Z12), a linear constraint.

通過引入類似的二元變量Z13，Z14等，你可以只需一個線性公式就可以處理所有約束條件。

用於IP配方的更多「技巧」可在以下網址找到： http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new15.pdf

來源

2012-01-10 07:48:59

這可以用混合整數線性規劃來形式化嗎？

回答

相關問題