Lineareize constraint with absolute values

 1 1 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 31 Jan '14, 13:02 gecko 41●1●4 accept rate: 0% Are the variables x and y real? (31 Jan '14, 13:19) Taha yes (edited) (31 Jan '14, 14:22) gecko Since you already almost "stole" my usual line of reasoning ("This... because @Paul Rubin said so!"), did you also read ? (31 Jan '14, 16:42) fbahr ♦

 2 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 01 Feb '14, 09:11 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 31 Jan '14, 13:02

Seen: 5,650 times

Last updated: 01 Feb '14, 10:18

Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.