linear-programming - 如何在混合整数规划中编码曼哈顿距离

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 中作为变量 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”方法的变体，通常用于线性化二次项。当然，您需要有 x 所有可能值的上限。 (在您的情况下，这将是您的距离值:如果您的点位于某个有界区域内，通常会出现这种情况)