# Simplex minimization problem reformation with modulus cost function

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

## 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 Helper
Dearly Missed

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

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

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
Homework Helper
Dearly Missed
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

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
Homework Helper
Dearly Missed
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

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

Ray Vickson
Homework Helper
Dearly Missed
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

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
Homework Helper
Dearly Missed
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

Last edited:
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
Homework Helper
Dearly Missed
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

Last edited:
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
Homework Helper
Dearly Missed
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