如何在Python中使用绝对值或绝对值之和进行整数优化？

Question

我有一个程序，我想要最小化两个变量的绝对差（一个绝对误差函数）。比如说：

e_abs(x, y) = |Ax - By|; where e_abs(x, y) is my objective function that I want to minimize.

该函数受以下限制条件的约束：

x and y are integers;
x >= 0; y >= 0
x + y = C, where C is an arbitrary constant (also C >= 0)

我正在使用 mip 库（https://www.python-mip.com/），在其中定义了我的目标函数和约束条件。

问题在于 mip 没有“abs”方法。因此，我不得不将主要问题分解为两个优化子问题来解决：

e(x, y) = Ax - By

Porblem 1: minimize e(x, y); subject to e(x, y) >= 0
Porblem 2: maximize e(x, y); subject to e(x, y) <= 0

在解决了两个单独的问题后，比较两个结果，得到 min(abs(e))。

这应该可以工作，但是 mip 似乎不理解错误可以是负数。如下所示：

constr(0): -1.0941176470588232 X(0, 0) +6.199999999999998 X(1, 0) - error = -0.0
constr(1): error <= -0.0
constr(2): X(0, 0) + X(1, 0) = 1.0

Obs.: consider X(0, 0) as x and X(1, 0) as y in our example

程序再次返回OptimizationStatus.INFEASIBLE，显然组合X(0, 0) = 1 and X(1, 0) = 0可以解决问题。

这是我的模型公式的问题吗？还是mip库的行为有问题？

- nicolasakf

---

发布你的代码。 - user2357112

Answer 1

你可以（并且应该）重新表述。因为你正在最小化一个函数的绝对值，所以你可以引入一个虚拟变量和两个限制条件，并最小化虚拟变量以保持它的线性。 （ABS是一个非线性函数）。

因此，引入z，使得：

z >= Ax - By

并且

z >= -(Ax - By)

如果您的目标是最小化z

编辑：对于绝对差值之和

如果您希望最小化绝对差值之和，则需要进行略微更多的工作，因为您需要针对索引变量重复上述过程。假设x和y由集合I索引，您只需要（在伪代码中...实现因框架而异）：

引入由相同集合'I'索引的z[i]

for i in I:
  z[i] >= Ax[i] - By[i]
  z[i] >= -(Ax[i] - By[i])

并最小化：

∑z[i]  (over the set I)

- AirSquid

---

难道不应该是 z >= Ax - By 和 z >= -(Ax - By) 吗？ - nicolasakf

是的！我把你的函数记录错了。我会编辑答案。 - AirSquid

如果我的目标函数是绝对差值之和呢？ - nicolasakf

但是我该如何从中获取x和y的值呢？ - ayush singhal

这完全取决于您使用的优化框架。 假设您解决了问题，最小化 z，然后查询求解器以获取解决方案中感兴趣的变量的值。 - AirSquid