1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.