线性规划 - 等于表达式符号的变量

Question

我正在尝试编写一个线性程序，需要一个等于 x-c 符号的变量 z，其中 x 是另一个变量，c 是一个常数。

我考虑过

z = (x-c)/|x-c|

。不幸的是，如果 x=c，则会除以 0。

我不能使用 z=x-c，因为我不想通过 x 和 c 之间的差异大小来对其进行加权。

有谁知道表达 z 的好方法，使其成为 x-c 的符号吗？

感谢您的帮助和建议！

Answer 1

您无法使用线性程序精确建模

z = sign(x-c)

（因为 LP 中的约束仅限于变量的线性组合）。

但是，如果您愿意将线性程序转换为混合整数程序，您可以建模

sign

，您可以使用以下两个约束对其进行建模：

 L*b <= x - c <= U*(1-b)
 z = 1 - 2*b

其中

b

是二元变量，

L

和

U

是数量

x-c

的下限和上限。如果

b = 0

，我们就有

0 <= x - c <= U

和

z = 1

。如果

b = 1

，我们有

L <= x - c <= 0

和

z = 1 - 2*1 = -1

。

您可以使用像Gurobi这样的求解器来求解混合整数程序。

Answer 2

对于 k » 1，这是符号函数的平滑逼近：

还有

当 ε → 0

这两个近似值没有除以 0 的问题，但现在您必须调整参数。

---

在某些语言（例如 C++ / C）中，您可以简单地编写如下内容：

double sgn(double x)
{
  return (x > 0.0) - (x < 0.0);
}

无论如何，考虑到许多环境/语言已经具有符号功能，例如

Mathematica 中的
• Sign[x]
Matlab 中的
• sign(x)
Java 中的
• Math.signum(x) Fortran 中的
• sign(1, x) R 中的
• sign(x)
密切注意 x 等于 0 时会发生什么（例如 Fortran 函数将返回 1，而其他语言则返回 0）。

Answer 3

x-c+M×s-N×t==0

和

z+s+t==1

，其中

z,s,t

是代表零、负或正的布尔值，

M

和

N

代表松弛变量。这非常简单。其他回答说不可能是错误的。

M×s

和

N×t

通过 Fortet 不等式很容易线性化。因此，接受的答案是低于标准且具有误导性的。