如何編碼的混合整數曼哈頓距離編程

Question

讓有兩點，（X1，Y1）和（x2，y2）的

DX = | X1 - X2 |

dy = | y1-y2 |

D_manhattan = DX + DY，其中DX，DY> = 0

我有點卡住如何讓X1 - X2積極爲| X1 - X2 |，想必我介紹代表極性的二元變量，但我不允許將極性開關乘以x1 - x2，因爲它們都是未知變量，並且會導致二次方程。

Answer 1

如果要最小化的|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」方法的變型。當然，你需要有所有可能值的上限（在你的情況下，這將是你的距離值：如果你的點在某個有界區域，這通常會是這種情況）