v = |x1-x2| with 0<=xj<=C for j=1,2, C constant

I was trying to moel this relation by linear constraints. This is what I've done

equality is equivalente to superior and inferior relation.

begining with v>=|x1-x2| :

this "superior" relation can be modeled as follow:

v>=x1-x2 (I) v>=x2-x1 (II)

for v<=|x1-x2| :

this "inferior" relation can be modeled as follow:

we discuss the case if x1>=x2 or not

v<=x1-x2 (III) v<=x2-x1 (IIII)

but I don't believe that my linear constraints are sufficients and corrects, are they corrects?



I'm assuming that you're modeling a Linear Program where you want to minimize

min v = |x1 - x2|

0 <= x1 <= C
0 <= x2 <= C

This model is equivalent to

min v

x1 - x2 <= v
x2 - x1 <= v
v >= 0
0 <= x1 <= C
0 <= x2 <= C

In general, the trick used in Linear Programming when dealing with absolute values is to introduce an additional variable. You can find a lot of resources by searching for 'linear program absolute values'. See for example this question: https://math.stackexchange.com/questions/432003/converting-absolute-value-program-into-linear-program

  • nice, thanks. I want also to know if there are graphical methods to extract these linear constraints. Because sometimes it is really difficult to find them directly(for example for this example)
    – Ayman
    Apr 6 '21 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.