Linear Programming Formulation
There is a natural linear programming formulation for the shortest path problem, given below. It is very trivial compared to most other uses of linear programs in discrete optimization, however it illustrates connections to other concepts.
Given a directed graph (V, A) with source node s, target node t, and cost wij for each arc (i, j) in A, consider the program with variables xij
- minimize subject to and for all i,
This LP, which is common fodder for operations research courses, has the special property that it is integral; more specifically, every basic optimal solution (when one exists) has all variables equal to 0 or 1, and the set of edges whose variables equal 1 form an s-t dipath. See Ahuja et al. for one proof, although the origin of this approach dates back to mid-20th century.
The dual for this linear program is
- maximize yt − ys subject to for all ij, yj − yi ≤ wij
and feasible duals correspond to the concept of a consistent heuristic for the A* algorithm for shortest paths. For any feasible dual y the reduced costs are nonnegative and A* essentially runs Dijkstra's algorithm on these reduced costs.
Read more about this topic: Shortest Path Problem
Famous quotes containing the words programming and/or formulation:
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)
“Art is an experience, not the formulation of a problem.”
—Lindsay Anderson (b. 1923)