Thread: 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

Originally Posted by Chidori

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

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)