Converting a linear optimization problem with absolute values

[Yo388]

Homework Statement

Here is an alternative approach to handling absolute value terms as the decision variables: abs(x) is the smallest value z that satisfies x \leq z and -x \leq z. Using this,convert the following into a lp

Min 2x₁ + 3abs(x₂)

S.T x₁ + x₂ \geq 6

Homework Equations

Here is a pretext from my textbook that shows how to do it a different way

The Attempt at a Solution

After a while of staring at it ,I gave it a try

What do you guys think?

 

[Ray Vickson]

Homework Statement

Here is an alternative approach to handling absolute value terms as the decision variables: abs(x) is the smallest value z that satisfies x \leq z and -x \leq z. Using this,convert the following into a lp

Min 2x₁ + 3abs(x₂)

S.T x₁ + x₃ \geq 6

Homework Equations

Here is a pretext from my textbook that shows how to do it a different way

View attachment 61918

The Attempt at a Solution

After a while of staring at it ,I gave it a try

View attachment 61920

What do you guys think?

I think there is something wrong with the problem statement: it has $x_1$ and $x_2$ in the objective but $x_1$ and $x_3$ in the constraint.
Mod note: This is now fixed.[/color]
As written, the problem does not have a finite solution, since we can have $x_1 \rightarrow -\infty$, $x_3 = 6 - x_1 \rightarrow +\infty$ and $x_2 = 0$. If you really intend to have $x_1 \geq 0$ you need to say so.

In any case, you need only one constraint, not three. Basically, it is one of the standard methods for such problems to just replace $x_2$ by $x_2^+ - x_2^-$ (with $x_2^+, x_2^- \geq 0$) and to write $x_2^+ + x_2^-$ in place of $|x_2|$ in the objective.

 

[Yo388]

Hey

Ya sorry I just noticed as well that I made a mistake. there's no x3,I meant x2.

Anyways , you the way you have said I already know how to do. But the reason I am confused is that the question asks that the aforementioned observation be used in answering the question.

P.S I can't seem to edit the question to fix the mistake

 

[Mark44]

Hey

Ya sorry I just noticed as well that I made a mistake. there's no x3,I meant x2.

Anyways , you the way you have said I already know how to do. But the reason I am confused is that the question asks that the aforementioned observation be used in answering the question.

P.S I can't seem to edit the question to fix the mistake

I fixed it for you. Members have only a few hours to go back and edit their posts, but mentors don't have that restriction.

 

[Ray Vickson]

Hey

Ya sorry I just noticed as well that I made a mistake. there's no x3,I meant x2.

Anyways , you the way you have said I already know how to do. But the reason I am confused is that the question asks that the aforementioned observation be used in answering the question.

P.S I can't seem to edit the question to fix the mistake

There are two *different* ways of handling such problems, and you have mixed them up. For problems in which |x| appears only in the objective, and with a coefficient c > 0, we can:
(1) Replace $x$ in the constraints by $x^+ - x^-$ and $|x|$ by $x^+ + x^-$ in the objective; or
(2) keep x unchanged in the constraints, replace |x| in the objective by a new variable z, and add two constraints z ≥ x and z ≥ -x.

 

[Yo388]

There are two *different* ways of handling such problems, and you have mixed them up. For problems in which |x| appears only in the objective, and with a coefficient c > 0, we can:
(1) Replace $x$ in the constraints by $x^+ - x^-$ and $|x|$ by $x^+ + x^-$ in the objective; or
(2) keep x unchanged in the constraints, replace |x| in the objective by a new variable z, and add two constraints z ≥ x and z ≥ -x.

Ya i know the first way as its stated in the textbook but the way the question is being asked to be done is how you stated in (2).

So if I replace |x₂| in this case by z and add the two constraints like you said, what i am wondering is what do the x₂ and -x₂ mean in the constraints because they are not in the objective function

Min 2x₁ +3z

S.T x₁ + x₂ ≥ 6
z ≥ x₂ and z ≥ -x₂

 

[Ray Vickson]

Ya i know the first way as its stated in the textbook but the way the question is being asked to be done is how you stated in (2).

So if I replace |x₂| in this case by z and add the two constraints like you said, what i am wondering is what do the x₂ and -x₂ mean in the constraints because they are not in the objective function

Min 2x₁ +3z

S.T x₁ + x₂ ≥ 6
z ≥ x₂ and z ≥ -x₂

Stop worrying; your formulation is OK exactly as it stands. When you try to make z small, that will restrict x_2 in the constraints, so everything *really is* connected together. If you don't believe it, try solving both formulations (either by hand or by using an LP computer package).