Question 9
TSP Distance matrix for 6 cities (A to F) and sorted segments are provided in the figure. For each city the distances to other cities are listed in ascending order. For example, Column 1 shows the distance from A to D as 14, A to B as 26 and so on.
Note 1: A segment is a two-way edge between a pair of cities. Note 2: In TSP BnB, after adding or dropping a permanent-segment, first, infer new (included/excluded) permanent-segments, then compute the lower bound. Use the above information to answer the sub-questions.
According to the TSP BnB algorithm covered in the lecture, select the first segment XY to refine the root node S0, then compute the lower bound cost of the node (S0, ~XY) that permanently excludes XY. Enter the lower bound cost in the textbox. Enter a natural number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42