I want to reformulate the following problem as a linear program: \[ \min ax + by \] st \[ x + y + |x+y| = c, \] \[ x,y,c \in \mathbb{R} \] The standard trick to eliminate the absolute value does: \[ \min ax + by \] st \[ x +y + z = c\ \quad -z\leq x + y \leq z , z\geq 0\] But this in fact increases the feasible region for x and y, as it allow them to be 0 (even if c>0). I have a bunch of these constraints, is there any way around this without introducing binary variables? I know that this is related to this, but im not quite sure when the conditions for the trick DO apply. I tried to penalize z, but that did not work.
asked
gecko |

You have a constraint of the form z + |z] = c, where z = x + y Let's look at the left hand side: z + |z| = 2z if z >= 0 z + |z| = 0 if z <= 0 Then, depending on the value of c: if c < 0 the problem is infeasible if c >= 0 you can replace the constraint by x + y = c/2 You then have a LP
answered
jfpuget |

Are the variables x and y real?

yes (edited)

Since you already almost "stole" my usual line of reasoning ("This... because @Paul Rubin said so!"), did you also read

`>`

http://orinanobworld.blogspot.de/2012/07/modeling-absolute-values.html?