讓有兩點,(X1,Y1)和(x2,y2)的如何編碼的混合整數曼哈頓距離編程
DX = | X1 - X2 |
dy = | y1-y2 |
D_manhattan = DX + DY,其中DX,DY> = 0
我有點卡住如何讓X1 - X2積極爲| X1 - X2 |,想必我介紹代表極性的二元變量,但我不允許將極性開關乘以x1 - x2,因爲它們都是未知變量,並且會導致二次方程。
讓有兩點,(X1,Y1)和(x2,y2)的如何編碼的混合整數曼哈頓距離編程
DX = | X1 - X2 |
dy = | y1-y2 |
D_manhattan = DX + DY,其中DX,DY> = 0
我有點卡住如何讓X1 - X2積極爲| X1 - X2 |,想必我介紹代表極性的二元變量,但我不允許將極性開關乘以x1 - x2,因爲它們都是未知變量,並且會導致二次方程。
如果要最小化的|x|
的增加函數(或最大化當然的遞減函數,), 你總是可以有任何數量x
的在LP的aboslute值作爲變量absx
如:
absx >= x
absx >= -x
它可以工作,因爲值absx
將趨於其下限,因此它將達到x
或-x
。另一方面,如果要最小化|x|
的遞減函數,則問題不是凸的,並且不能被建模爲lp
。
對於所有這些類型的問題,最好將問題的簡化版本與目標相加,因爲它經常用於所有這些建模技術。
編輯
我的意思是,有對此類問題沒有通用的解決方案:你一般不能代表一個線性問題的絕對值,但在實際情況中,通常可以。
例如,考慮該問題:
max y
y <= | x |
-1 <= x <= 2
0 <= y
它是有界的,並且具有一個明顯的解決方案(2,2),但它不能被建模爲LP,因爲域不是凸(它看起來像'M'下的形狀,如果你畫它)。
沒有你的模型,我不可能回答我害怕的問題。
編輯2
我很抱歉,我沒有正確讀取的問題。如果您可以使用二進制變量和(如果所有距離都以某個常數M
爲界),則可以執行某些操作。
我們使用:
ax
來表示量x
sx
的絕對值來表示的x
(sx = 1
如果x >= 0
)符號如果x < 0
和ax = x
以其他方式執行,則始終驗證這些約束條件:
ax <= x + M * (1 - sx)
ax >= x - M * (1 - sx)
這些制約總是如果x >= 0
覈實,並執行ax = -x
否則:
ax <= -x + M * sx
ax >= -x - M * sx
這是經常被用來線性二次項「大M」方法的變型。當然,你需要有所有可能值的上限(在你的情況下,這將是你的距離值:如果你的點在某個有界區域,這通常會是這種情況)
實際上距離只受限制,成本函數是間接相關的變量。因此,無論其最小或最大值是不是真的知道。 –
在這種情況下,如果可能的話,您需要發佈您的問題(或至少一個簡化版本):請參閱上面的我的編輯。 –
對不起這個爛攤子!如果距離有界,實際上可以用二進制變量,見第二次編輯;) –