如何用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/)，我在其中定义了 objective 函数和约束。

问题是 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 是一个 non-linear 函数）。

因此，引入 z 这样：

z >= Ax - By

和

z >= -(Ax - By)

那么你的objective就是最小化z

如何用python中的绝对值进行整数优化？

How to make integer optimization with absolute values in python?

python

optimization

mixed-integer-programming