CS 312 (W'07, T Th sections)

« So you'veSyllabus for all sect | Main | Homework 13 »

June 07, 2006

Homework 11

Consider the following reduced cost matrix M, in which M[a,b] = i means that the path from a to b has been excluded from
consideration (by setting its cost to infinity) with the given lower bound lb:
M =
0 4 6 0 i 2
i i i i i i
3 0 0 4 i 7
5 2 6 0 i 0
4 i 0 8 i 2
0 3 1 2 i 0
lb = 25
1. Suppose your algorithm includes the edge from city 5 to 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:
a. All edges that can now be excluded from consideration have had their cost replaced by i.
b. The resulting matrix has been reduced.
c. The new lower bound includes the impact of the reduction.
2. Take a look at the new reduced cost matrix. Which edge would you decide to include in a solution next? Justify your answer
(Note that I can think of 3 different ways to pick this edge and each of those picking methods have a good justification. And, there
might be more good methods that I haven't thought of)
-----------------------------------
On the third day we talk about edge selection algorithms and put the whole algorithm together. Putting the whole algorithm
together means generating nodes from other nodes, managing the priority queue, the structure of the search tree and the best
solution so far and deciding when to terminate the algorithms. You can structure the search tree two different ways. The structure
of the search tree influences the design of the edge picking algorithm. The first way is to pick an edge then generate children by
including that edge and by excluding that edge. For this tree structure, one might pick an edge by maximizing the difference
between the included edge child and the excluded edge child or one might pick the edge that maximizes the bound on the
exclude-edge child. In this tree formulation, one needs to be careful to not create a cycle prematurely (because the edges are
picked willy nilly).
The second way is to generate n children per node where each child is generated by including one of the edges that leave city i
where i is the depth of the tree. The nice thing about this formulation is that one does not create cycles prematurely but the
downside is that on many problems this problem formulation will result in excessively priority queues. The edge picking algorithm
for this formulation is quite simple: you just pick them all. Of course, bright students will say, well, why don't I just pick the best one
leaving city i instead of all of them? That's not a bad idea, but keep in mind that later on you might need to go back and pick a new
edge leaving city i so don't throw the parent node away quite yet.

Posted by tonglaga at June 7, 2006 04:18 PM

Comments

Post a comment