Find Solution of Travelling salesman problem using branch and bound (penalty) method (MIN case)

Work\Job	A	B	C	D	E
A	x	5	8	4	5
B	5	x	7	4	5
C	8	7	x	8	6
D	4	4	8	x	8
E	5	5	6	8	x

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

	`A`	`B`	`C`	`D`	`E`
`A`	M	5	8	4	5
`B`	5	M	7	4	5
`C`	8	7	M	8	6
`D`	4	4	8	M	8
`E`	5	5	6	8	M

We know that the sum of row minimum gives us the lower bound.
Step-1: Find out the each row minimum element and subtract it from that row

	`A`	`B`	`C`	`D`	`E`
`A`	M	1	4	0	1	(-4)
`B`	1	M	3	0	1	(-4)
`C`	2	1	M	2	0	(-6)
`D`	0	0	4	M	4	(-4)
`E`	0	0	1	3	M	(-5)

So, row minimum will be `23`. (`4+4+6+4+5=23`)

Step-2: Find out the each column minimum element and subtract it from that column.

	`A`	`B`	`C`	`D`	`E`
`A`	M	1	3	0	1
`B`	1	M	2	0	1
`C`	2	1	M	2	0
`D`	0	0	3	M	4
`E`	0	0	0	3	M
	(-0)	(-0)	(-1)	(-0)	(-0)

So, column minimum will be `1`. (`0+0+1+0+0=1`)

we get the lower bound = `23+1=24`

Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`A`	`B`	`C`	`D`	`E`
`A`	`M`	`1`	`3`	`0^(color{red}{(1)})`	`1`
`B`	`1`	`M`	`2`	`0^(color{red}{(1)})`	`1`
`C`	`2`	`1`	`M`	`2`	`0^(color{red}{(2)})`
`D`	`0^(color{red}{(0)})`	`0^(color{red}{(0)})`	`3`	`M`	`4`
`E`	`0^(color{red}{(0)})`	`0^(color{red}{(0)})`	`0^(color{red}{(2)})`	`3`	`M`

Here maximum penalty is 2, occur at `X_(C,E)` or `X_(E,C)` , so we choose `X_(E,C)` to begin branch

There are two branches.
1. If `X_(E,C)=0`, then we have an additional cost of `2` and the lower bound becomes `24+2=26`

2. If `X_(E,C)=1`,

we can go `E->C`

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

Now we leave row `E` and column `C`, so reduced matrix is

	`A`	`B`	`D`	`E`
`A`	M	1	0	1
`B`	1	M	0	1
`C`	2	1	2	M
`D`	0	0	M	4

Step-1: Find out the each row minimum element and subtract it from that row

	`A`	`B`	`D`	`E`
`A`	M	1	0	1	(-0)
`B`	1	M	0	1	(-0)
`C`	1	0	1	M	(-1)
`D`	0	0	M	4	(-0)

So, row minimum will be `1`. (`0+0+1+0=1`)

Step-2: Find out the each column minimum element and subtract it from that column.

	`A`	`B`	`D`	`E`
`A`	M	1	0	0
`B`	1	M	0	0
`C`	1	0	1	M
`D`	0	0	M	3
	(-0)	(-0)	(-0)	(-1)

So, column minimum will be `1`. (`0+0+0+1=1`)

we get the lower bound = `24+1+1=26`

Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`A`	`B`	`D`	`E`
`A`	`M`	`1`	`0^(color{red}{(0)})`	`0^(color{red}{(0)})`
`B`	`1`	`M`	`0^(color{red}{(0)})`	`0^(color{red}{(0)})`
`C`	`1`	`0^(color{red}{(1)})`	`1`	`M`
`D`	`0^(color{red}{(1)})`	`0^(color{red}{(0)})`	`M`	`3`

Here maximum penalty is 1, occur at `X_(C,B)` or `X_(D,A)` , so we choose `X_(C,B)` to begin branch

There are two branches.
1. If `X_(C,B)=0`, then we have an additional cost of `1` and the lower bound becomes `26+1=27`

2. If `X_(C,B)=1`,

we can go `C->B`

Here till now we traversed `E->C->B`

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

Now we leave row `C` and column `B`, so reduced matrix is

	`A`	`D`	`E`
`A`	M	0	0
`B`	1	0	M
`D`	0	M	3

Here we have 0 in every row and column. So, the lower bound remains the same i.e, `26+0=26`

Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`A`	`D`	`E`
`A`	`M`	`0^(color{red}{(0)})`	`0^(color{red}{(3)})`
`B`	`1`	`0^(color{red}{(1)})`	`M`
`D`	`0^(color{red}{(4)})`	`M`	`3`

Here maximum penalty is 4, occur at `X_(D,A)` , so we choose `X_(D,A)` to begin branch

There are two branches.
1. If `X_(D,A)=0`, then we have an additional cost of `4` and the lower bound becomes `26+4=30`

2. If `X_(D,A)=1`,

we can go `D->A`

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

Now we leave row `D` and column `A`, so reduced matrix is

	`D`	`E`
`A`	M	0
`B`	0	M

Here we have 0 in every row and column. So, the lower bound remains the same i.e, `26+0=26`

Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`D`	`E`
`A`	`M`	`0^(color{red}{(0)})`
`B`	`0^(color{red}{(0)})`	`M`

we can go `A->E`

and `B->D`

So our final path is `E->C->B->D->A->E`

and total distance is `6+7+4+4+5=26`

---