如何编码的混合整数曼哈顿距离编程

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”方法的变型。当然，你需要有所有可能值的上限（在你的情况下，这将是你的距离值：如果你的点在某个有界区域，这通常会是这种情况）