How to make integer optimization with absolute values or sum of absolute values in python?

Question

I have a program where I want to minimize an absolute difference of two variables (an absolute error function). Say:

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

The function is subjected to the following constrains:

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

I am using the mip library (https://www.python-mip.com/), where I have defined both my objective function and my constrains.

The problem is that mip does not have an "abs" method. So I had to overcome that by spliting the main problem into two optimization sub-problems:

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

After solving the two separate problems, compare the two results, yield the min(abs(e)).

That should have worked, but mip does not seem to understand that the error can be negative. As I show below:

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

Again, the program results OptimizationStatus.INFEASIBLE, where clearly the combination X(0, 0) = 1 and X(1, 0) = 0 solves the problem.

Is it a formulation issue of my model? Or is it a bad behavior of the mip library?

Post your code.

user2357112
– user2357112

2020-09-28 20:20:53 +00:00
Commented Sep 28, 2020 at 20:20 — user2357112
– user2357112, Commented Sep 28, 2020 at 20:20

AirSquid · Accepted Answer · 2023-03-08 22:24:11Z

7

You can (and should) reformulate. Because you are minimizing the absolute value of a function, you can introduce a dummy variable and 2 constraints on that variable and then minimize the dummy variable to keep it linear. (ABS is a non-linear function).

So, introduce z such that:

z >= Ax - By

and

z >= -(Ax - By)

then your objective is to minimize z

Edit: For sum of absolute differences

In the case where you wish to minimize the sum of absolute differences, only slightly more work is required as you will need to repeat the above process for the indexing variable. Assuming that x and y are indexed by the set I you simply need to (in pseudocode ... implementation differs slightly based on framework):

Introduce z[i], which is indexed by the same set 'I' and

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

and minimize:

∑z[i]  (over the set I)

edited Mar 8, 2023 at 22:24

answered Sep 28, 2020 at 20:18

AirSquid

12k2 gold badges11 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

nicolasakf Over a year ago

Wouldn't it be z >= Ax - By and z >= -(Ax - By)?

AirSquid Over a year ago

Yep! I bungled transcribing your function. I'll edit the answer.

nicolasakf Over a year ago

And what if I had an objective function that is the result of a sum of absolute differences?

ayush singhal Over a year ago

But how do I get the values of x and y from this ?

AirSquid Over a year ago

That is completely dependent on which optimization framework you are using. Presumably, you solve the problem, minimizing z and then interrogate the solver for the values of the variables of interest in the solution

Collectives™ on Stack Overflow

How to make integer optimization with absolute values or sum of absolute values in python?

1 Answer 1

Edit: For sum of absolute differences

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Edit: For sum of absolute differences

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related