IP1: Branch and Bound Method
A company is assembling a team
to carry out a series of operations. There are four members of the
team: A, B, C and D, and four operations to be
carried out. Each team
member can carry out exactly one operation. All four operations must be
the overall project to succeed, however
the probability of a particular team member succeeding in a particular
as shown in the table below. For example, if
members were assigned to operations in the order ABCD, then the
probability of successful completion of the project is
(0.9)(0.6)(0.85)(0.7) = 0.3213.
If there is any
possible way that the team can be arranged such that the overall
probability of success exceeds 45%, then the manager will approve the
project. Will the manager approve the project? If yes, what is the
arrangement of the team that gives the highest probability of success?
formal branch and bound formulation for
this problem follows:
node in the branch and bound tree: a
person-operation assignment, full or partial.
selection policy: global best value of the
selection policy: choose the next operation in
natural order, 1 to 4.
function: for unassigned operations, choose the
best unassigned person (the one with the highest probability of
success) even if that person is chosen more than once.
Rule: when the incumbent solution objective
function value is better than or equal to the bounding
associated with all of the bud nodes.
when a bounding function gives a solution in
each operation is assigned to a different person.
The example below will
step through the branch and bound method in order to find a solution to
Press the Start button
twice to begin the example.