Week 7 - Critical path analysis, Markov chains (intro)

Question 1

Critical path

Answer 1

An s–t path in which lengthening any arc (activity duration) by any amount would delay the project completion time

Question 2

How to decide if there is more than one critical path in a network and, if so, exhibit a second one?
For a given activity, can you decide if there is any critical path containing this particular activity?

[Exercise 11.3]

Answer 2

1. Find all CRITICAL ACTIVITIES (those with FLOAT 0); discard all other nodes
2. From this smaller network, retain only the TIGHT arcs, discarding the others.
3. Every s–t path in what remains is critical, by construction, and this is the simplest description of the set of all s–t paths in the original network.
4. There is a unique critical path (in the original network) iff the reduced network is simply a PATH.

Question 3

Explain how a problem can be formulated as LONGEST PATH PROBLEM.
What algorithm would you suggest to find an optimal solution efficiently?

[Exercise 11.4, 2016 exam Q]

Answer 3

1. Create a NETWORK by creating a NODE for every bid, an arc (u,v) between two bids u and v if u finishes before v starts (possibly on the same day),
   - and two extra nodes s and t with an arc from s to every bid and an arc from every bid to t.
2. Give each (s, u) arc length 0, and give every other arc (u, v) or (u, t) length equal to its bid amount.
3. The value of a bid set = the LENGTH of the CORRESPONDING PATH.
   - Thus, a maximum-revenue set of bids corresponds to a longest path.
4. Use the critical path algorithm (CPA) to find the longest path.
5. We rely on the fact that the network has NO CYCLE, and therefore has a TOPOLOGICAL ORDER.
   - This is so because in every arc (u, v), the starting day of rental v must be strictly after that of u; in this sense time goes strictly forward as we follow a path, and we cannot possibly return to the same vertex.

Question 4

Topological order

Answer 4

An ordering of the vertices where, for every arc (u, v), u precedes v in the order

Question 5

Formula to calculate total float

Answer 5

Float = q(u) - p(u)
where p(u) = earliest possible starting time
and q(u) = latest possible starting time

Question 6

4 differences between Dijkstra’s algorithm & CPA algorithm

Answer 6

Djikstra’s algorithm
1. shortest paths
2 arbitrary directed graphs
3. NONNEGATIVE COSTS
4. order of vertices determined during algorithm & depends on the COSTS

CPA
1. longest paths
2. directed graphs with restricted ACYCLIC STRUCTURE
3. arbitrary costs
4. uses FIXED TOPOLOGICAL ORDER, independent of the costs