1. Find Solution of Travelling salesman problem using branch and bound method

Work\Job	1	2	3	4
1	x	4	9	5
2	6	x	4	8
3	9	4	x	9
4	5	8	9	x

Solution:
The number of rows = 4 and columns = 4

	`1`	`2`	`3`	`4`
`1`	M	4	9	5
`2`	6	M	4	8
`3`	9	4	M	9
`4`	5	8	9	M

The lower bound of total distance is
LB `=4+4+4+5=17`

So the tour has to travel at least `17`. Optimal solution will have to be more than or equal to the lower bound of `17`.

`:.` we create 3 more branches as `x_(1,2)=1,x_(1,3)=1,x_(1,4)=1` and `x_(1,1)=1` is a sub tour.

Branch-1 `->` For `x_(1,2)=1`, leave row `1` and column `2`

So we can't go `2->1`, so set it to M.

	`1`	`3`	`4`
`2`	M	4	8
`3`	9	M	9
`4`	5	9	M

`1` to `2` will be `4+4+9+5=22`

Branch-2 `->` For `x_(1,3)=1`, leave row `1` and column `3`

So we can't go `3->1`, so set it to M.

	`1`	`2`	`4`
`2`	6	M	8
`3`	M	4	9
`4`	5	8	M

`1` to `3` will be `9+6+4+5=24`

Branch-3 `->` For `x_(1,4)=1`, leave row `1` and column `4`

So we can't go `4->1`, so set it to M.

	`1`	`2`	`3`
`2`	6	M	4
`3`	9	4	M
`4`	M	8	9

`1` to `4` will be `5+4+4+8=21`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `21` is minimum, so we branch further from this node.

4. The branch and bound diagram

LB 17
`x_(1,2)=1`		`x_(1,3)=1`		`x_(1,4)=1`
22		24		21

---

`:.` we create 2 more branches as `x_(2,1)=1,x_(2,3)=1` and `x_(2,2)=1` is a sub tour.

Branch-1 `->` For `x_(2,1)=1`, leave row `2` and column `1`

Here till now we traversed `2->1->4`

So we can't go `4->2`, so set it to M.

	`2`	`3`
`3`	4	M
`4`	M	9

`2` to `1` will be `5+6+4+9=24`

Branch-2 `->` For `x_(2,3)=1`, leave row `2` and column `3`

So we can't go `3->2`, so set it to M.

	`1`	`2`
`3`	9	M
`4`	M	8

`2` to `3` will be `5+4+9+8=26`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram

LB 17
`x_(1,2)=1`		`x_(1,3)=1`		`x_(1,4)=1`
22		24		21
				`x_(2,1)=1`		`x_(2,3)=1`
				24		26

---

`:.` we create 2 more branches as `x_(2,3)=1,x_(2,4)=1` and `x_(2,1)=1` is a sub tour.

Branch-1 `->` For `x_(2,3)=1`, leave row `2` and column `3`

Here till now we traversed `1->2->3`

So we can't go `3->1`, so set it to M.

	`1`	`4`
`3`	M	9
`4`	5	M

`2` to `3` will be `4+4+9+5=22`

Branch-2 `->` For `x_(2,4)=1`, leave row `2` and column `4`

	`1`	`3`
`3`	9	M
`4`	5	9

`2` to `4` will be `4+8+9+5=26`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram

LB 17
`x_(1,2)=1`				`x_(1,3)=1`		`x_(1,4)=1`
22				24		21
`x_(2,3)=1`		`x_(2,4)=1`				`x_(2,1)=1`		`x_(2,3)=1`
22		26				24		26

---

`:.` we create 1 more branches as `x_(3,4)=1` and `x_(3,1)=1` is a sub tour.

Branch-1 `->` For `x_(3,4)=1`, leave row `3` and column `4`

	`1`
`4`	5

`3` to `4` will be `4+4+9+5=22`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram

LB 17
`x_(1,2)=1`				`x_(1,3)=1`		`x_(1,4)=1`
22				24		21
`x_(2,3)=1`		`x_(2,4)=1`				`x_(2,1)=1`		`x_(2,3)=1`
22		26				24		26
`x_(3,4)=1`
22

---

`:.` we create 1 more branches as `x_(4,1)=1`

`4` to `1` will be `4+4+9+5=22`

Answer :
The best optimal solution is `1to2,2to3,3to4,4to1`

The city path is `1->2->3->4->1`

which is 22

---

4. The branch and bound diagram

LB 17
`x_(1,2)=1`				`x_(1,3)=1`		`x_(1,4)=1`
22				24		21
`x_(2,3)=1`		`x_(2,4)=1`				`x_(2,1)=1`		`x_(2,3)=1`
22		26				24		26
`x_(3,4)=1`
22
`x_(4,1)=1`
22

---

---