I'm studying the branch and bound method and how it is used in conjunction with a simplex tableau.
The issue I'm struggling with is how you incorporate the branches in your tableau to find out whether it's a feasible solution. For example consider this illustration (page 4) of the B&B method.
What's given is this:
max z = 4x1 − x2 restrictions 7x1 − 2x2 ≤ 14 0x1 + x2 ≤ 3 2x1 − 2x2 ≤ 3 xi ∈ Z+ 0, i = 1, 2
Which, using the simplex method, results in
z = 59/7 with
x = (20/7, 3).
Here we can see that
x1 is a fractional value so that's where we'll use the B&B method. Its value is
~2.86 which means we'll have to use
<= 2 and
>= 3. All of this is clear to me but then the illustration immediately jumps to the result of the simplex method.
What exactly happens when you "add the constraint to the tableau"? Do you keep the resulting tableau, add a column
x7, perform Gaussian Elimination until everything but one row is 0 and take the resulting value?