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

cs-312:hw26 [2014/12/31 16:08] ringger created |
cs-312:hw26 [2014/12/31 16:23] (current) ringger |
||
---|---|---|---|

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</math> for a state, in which <math>M[i,j] = \infty</math> means that the path from <math>i</math> to <math>j</math> 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</math>. | + | * '''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. |