Shortest Path Problem - Linear Programming Formulation

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 ytys subject to for all ij, yjyiwij

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)

    You do not mean by mystery what a Catholic does. You mean an interesting uncertainty: the uncertainty ceasing interest ceases also.... But a Catholic by mystery means an incomprehensible certainty: without certainty, without formulation there is no interest;... the clearer the formulation the greater the interest.
    Gerard Manley Hopkins (1844–1889)