Discussion
Let C^(x) denote the ranking function that associates cost with a node in Branch and Bound Formulation of Travelling Salesperson Problem. What is the value of C^(x) for the root node for the following problem instance ?
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | ∞ | 3 | 5 | 10 |
| 2 | 11 | ∞ | 6 | 8 |
| 3 | 16 | 7 | ∞ | 20 |
| 4 | 13 | 12 | 10 | ∞ |
Answer: C
The root's cost is 31.
In the branch and bound TSP method, the root's lower bound is the total amount subtracted in reducing the cost matrix. Row minima: 3, 6, 7 and 10, total 26. After subtracting them the rows become (∞, 0, 2, 7), (5, ∞, 0, 2), (9, 0, ∞, 13) and (3, 2, 0, ∞).
Column minima of the reduced matrix: column 1 has 3, column 2 has 0, column 3 has 0 and column 4 has 2, total 5.
\[ \hat{C}(\text{root}) = 26 + 5 = 31 \]
26 is only the row reduction, without the column step. 29 and 36 come from arithmetic slips in the reductions.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development