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's gravatar image

ShahinG
281213
accept rate: 0%

edited 05 Jan '13, 14:00

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

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.

link

answered 05 Jan '13, 15:43

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
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][2] <= 1;
edge1_4: x[1][4] <= 1;
edge2_3: x[2][3] <= 1;
edge3_4: x[3][4] <= 1;

we get: // solution (optimal) with objective 3

x[1][2] == 1;
x[2][3] == 1;
x[3][4] == 1;
Dual value(source): 2
Dual value(sink): 2
Dual value(intermediate[2]): -1
Dual value(intermediate[3]): 1
(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

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

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

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][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=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

link

answered 05 Jan '13, 19:18

ShahinG's gravatar image

ShahinG
281213
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 05 Jan '13, 09:24

Seen: 1,207 times

Last updated: 07 Jan '13, 22:49

OR-Exchange! Your site for questions, answers, and announcements about operations research.