python - 如何在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 库的不良行为？

Answer 1

您可以(并且应该)重新制定。因为您正在最小化函数的绝对值，所以您可以引入一个虚拟变量和该变量的 2 个约束，然后最小化虚拟变量以使其保持线性。 (ABS 是非线性函数)。
那么，介绍一下z使得:

z >= Ax - By

和

z >= -(Ax - By)

那么你的目标是最小化 z