Results 1 to 4 of 4

Math Help - branch-and-bound tree for solving IPs

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    33
    Thanks
    1

    branch-and-bound tree for solving IPs

    max z = 4x + 3y
    4x + 9y <= 26
    8x + 5y <= 17
    x >= 0
    y >= 0

    I know you branch off the x or y with a decimal answer, but this gives LP relaxation: x=0.442 , y=2.692 , z=9.846 and I don't understand which one you're supposed to branch off... Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2009
    Posts
    27
    what do you mean? Branch and bound is the method you use to find the solution, you dont know how to do this is that the problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    33
    Thanks
    1
    No sorry maybe I didn't describe it very well. We are allowed to use software to find the solution so for example another problem gave x=5, y=2.5, z=17.5 but we want integer solutions so we branched y<=2 and y>=3 to get 2 more solutions and you keep branching until you get an optimal integer solution. But in this problem solving it gave x=0.442, y=2.692, z=0.846 so I wasn't sure how you determine if you branch off x or y since they are both noninteger solutions. I tried both but I can't seem to get any integer solutions.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by jlt1209 View Post
    No sorry maybe I didn't describe it very well. We are allowed to use software to find the solution so for example another problem gave x=5, y=2.5, z=17.5 but we want integer solutions so we branched y<=2 and y>=3 to get 2 more solutions and you keep branching until you get an optimal integer solution. But in this problem solving it gave x=0.442, y=2.692, z=0.846 so I wasn't sure how you determine if you branch off x or y since they are both noninteger solutions. I tried both but I can't seem to get any integer solutions.
    Branching off either x or y should work. I.e., you could try either

    x = 0 and x >=1

    or

    y <= 2 and y >= 3.

    If you get no integer solutions then either your problem is infeasible-- there are no integers which satisfy the constraints-- or you made a mistake somewhere. In this problem clearly (0,0) is one feasible solution, so I suspect you made a mistake somewhere along the way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 19th 2010, 02:06 AM
  2. greatest least bound and least upper bound proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 4th 2009, 05:44 PM
  3. Branch and Bound
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 2nd 2008, 11:31 PM
  4. Integer Programming - Branch-and-Bound
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 17th 2008, 06:35 AM
  5. least upper bound and greatest lower bound
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 22nd 2007, 10:59 AM

Search Tags


/mathhelpforum @mathhelpforum