1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simplex minimization problem reformation with modulus cost function

  1. Nov 10, 2012 #1
    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. jcsd
  3. Nov 10, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  4. Nov 12, 2012 #3
    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
     
  5. Nov 12, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  6. Nov 12, 2012 #5
    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
     
  7. Nov 12, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  8. Nov 12, 2012 #7
    The minimum is 5 in the first case and 0 in the second yes?
     
  9. Nov 12, 2012 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  10. Nov 12, 2012 #9
    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
     
  11. Nov 12, 2012 #10

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
  12. Nov 13, 2012 #11
    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
     
  13. Nov 13, 2012 #12

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
  14. Nov 14, 2012 #13
    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
     
  15. Nov 14, 2012 #14

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simplex minimization problem reformation with modulus cost function
Loading...