Branch and Bound
Assignment Problem
Assignment Problem
• Let there be N workers and N jobs.
• Any worker can be assigned to perform any job,
incurring some cost that may vary depending on
the work-job assignment.
• It is required to perform all jobs by assigning
exactly one worker to each job and exactly one
job to each agent in such a way that the total
cost of the assignment is minimized.
Example
Task 1 2 3
Agent
a 4 7 3
b 2 6 1
c 3 9 4
a 4 7 3
b 2 6 1
c 3 9 4
Example
Task 1 2 3 4
Agent
a 11 12 18 40
b 14 15 13 22
c 11 17 19 23
D 17 14 20 28
Upper Bound
• To obtain an upper bound on the answer
a1 Task 1 2 3 4
Agent
b2 a 11 12 18 40
c3
b 14 15 13 22
d4
c 11 17 19 23
D 17 14 20 28
is one possible solution whose cost
= 11+15+19+28
=73
Upper Bound
• Another possible solution is:
a4
b3 Task 1 2 3 4
Agent
c2
a 11 12 18 40
d1
b 14 15 13 22
c 11 17 19 23
is one possible solution whose cost D 17 14 20 28
=40+13+17+17
=87
In this case second solution is not improvement over the first.
Lower Bound
• To obtain a lower bound on the solution we can argue that whoever execute
task 1,cost will be at least 11.
• Whoever execute task 2, the cost will be at least 12 an so on.
• Thus adding the smallest element in each column give us lower bound on the
answer 11+12+13+22=58
• A second lower bound is obtained by adding the smallest element in each
row. 11+13+11+14=49
Not as useful as the previous lower bound.
• Pulling this facts together, we know that the answer to our instance lies
somewhere in [58……..73] Task 1 2 3 4
Agent
a 11 12 18 40
b 14 15 13 22
c 11 17 19 23
D 17 14 20 28
1. Compare and contrast Branch and Bound and Backtracking
Methods with suitable example. (Jan 2021) 7 Marks
2. Solve the following Task Assignment problem for
minimization using following cost matrix.(Cost matrix
represents cost of Task T performed by Person P.
T1 T2 T3
P1 10 20 25
P2 20 23 26
P3 12 16 25
Marks 04
• Explain Backtracking Method. What is N-
Queens Problem? Give solution of 4-Queens
Problem using Backtracking Method.
Marks 07 (Jan 2021 Marks 7)
Difference between
Backtracking and Branch and Bound
Backtracking Branch and Bound
1. It is used to find all possible 1. It is used to solve optimization
solutions to available problem. problem.
2. It traverse tree by DFS. 2. It may traverse a tree in any
manner, BFS or DFS
3. It realize that it has made a bad 3.It realize that it already has a
choice and undoes the last choice better optimal solution that the
by backing up. pre-solution leads to, so it
abandons(look after) that pre-
solution.
4. It searches the state space tree 4. It completely searches the state
until it found a solution. space tree to get optimal solution.
5. It involves feasibility function. 5. It involves bounding function.
