2

让我们有两个点，(x1, y1) 和 (x2,y2)

dx = |x1 - x2|

dy = |y1 - y2|

D_manhattan = dx + dy 其中 dx,dy >= 0

我有点不知道如何让 |x1 - x2| 的 x1 - x2 为正，大概我引入了一个表示极性的二进制变量，但我不允许将极性开关乘以 x1 - x2，因为它们都是未知变量和这将导致二次。

4

1 回答 1

2

如果您要最小化 的增加函数|x|（或最大化减少函数，当然），您总是可以将xlp 中任何数量的绝对值作为变量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
  • 表示( if )sx符号的二进制变量xsx = 1x >= 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（在您的情况下，这将是您的距离值：如果您的点位于某个有界区域，通常就是这种情况）

于 2013-10-04T22:44:50.290 回答