Simplex minimization problem reformation with modulus cost function

[thomas49th]

Homework Statement

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

Homework Equations

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

 

[Ray Vickson]

Homework Statement

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

Homework Equations

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

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 modeled 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

 

[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

 

[Ray Vickson]

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

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

 

[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

 

[Ray Vickson]

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

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

 

[thomas49th]

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

 

[Ray Vickson]

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

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

 

[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

 

[Ray Vickson]

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

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

 

[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

 

[Ray Vickson]

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

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

 

[thomas49th]

All good upto here

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

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

 

[Ray Vickson]

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

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