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's gravatar image

gecko
4114
accept rate: 0%

edited 01 Feb '14, 08:04

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

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

?

(31 Jan '14, 16:42) fbahr ♦

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

link

answered 01 Feb '14, 09:11

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

edited 01 Feb '14, 09:12

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×79
×16

Asked: 31 Jan '14, 13:02

Seen: 5,529 times

Last updated: 01 Feb '14, 10:18

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