##### Differences

This shows you the differences between two versions of the page.

 cs-312:hw26 [2014/12/31 23:08]ringger created cs-312:hw26 [2014/12/31 23:23] (current)ringger 2014/12/31 23:23 ringger 2014/12/31 23:08 ringger created 2014/12/31 23:23 ringger 2014/12/31 23:08 ringger created Line 4: Line 4: Show all work neatly. Show all work neatly. - The setting is B&B for TSP.  Consider the following reduced cost matrix ​<​math>​M ​for a state, in which <​math>​M[i,j] = \infty ​means that the path from <​math>​i ​to <​math>​j ​has been excluded from consideration (by setting its cost to infinity), with the lower bound lb=25. ​ Note that the edge (2,5) has already been included for the partial tour represented by this state. + The setting is B&B for TSP.  Consider the following reduced cost matrix ​$M$ for a state, in which $M[i,j] = \infty$ means that the path from $i$ to $j$ has been excluded from consideration (by setting its cost to infinity), with the lower bound lb=25. ​ Note that the edge (2,5) has already been included for the partial tour represented by this state.  Line 19: Line 19: ===Question 1=== ===Question 1=== Suppose your algorithm includes the edge from city 5 to city 3 next (this edge has cost 0 relative to the current lower bound lb=25). ​ Give a new reduced cost matrix and new lower bound that have the following properties: Suppose your algorithm includes the edge from city 5 to city 3 next (this edge has cost 0 relative to the current lower bound lb=25). ​ Give a new reduced cost matrix and new lower bound that have the following properties: - * '''​All'''​ edges that can now be excluded from consideration,​ even on feasibility grounds, have had their entry in the matrix replaced with <​math>​\infty​. + * '''​All'''​ edges that can now be excluded from consideration,​ even on feasibility grounds, have had their entry in the matrix replaced with $\infty$. * The resulting matrix has been reduced. * The resulting matrix has been reduced. * The new lower bound includes the impact of the reduction. ​ * The new lower bound includes the impact of the reduction. ​