Algorithm

Travelling salesman problem using branch and bound (penalty) method Steps (Rule)
Step-1:	Find out the each row minimum element and subtract it from that row. Also add each row minimum element is called row minimum.
Step-2:	Find out the each column minimum element and subtract it from that column. Also add each column minimum element is called column minimum.
Step-3:	lower bound = row minimum + column minimum
Step-4:	Calculate the penalty of all 0's penalty (of each 0) = minimum element of that row + minimum element of that column.
Step-5:	Find maximum penalty from all this penalties. And the new branch will be start from this location. If there are more than 1 such location then choose any one arbitrarily.
Step-6:	Let branch will occur at `X_(A,D)`. There are two branches. 1. If `X_(A,D)=0`, then we have an additional cost of say t and the lower bound becomes LB + t 2. If `X_(A,D)=1`, then we can go `A->D` So we can't go `D->A`, so set it to M. Now we leave row A and column D. Again repeat the steps from step-1 using this reduced matrix, until whole path is found.
Step-7:	So finally we get total distance and final path.

---

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

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

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

	`1`	`2`	`3`	`4`
`1`	M	0	5	1	(-4)
`2`	2	M	0	4	(-4)
`3`	5	0	M	5	(-4)
`4`	0	3	4	M	(-5)

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

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

	`1`	`2`	`3`	`4`
`1`	M	0	5	0
`2`	2	M	0	3
`3`	5	0	M	4
`4`	0	3	4	M
	(-0)	(-0)	(-0)	(-1)

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

we get the lower bound = `17+1=18`

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

	`1`	`2`	`3`	`4`
`1`	`M`	`0^(color{red}{(0)})`	`5`	`0^(color{red}{(3)})`
`2`	`2`	`M`	`0^(color{red}{(6)})`	`3`
`3`	`5`	`0^(color{red}{(4)})`	`M`	`4`
`4`	`0^(color{red}{(5)})`	`3`	`4`	`M`

Here maximum penalty is 6, occur at `X_(2,3)` , so we choose `X_(2,3)` to begin branch

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

2. If `X_(2,3)=1`,

we can go `2->3`

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

Now we leave row `2` and column `3`, so reduced matrix is

	`1`	`2`	`4`
`1`	M	0	0
`3`	5	M	4
`4`	0	3	M

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

	`1`	`2`	`4`
`1`	M	0	0	(-0)
`3`	1	M	0	(-4)
`4`	0	3	M	(-0)

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

we get the lower bound = `18+4+0=22`

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

	`1`	`2`	`4`
`1`	`M`	`0^(color{red}{(3)})`	`0^(color{red}{(0)})`
`3`	`1`	`M`	`0^(color{red}{(1)})`
`4`	`0^(color{red}{(4)})`	`3`	`M`

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

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

2. If `X_(4,1)=1`,

we can go `4->1`

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

Now we leave row `4` and column `1`, so reduced matrix is

	`2`	`4`
`1`	0	M
`3`	M	0

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

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

	`2`	`4`
`1`	`0^(color{red}{(0)})`	`M`
`3`	`M`	`0^(color{red}{(0)})`

we can go `1->2`

and `3->4`

So our final path is `2->3->4->1->2`

and total distance is `4+9+5+4=22`

---

---