Results 1 to 3 of 3

Math Help - Integer Programming - Branch-and-Bound

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    2

    Integer Programming - Branch-and-Bound

    Hi, I am not sure if I am asking in the right section.
    Anyway, for the following:

    max f = 7x + 4z + 4
    s.t. 3x + 2z < 2
    0 < x,z < 1

    I have to solve by inspection by considering the ratio of the coefficients of the variables in objective function and constraint.
    For x it is 7/3 and for z it is 2. Apparently I am supposed to choose x as large as possible so therefore x = 2/3
    I would like to know how this is obtained.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Chidori View Post
    Hi, I am not sure if I am asking in the right section.
    Anyway, for the following:

    max f = 7x + 4z + 4
    s.t. 3x + 2z < 2
    0 < x,z < 1

    I have to solve by inspection by considering the ratio of the coefficients of the variables in objective function and constraint.
    For x it is 7/3 and for z it is 2. Apparently I am supposed to choose x as large as possible so therefore x = 2/3
    I would like to know how this is obtained.

    Thanks
    The subject line says Integer Programming. If that is what is meant then x=2/3 is inadmissible. With the strict inequalities that you have there are no admissible solutions (there are no integers z that satisfy 0<z<1).

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    2
    It should be correct as this was a worked example in my lecture notes. I should probably show the IP:

    max f = 7x + 4y +4z

    s.t. 3x + 2y +2z < 4

    0 < x,y,z < 1

    The solution to the LP-relaxation is x=1, y=1/2, z=0 with max value of f=9=UB

    The step after this is to branch on y=1/2 and the LP is as shown in my previous post.

    If it really is inadmissible in this case, I would like to know in other similar problems, in general, how the largest value is obtained from using the ratio of coefficients of the variables when solving by inspection.

    Edit: Note that the inequalities are meant to be greater/less than or equal to (I don't know how to insert the proper mathematical terms on here)
    Last edited by Chidori; May 17th 2008 at 05:33 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Integer Programming Problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: April 26th 2010, 08:22 PM
  2. Integer Programming
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: March 10th 2010, 07:56 PM
  3. branch-and-bound tree for solving IPs
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: April 26th 2009, 06:36 AM
  4. Branch and Bound
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 2nd 2008, 11:31 PM
  5. Integer programming
    Posted in the Business Math Forum
    Replies: 0
    Last Post: April 28th 2008, 07:18 PM

Search Tags


/mathhelpforum @mathhelpforum