Let us be given a network without capacities (V, E, s, t), where (V, E) is...

 

Transcribed Image Text:

Let us be given a network without capacities (V, E, s, t), where (V, E) is a directed graph, with a source s € V (unique node with no incoming arcs) and a sink te V (unique node with no outcoming arcs). Suppose that CE R is a vector of nonnegative costs of the arcs in the network (where n is the number arcs). Dijkstra's algorithm finds a shortest st path in such network, that is, a directed st path with smallest total cost (computed as the sum of the costs of all arcs). We will first study a specialisation of the primal-dual algorithm, which is strongly related to Dijkstra's algorithm. It is known [1, Section 5.4] that to solve the problem of finding such shortest path one can write out the following linear programming problem: min c f s.t. Af + d=0, f≥ 0, where fR is the flow through the network, c ER is the vector of costs of all arcs, A is the node-arc incidence matrix, and d E R" is the vector whose coordinates are defined by di = -1, 1, 0, if i= s, if it, otherwise, (1) where m is the number of nodes. Solve the following problems: Problem 1. Formulate the dual to (1) and explain why the condition Tt = 0 can be added to the constraints. Problem 2. Assuming that a dual feasible solution with t=0 is known, consider an application of the primal-dual algorithm to (1). Which equation of the system Af + d = 0 can be excluded from the system to make the primal-dual algorithm applicable (with all other equations remaining unchanged), and why can it be excluded? Given a dual feasible, which arcs (i, j), for i, je V, correspond to the admissible columns? Formulate the restricted primal problem (RP) for (1) with one equation excluded (which you specified before), and the dual to that restricted primal problem (DRP). Let us be given a network without capacities (V, E, s, t), where (V, E) is a directed graph, with a source s € V (unique node with no incoming arcs) and a sink te V (unique node with no outcoming arcs). Suppose that CE R is a vector of nonnegative costs of the arcs in the network (where n is the number arcs). Dijkstra's algorithm finds a shortest st path in such network, that is, a directed st path with smallest total cost (computed as the sum of the costs of all arcs). We will first study a specialisation of the primal-dual algorithm, which is strongly related to Dijkstra's algorithm. It is known [1, Section 5.4] that to solve the problem of finding such shortest path one can write out the following linear programming problem: min c f s.t. Af + d=0, f≥ 0, where fR is the flow through the network, c ER is the vector of costs of all arcs, A is the node-arc incidence matrix, and d E R" is the vector whose coordinates are defined by di = -1, 1, 0, if i= s, if it, otherwise, (1) where m is the number of nodes. Solve the following problems: Problem 1. Formulate the dual to (1) and explain why the condition Tt = 0 can be added to the constraints. Problem 2. Assuming that a dual feasible solution with t=0 is known, consider an application of the primal-dual algorithm to (1). Which equation of the system Af + d = 0 can be excluded from the system to make the primal-dual algorithm applicable (with all other equations remaining unchanged), and why can it be excluded? Given a dual feasible, which arcs (i, j), for i, je V, correspond to the admissible columns? Formulate the restricted primal problem (RP) for (1) with one equation excluded (which you specified before), and the dual to that restricted primal problem (DRP).

Answer rating: 100% (QA)

Primed min of Af D f20 dual mon Ts 1 Afta j Fjcij for all Pj EE t0 Ti is unrestricted R... View the full answer