Converting a linear optimization problem with absolute values

In summary, the alternative approach to handling absolute value terms as decision variables is to replace them with a new variable z and add two constraints z ≥ x and z ≥ -x. This is used to convert the given problem into an LP form, with the objective function being Min 2x1 +3z and the constraint being x1 + x2 ≥ 6. This approach is different from the one stated in the textbook but can still be used to solve the problem.
  • #1
Yo388
9
0

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 [itex]\leq[/itex] z and -x [itex]\leq[/itex] z. Using this,convert the following into a lp

Min 2x1 + 3abs(x2)

S.T x1 + x2 [itex]\geq[/itex] 6

Homework Equations


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

20130917_232043_2.jpg


The Attempt at a Solution



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

20130917_231852_5.jpg


What do you guys think?
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
Yo388 said:

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 [itex]\leq[/itex] z and -x [itex]\leq[/itex] z. Using this,convert the following into a lp

Min 2x1 + 3abs(x2)

S.T x1 + x3 [itex]\geq[/itex] 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.
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.
 
Last edited by a moderator:
  • #3
Hey

Ya sorry I just noticed as well that I made a mistake. Theres 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
 
  • #4
Yo388 said:
Hey

Ya sorry I just noticed as well that I made a mistake. Theres 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.
 
  • Like
Likes 1 person
  • #5
Yo388 said:
Hey

Ya sorry I just noticed as well that I made a mistake. Theres 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.
 
  • Like
Likes 1 person
  • #6
Ray Vickson said:
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 |x2| in this case by z and add the two constraints like you said, what i am wondering is what do the x2 and -x2 mean in the constraints because they are not in the objective function

Min 2x1 +3z

S.T x1 + x2 ≥ 6
z ≥ x2 and z ≥ -x2
 
  • #7
Yo388 said:
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 |x2| in this case by z and add the two constraints like you said, what i am wondering is what do the x2 and -x2 mean in the constraints because they are not in the objective function

Min 2x1 +3z

S.T x1 + x2 ≥ 6
z ≥ x2 and z ≥ -x2

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).
 
  • Like
Likes 1 person

1. What is a linear optimization problem with absolute values?

A linear optimization problem with absolute values is a type of mathematical problem that involves finding the maximum or minimum value of a linear function with constraints that include absolute value expressions. These expressions represent the distance between a variable and a fixed point, and can be converted into linear constraints by breaking them into two separate constraints.

2. How do you convert a linear optimization problem with absolute values?

To convert a linear optimization problem with absolute values, you first need to identify the absolute value expressions in the constraints. Then, you can break each expression into two separate constraints, one for when the variable is positive and one for when it is negative. Finally, you can use standard linear optimization techniques to solve the resulting problem.

3. What are the benefits of converting a linear optimization problem with absolute values?

Converting a linear optimization problem with absolute values can make it easier to solve, as linear optimization techniques are well-developed and can be applied to a wider range of problems. Additionally, converting the problem can often lead to a more efficient and accurate solution.

4. Are there any limitations to converting a linear optimization problem with absolute values?

One limitation of converting a linear optimization problem with absolute values is that it may introduce additional variables and constraints, making the problem more complex. Additionally, the converted problem may not always accurately reflect the original problem, so it is important to carefully check the solution to ensure its validity.

5. Can a linear optimization problem with absolute values be solved using software?

Yes, there are many software programs that can solve linear optimization problems with absolute values. These programs use algorithms and mathematical techniques to quickly and accurately find the optimal solution. However, it is important to understand the conversion process in order to properly set up the problem in the software.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
18
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
3K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
979
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
13
Views
3K
Back
Top