Bah, yeah, I screwed this up. It's the dual optimal solution that's the shortest path. I will fix it later. Like I said, encoding functions as optimization can be super confusing.
Thanks so much, enjoying the blogs as usual. Just for clarification, Is this correct about obtaining soln. from the dual solution? - The shortest path from A to B is determined by the Lagrange multipliers in the Lagrangian function. There is one multiplier for each inequality constraint. The inequalities which are satisfied by the optimal solution (leading to shortest path when traced from A to B) are marked with a non-zero value in the Lagrange multiplier vector. Hence by simply checking the zeros and non-zeros in the Lagrange multiplier vector, we get the info. Whether that link/branch lies on the shortest path or not.
"The nonzero indices in this vector correspond to endpoints in the shortest path."
I'm not sure this is true?
Suppose we have four nodes (labeled 1, 2, 3, 4) and four edges arranged in a diamond, so that the edges are
1 <=> 2, length 1
2 <=> 4, length 1
1 <=> 3, length 1
3 <=> 4, length 2.
We want to go from 1 to 4, and the shortest path is clearly 1 => 2 => 4, with length 2.
I think a valid solution for x is
x1 = 0
x2 = 1
x3 = 1
x4 = 2
But node 3 is not on the shortest path, even though x3 > 0. In fact, I don't see any way to set x3 = 0 without violating a constraint.
Bah, yeah, I screwed this up. It's the dual optimal solution that's the shortest path. I will fix it later. Like I said, encoding functions as optimization can be super confusing.
Thanks so much, enjoying the blogs as usual. Just for clarification, Is this correct about obtaining soln. from the dual solution? - The shortest path from A to B is determined by the Lagrange multipliers in the Lagrangian function. There is one multiplier for each inequality constraint. The inequalities which are satisfied by the optimal solution (leading to shortest path when traced from A to B) are marked with a non-zero value in the Lagrange multiplier vector. Hence by simply checking the zeros and non-zeros in the Lagrange multiplier vector, we get the info. Whether that link/branch lies on the shortest path or not.