Example
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
carried out
successfully for
the overall project to succeed, however
the probability of a particular team member succeeding in a particular
operation varies,
as shown in the table below. For example, if
the team
members were assigned to operations in the order ABCD, then the
overall
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?
The
formal branch and bound formulation for
this problem follows: