时间戳

首页 > 解决方案 > 如何在python中使用绝对值进行整数优化？

python - 如何在python中使用绝对值进行整数优化？

问题描述

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

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 库的不良行为？

标签： pythonoptimizationmixed-integer-programming

解决方案

您可以（并且应该）重新制定。因为您要最小化函数的绝对值，所以您可以在该变量上引入一个虚拟变量和 2 个约束，然后最小化虚拟变量以使其保持线性。（ABS 是非线性函数）。

所以，引入z这样的：

z >= Ax - By

和

z >= -(Ax - By)

那么你的目标是最小化z

推荐阅读