Simplex minimization problem reformation with modulus cost function

1. Nov 10, 2012

thomas49th

1. The problem statement, all variables and given/known data
If I said minimize the cost function
|a-2b| + |-3a-b|

subject to
2a + b <= 6

a,b >= 0

We can all see it's 0,0 but if I want to apply the simplex algorithm to it, how do I reformulate the problem into something I can use

2. Relevant equations

3. The attempt at a solution
I thought about letting y = |a-2b|and z = |-3a-b|

then isn't y = a-2b, y = -a+2b
and z = -3a-b, z = 3a+b

then saying minimize y+z subject to
2a + b <= 6
y = a-2b
y = -a+2b
z = -3a-b
z = 3a+b

Is this allowed?

Thanks
Thomas

2. Nov 10, 2012

Ray Vickson

Not quite: you need inequalities y ≥ a-2b and y ≥ 2b - a, etc.

Obviously, if you impose both as equalities you must have y = a - 2b = 0. In this particular problem that would not give a wrong solution because the optimal solution is a = b = 0. However, if we changed the constraint to 2a + b >= 6, your suggestion would give a problem that might be far from optimal, or possibly even infeasible. (Actually, it would be infeasible, since it would require both 2b-a=0 and 3a + b = 0, with 2a + b >= 6 and a,b >= 0.)

Alternatively, you can write yp - yn = a - 2b, with yp, yn >= 0, and you want to minimize yp+yn. This formulation has more variables but fewer constraints. This can also be generalized to handle the problem of Maximizing the absolute values, but that problem needs additional binary variables plus some extra constraints---that is, it must be modelled as an MIP problem, rather than a pure LP: we need also that either yp = 0 or yn = 0. That happens automatically in the min problem, so can be ignored.

RGV

3. Nov 12, 2012

thomas49th

Hi,

I'm not quite sure why you can write this

yp - yn = a - 2b

What exactly are you trying to say here and where would yp + yn come from?

Thanks
Thomas

4. Nov 12, 2012

Ray Vickson

Suppose, for example, that a - 2b = 5. What do you get when you solve the problem min yp+yn, subject to yp - yn = 5, yp, yn >= 0? If, instead, you have a - 2b = -5, what do you get when you solve the problem min yp + yn, subject to yp - yn = -5, yp, yn >= 0?

RGV

5. Nov 12, 2012

thomas49th

So basically yp - yn = 5 is a constraint
along with yp, yn >= 0.

my objective function is yp+yn

But how does a - 2b = 5 fit in here? What is the translate between y+ and y- and a and b?

Thanks
Thomas

6. Nov 12, 2012

Ray Vickson

Forget about a and b. Just answer my two questions: what would you get if you had (i) min yp + yn, st yp - yn = 5, yp,yn >=0; and if you had (ii) min yp + yn st yp -yn = -5, yp, yn >= 0?

RGV

7. Nov 12, 2012

thomas49th

The minimum is 5 in the first case and 0 in the second yes?

8. Nov 12, 2012

Ray Vickson

No, not 0 in the second case. For yp and yn >= 0, the only way to get yp + yn = 0 would be to have yp = yn = 0, and that would not satisfy the constraint yp - yn = -5.

RGV

9. Nov 12, 2012

thomas49th

sorry yeah equality as opposed to inequality, so it's 5 at y+ = 0, y- = 5.

So where are you trying to lead me to here?

Thanks
Thomas :P

10. Nov 12, 2012

Ray Vickson

Back to the beginning: you asked how to represent an absolute value minimization objective in linear terms. That is what I have been attempting to explain to you, but leaving you to do most of the work.

RGV

Last edited: Nov 12, 2012
11. Nov 13, 2012

thomas49th

Thanks for the help,

But I'm not making the mental link

So far I know we can write |a-2b| as 2 inequalities

y ≥ a-2b and y ≥ 2b - a

But I don't see how the equation

yp - yn = a - 2b

comes about, nor why we then go onto maximise yp+yn

Thanks
Thomas

12. Nov 13, 2012

Ray Vickson

Well, alright. You have already solved the problem one way, so I guess it is OK to supply the details of another way without violating the Forum rules.

The above is just the familiar splitting up of a number into positive and negative parts, then expressing the absolute value as the sum of the parts.

Look at min (p + n), subject to p-n = X, p,n >= 0. If X > 0, one feasible solution is (p,n) = (X,0); another feasible solution is (p,n) = (X+1,1), another is (p,n) = (X+2,2), ... and in general, a feasible solution is (p,n) = (X+t,t) for any t >= 0. However, among all these feasible solutions, the unique one that minimizes the sum p + n is (p,n) = (X,0). Next, suppose X < 0. One feasible solution is (p,n) = (0,-X) (noting that -X = |X| > 0); another is (p,n) = (1,-X+1), another is (p,n) = (2,-X+2), ... . Among these, the unique one that minimizes p+n is (p,n) = (0,-X) = (0,|X|), giving p+n = |X|. So, for the problem min (p+n), st p-n = X, p,n >= 0, we have
(p+n)min = |X|.

Of course, using min z, s.t. z >= X and z >= -X is another way. One way has fewer variables and more constraints, the other has more variables and fewer constraints. Each method has advantages in certain contexts.

RGV

Last edited: Nov 13, 2012
13. Nov 14, 2012

thomas49th

All good upto here

I feel like a complete incompetent.

p-n=X. So we set p = 0. n = -X. Ok the first bit makes sense but I don't understand how I can "note" -X = |X| > 0. You're saying that -X is the same as |X| (when the modulus of X is greater than 0 (aka X is not zero)).

Maybe you already did, but can you show me exactly how you obtained -X = |X| > 0 and (p,n) = (0,-X) = (0,|X|)

Many many thanks
Thomas

14. Nov 14, 2012

Ray Vickson

No. When X > 0 we set p = X and n = 0. When X < 0 (that is, when X = -|X|) we set p = 0 and n = |X| = -X > 0.

OK, one very last time! Look: 5 = 5 - 0 = 6 - 1 = 7 - 2 = 8 - 3 = ... . There are lots of ways to write 5 as p-n with p,n >= 0, but the way that minimizes p+n is the first one: p = 5 and n = 0, giving p+n = 5 = |5|. Next, consider -5. We have -5 = 0 - 5 = 1 - 6 = 2 - 7 = 3 - 8 = .... . There are lots of ways to write -5 as p - n with p,n >= 0, but the one that minimizes p+n is the first one: p = 0 and n = 5. This gives p+n = 5 = |-5|.

Now I'm out of here.

RGV