Explore BrainMass
Share

Branch and Bound Implicit Enumeration

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Use Implicit Enumeration to solve the following 0-1 IP.

MAX Z=3X1+X2+2X3-X4+X5
ST 2X1+X2-3X4<=1
X1+2X2-3X3-X4+2X5=>2
Xi=0 or 1

Please show enumeration tree. If a node is fathomed, indicate why it is fathomed. Provide the sequence of problems solved, eg. P1->P3->P4. Clearly indicate what the optimal solution is. Branch on x1 first.

I need to understand the process, so no LINGO solution or any other program please. Steps have to be done by hand.

© BrainMass Inc. brainmass.com December 20, 2018, 7:25 am ad1c9bdddf
https://brainmass.com/math/algebra/branch-bound-implicit-enumeration-408365

Solution Preview

MAX Z=3X1+X2+2X3-X4+X5
ST 2X1+X2-3X4<=1
X1+2X2-3X3-X4+2X5=>2
Xi=0 or 1
Branch on x1
P1: x1=1
P2:x1=0

At P1 x1=1,
The subproblem is
MAX Z=3+x2+2x3-x4+x5
s.t.
2+x2-3x4<=1
1+2x2-3x3-x4+2x5>=2

Or
MAX Z=3+x2+2x3-x4+x5
s.t.
x2-3x4<= -1
2x2-3x3-x4+2x5>=1
By looking at the first constraint, x4 has to be 1, otherwise x2<=-1 is invalid, since x2=1 or 0.
So x4=1
Therefore
X2-3<=-1
2x2-3x3-1+2x5>=1
Or
X2<=2
2x2-3x3+2x5>=2
The first constraint is redundant, since x2= 1 or 0, both satisfying x2<=2.
By looking at the second ...

Solution Summary

The solution to Branch and bound with details are provided. Implicit Enumeration to solve the problem is provided.

$2.19