Remark: the Equipment Replacement Example Was Difficult for People to Process

OR 215 Spring 1999

Network Flows M. Hartmann

introduction to shortest paths

Different types of shortest path problems

Assumptions

Applications of shortest path problems

Optimality of spanning tree solutions

Finding shortest paths in acyclic networks

The “string” model for solving shortest path problems

different types of shortest path problems

1.  Differentiated by the number of origin nodes and the number of destination nodes. (We will focus on finding the shortest paths from one source node to all other nodes in the network.)

2.  Differentiated by properties of the arc lengths. In particular, must the arc lengths be non-negative, or are they allowed to be negative?

3.  Differentiated by the network topology. For example, is the network planar? Is the network acyclic?

assumptions

1. Integer data

2. Directed network

3. There is a path from s to all other nodes.

4. There is no negative length directed cycle.

The label correcting algorithm, which we will study, either

i.  Finds a shortest path from the source node to all other nodes, or

ii.  Identifies a negative (length) cycle.

Application: maximizing rent revenue

John owns a vacation home that he wishes to rent out for the entire year. He has solicited a number of bids, each of which has the following form:

·  Day rental starts (rental days start at 3 PM)

·  Day rental ends (check out time is noon)

·  Bid in $’s

What selection of bids should John select so as to maximize his total revenue?

Dates in January

Idea: Construct a formulation in which the days are nodes and the bids are arcs. (Not renting the condo for one day is equivalent to a bid of $0 for one day.)

PROJECT NETWORKS

A construction project is composed of several tasks i=1,…,n. The goal is to complete all tasks as soon as possible. Some tasks must be carried out before others. ( i < j means that task i must precede task j ). The dura- tion of task i is di. What is the earliest completion time?

Idea: construct a formulation in which the tasks are nodes and the precedence relation determines the arcs.

equipment replacement

An industrial machine in a manufacturing organi-zation must be replaced periodically. This machine is expensive and requires substantial capital investment.

As the machine is used over the years, it breaks down more frequently and hence it gets more expensive to operate. Furthermore, as its age increases, its salvage value goes down. The equipment replacement problem attempts to obtain a replacement plan that minimizes the total cost of buying, selling and operating the equipment over a planning horizon of T periods (years).

cij = cost of buying a machine at the beginning of

period i, operating it over periods i,i+1,..., j -1 minus

the salvage value at the beginning of period j

Note: This setup is similar to maximizing rent revenue.

lotsizing problem

There is a demand dj for goods in each of the periods j = 1,2,…,T. In period j, we can produce at level xj and/or we can meet the demand by drawing upon the inventory Ij-1 from the previous period.

·  Cost of inventory: hj-1Ij-1

·  Cost of production: pjxj + Sj if xj > 0 (fixed charge)

cij = cost of production and inventory to satisfy demand

in periods i+1,..., j by production in period i+1

Properties of optimal solutions

Property 4.1. If the path s = i1,i2,...,ih = k is a shortest path from node s to node k, then the subpath s = i1,i2,...,il is a shortest path from s to node il for every l = 2,3,...,h-1.

Property 4.2. Let the vector d represent the shortest path distances from the source node. Then a directed path P from source to node k is a shortest path if and only if d(j) = d(i) + cij for every arc (i,j) Î P.

Proof: By induction on the number of arcs in P.

·  Call an arc “eligible” if d(j) = d(i) + cij.

Remark: We may find the shortest paths from node 1 to all other nodes by performing a breadth first search on eligible arcs (assuming we know the shortest path distances). Hence there must be a tree of shortest paths.

SHORTEST PATHS IN AN ACYCLIC NETWORK

(or longest paths)

Preprocessing Step: Label the nodes 1,…,n so that i < j for all (i,j) Î A .

Such a labeling is called a topological sort of the nodes.

The Algorithm

begin

d(1) := 0;

pred(1) := Æ;

d(j) = ¥ for j = 2 to n;

for i = 1 to n do

for each j Î A(i) if d(j) > d(i) + cij then

begin

d(j) := d(i) + cij;

pred(j) := i;

end;

end

1 2 3 4 5 6 7 8

CORRECTNESS

Theorem. The algorithm correctly determines the shortest paths from node 1 to all other nodes in an acyclic network.

Proof: We can show by induction that d(j) is always the length of some path from 1 to j; hence d(j) is an upper bound on the length of the shortest path from 1 to j.

Claim: By the time that A(j) is inspected, the label d(j) is the length of shortest path from node 1 to node j.

Proof of Claim: Consider a proof by induction on j:

shortest path from node 1 to node j

STREET SWEEPING PROBLEM

A street sweeper is faced with an undirected network of streets to sweep. What route should he/she follow so that the total time spent deadheading (driving with out sweeping) is as small as possible?

First of all, is it possible to find a route with no dead-heading (an Euler tour)?

Konigsberg Bridge Problem

Theorem. A graph contains a closed walk that visits each arc exactly once if and only if every node in the graph has an even degree.

There is no Euler tour in this graph, so which arcs should be repeated (to minimize deadheading)?

Claim. The repeated arcs form a collection of arc- disjoint paths between nodes of odd degree.

Before matching up the nodes of odd degree, we must solve an all-pairs shortest paths problem.

the string solution

Consider the shortest paths problem on an undirected graph with non-negative costs, physically represented by:

·  Nodes: Small yet surprisingly heavy rings, labeled 1 to n.

·  Arcs: For each arc (i,j) connect ring i to ring j with a string of length cij.

Algorithm. To find the shortest path from node 1 to all other nodes: hold ring 1, and let the other rings fall under the force of gravity.

Remark. Let d(k) denote the distance that ring k falls.

Then d(k) is the maximum possible distance subject to the constraints that d(j) £ d(i) + cij for all i and j.

(Thus we solve the shortest path problem by solving a related maximization problem.)