# Reduced cost for edges in shortest path algorithm

 1 Hi everybody When using primal simplex algorithm to find shortest O-D path on an undirected graph (with non-negative costs) it is possible to extract the reduce cost of every node(source, sink and any intermediate node) in the course of algorithm. If for a given O-D, in addition to the original shortest path model constraints: Min $$\sum_{i,j} c_{ij}x_{ij}$$ s.t. $$\sum_j x_{oj} = 1$$ $$\sum_i x_{id} = 1$$ $$\sum_{i:\neq k} x_{ik} = \sum_{i\neq k} x_{ki}~~\forall k$$ we also have $$x_{ij} \leq 1$$ for some $$i,j$$ and $$x_{ij} \leq 0$$ for some other $$i,j$$ then is there any variant of shortest path algorithms, e.g. Dijkstra or simplex, primal dual etc, that also let us extract the reduced costs corresponding to edges? as the dual has multiple optimal solutions, what are the possibilities to chose solution which produce dual values both for edges and nodes? I appreciate any constructive comment regards, Shahin asked 05 Jan '13, 09:24 ShahinG 281●2●13 accept rate: 0% 2 I assume that last constraint should have the $$i$$ and $$k$$ indices reversed on one side or the other. Assuming nonnegativity also applies, the $$x_{ij} \leq 1$$ constraints are redundant and the $$x_{ij} \leq 0$$ constraints simply eliminate edges in the graph. Maybe you could clarify your question a bit? (05 Jan '13, 13:57) Matthew Salt... ♦ Thanks for your attention. Sorry, is it clear now? they are just flow conservation constraints in order to send one unit of flow from O to D passing through intermediate nodes $$k$$. Yes, that constraint is for eliminating the edge and the other one sounds redundant. Does it imply anything in dual sense? can't we expect still to have corresponding non-zero dual values? let 1->2->3->4 is the path and every link has cost of 1. We know that one solution to the dual is $$u_1=0, u_2=-1, u_3=-2, u_4=-3$$ and optimal dual solution -3 (dual be minimization problem). (05 Jan '13, 14:01) ShahinG Now, I need to re-distribute the dual values such that I also can obtain dual values for edge 2->3 and 3->4 and edge 1->4 which exists but is not in the optimal shortest path such that the optimal path does not change. (05 Jan '13, 14:44) ShahinG

 2 A basis for this problem consists of a spanning tree of edges in the graph, of which the edges in the shortest $$o$$-$$d$$ path will form a part. For all edges in the tree, the dual values satisfy $$u_i - u_j = c_{ij}$$. The reduced costs on the edges are then $$c_{ij} - u_i + u_j$$ and the tree you selected is optimal if those values all are nonnegative. Any selection of non-path edges that makes that relationship hold forms an optimal basis. I'm not sure there's an obvious geometric interpretation for the off-path duals and reduced costs in the single-path problem. A closely related problem (actually the one that I usually see discussed in textbooks) asks for the shortest paths from $$o$$ to all the other nodes. In that case, the basis is a tree of shortest $$o$$-$$j$$ paths. The duals are the negatives of the shortest $$o$$-$$j$$ distances and the reduced cost on an edge $$ij$$ is the differences in cost between getting from $$i$$ to $$j$$ via that edge and via the edges in the tree. answered 05 Jan '13, 15:43 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17% Thanks for the comment--very much appreciated. well, let's do it with a simple example $$n =4;\ c=[ [0, 1, 3, 1], [1, 0, 1, 5], [2, 1, 0, 1], [3, 2, 1, 0]];$$ Where we need to find a SP from 1 to 4. scenario 1) we add redundant edge constraints: edge1_2: x <= 1; edge1_4: x <= 1; edge2_3: x <= 1; edge3_4: x <= 1;  we get: // solution (optimal) with objective 3 x == 1; x == 1; x == 1; Dual value(source): 2 Dual value(sink): 2 Dual value(intermediate): -1 Dual value(intermediate): 1  (05 Jan '13, 16:52) ShahinG Dual value(edge1_2: x <= 1 ]): 0 Dual value(edge1_4: x <= 1 ]): 0 Dual value(edge2_3: x <= 1 ]): -1 Dual value(edge3_4: x <= 1 ]): 0 scenario 2) we remove them from the model // solution (optimal) with objective 3 x == 1; x == 1; x == 1; Dual value(source): 2 Dual value(sink): 1 Dual value(intermediate): -1 Dual value(intermediate): 0  The duals calculated by $$c_{ij} - u_i + u_j$$ does in the second scenario do not match with those of the first. in fact, the formulation $$c_{ij} - u_i + u_j$$ does not hold. did I miss anything? (05 Jan '13, 16:52) ShahinG Wait, why isn't the shortest 1-4 path just edge 14 with total cost 1? The duals have a degree of freedom (there are $$n$$ nodes but only $$n-1$$ edges in a spanning tree, so the convention is to set the source value at 0. Then the sink value is -1. If we add edges 12 and 13 to form the tree, node 2's dual is -1 and node 3's is -3. That doesn't happen to be optimal, but some other choice of the two additional edges is. (05 Jan '13, 18:51) Matthew Salt... ♦ sorry my mistake $$c=[ [0, 1, 3, 4], [1, 0, 1, 5], [2, 1, 0, 1], [3, 2, 1, 0]];$$ (05 Jan '13, 18:57) ShahinG So the tree consists of 12, 23, 34 and duals are 1: 0, 2: -1, 3: -2; 4: -3. I believe all reduced costs are nonnegative. That's without any of the redundant upper bound constraints. The upper bound constraints add variables to the dual and must be covered in the now larger basis by either the variable being bounded or the corresponding slack, whichever is positive. (05 Jan '13, 19:28) Matthew Salt... ♦ Th dual is the following and by setting those Minimize rhs: source + sink Subject To x(1)(2): source + intermediate(2) >= -1 x(1)(3): source + intermediate(3) >= -3 x(1)(4): source + sink >= -4 x(2)(1): - intermediate(2) >= -1 x(2)(3): - intermediate(2) + intermediate(3) >= -1 x(2)(4): sink - intermediate(2) >= -5 x(3)(1): - intermediate(3) >= -2 x(3)(2): intermediate(2) - intermediate(3) >= -1  (05 Jan '13, 19:46) ShahinG and  x(3)(4): sink - intermediate(3) >= -1 x(4)(1): >= -3 x(4)(2): intermediate(2) >= -2 x(4)(3): intermediate(3) >= -1 source = 0 intermediate(2) = -1 intermediate(3) = -2 sink = -3 Bounds source Free sink Free intermediate(2) Free intermediate(3) Free End  but this is infeasible due to constraint x(4)(3). (05 Jan '13, 19:46) ShahinG I have constraint x(4)(3) as $$c_{43} - u_4 + u_3 = 1 - (-3) + (-2) = 2 \geq 0$$. (05 Jan '13, 21:43) Matthew Salt... ♦ but the last model is infeasible! isn't it? x(4)(3): intermediate(3) >= -1 and intermediate(3) = -2 (06 Jan '13, 04:31) ShahinG The dual constraint for edge 43 is the one in the comment above. I don't see where you got your x(4)(3) constraint. (07 Jan '13, 22:49) Matthew Salt... ♦ showing 5 of 10 show 5 more comments
 0 The primal is: \ENCODING=ISO-8859-1 \Problem name: IloCplex $$Minimize obj: x(1)(2) + 3 x(1)(3) + 4 x(1)(4) + x(2)(1) + x(2)(3) + 5 x(2)(4)\  + 2 x(3)(1) + x(3)(2) + x(3)(4) + 3 x(4)(1) + 2 x(4)(2) + x(4)(3) + x13\  Subject To source: x(1)(2) + x(1)(3) + x(1)(4) = 1 sink: x(1)(4) + x(2)(4) + x(3)(4) = 1 intermediate(2): x(1)(2) - x(2)(1) - x(2)(3) - x(2)(4) + x(3)(2) + x(4)(2) = 0 intermediate(3): x(1)(3) + x(2)(3) - x(3)(1) - x(3)(2) - x(3)(4) + x(4)(3) = 0 Bounds x13 = 0 End$$ The optimal is // solution (optimal) with objective 3 x == 1; x == 1; x == 1; Dual value(source): 2 Dual value(sink): 1 Dual value(intermediate): -1 Dual value(intermediate): 0 dual is \ENCODING=ISO-8859-1 \Problem name: spp.dua Minimize rhs: source + sink Subject To x(1)(2): source + intermediate(2) >= -1 x(1)(3): source + intermediate(3) >= -3 x(1)(4): source + sink >= -4 x(2)(1): - intermediate(2) >= -1 x(2)(3): - intermediate(2) + intermediate(3) >= -1 x(2)(4): sink - intermediate(2) >= -5 x(3)(1): - intermediate(3) >= -2 x(3)(2): intermediate(2) - intermediate(3) >= -1 x(3)(4): sink - intermediate(3) >= -1 x(4)(1): >= -3 x(4)(2): intermediate(2) >= -2 x(4)(3): intermediate(3) >= -1 Bounds  source Free sink Free intermediate(2) Free intermediate(3) Free  End and the solution is Variable Name Solution Value source -2.000000 sink -1.000000 intermediate(2) 1.000000 All other variables in the range 1-4 are 0 CPLEX> disp sol dual Display dual values for which constraint(s): - Constraint Name Dual Price x(1)(2) 1.000000 x(2)(3) 1.000000 x(3)(4) 1.000000 if we set u_1 = source = 0 we get Dual simplex - Optimal: Objective = -2.0000000000e+000 Solution time = 0.00 sec. Iterations = 0 (0) Deterministic time = 0.01 ticks (10.23 ticks/sec) and Variable Name Solution Value sink -2.000000 intermediate(2) -1.000000 intermediate(3) -1.000000 All other variables in the range 1-4 are 0. CPLEX> disp sol dual - Constraint Name Dual Price x(3)(4) 1.000000 x(4)(3) 1.000000 c13 1.000000 So fixing to zero seems tricky answered 05 Jan '13, 19:18 ShahinG 281●2●13 accept rate: 0%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×3
×2
×1
×1