Hi everybody When using primal simplex algorithm to find shortest OD path on an undirected graph (with nonnegative 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 OD, 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 
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 nonpath edges that makes that relationship hold forms an optimal basis. I'm not sure there's an obvious geometric interpretation for the offpath duals and reduced costs in the singlepath 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... ♦ Thanks for the commentvery 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:
we get: // solution (optimal) with objective 3
(05 Jan '13, 16:52)
ShahinG
Dual value(edge1_2: x[1][2] <= 1 ]): 0 Dual value(edge1_4: x[1][4] <= 1 ]): 0 Dual value(edge2_3: x[2][3] <= 1 ]): 1 Dual value(edge3_4: x[3][4] <= 1 ]): 0 scenario 2) we remove them from the model // solution (optimal) with objective 3
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 14 path just edge 14 with total cost 1? The duals have a degree of freedom (there are \(n\) nodes but only \(n1\) 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
(05 Jan '13, 19:46)
ShahinG
and
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

The primal is: \ENCODING=ISO88591 \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)\
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][2] == 1; x[2][3] == 1; x[3][4] == 1; Dual value(source): 2 Dual value(sink): 1 Dual value(intermediate[2]): 1 Dual value(intermediate[3]): 0 dual is \ENCODING=ISO88591 \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
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 14 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 14 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 
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?
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 nonzero 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).
Now, I need to redistribute 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.