MP4F05 OPERATIONS RESEARCH NETWORK OPTIMIZATION MODELS WEEK 6
Dr. Dr Mao Jianfeng Assistant Professor, MAE Office: N3.2-02-32 Email: jfmao@ntu edu sg [email protected] Tel: 6790 5522
Consultation Hour p , y 5~6pm, Tuesday
Network Optimization Models Main Topics
Shortest Path Problem Minimum Spanning Tree Problem Maximum Flow Problem
Jianfeng Mao
1 of 45
Network Optimization Models
Network optimization models exhibit a very special structure. Networks and graphs are powerful modeling tools. For special cases, the special structure can dramatically reduce computational complexity. complexity Network optimization models addresses huge number of diverse application. They were the first widespread application of LP to problem of industrial logistics.
Jianfeng Mao 2 of 45
Network Optimization Models
Physical Networks
Road Networks Railway Networks Airline Traffic Networks Power Grid Networks Cyber Networks y Oil & Gas Pipeline Networks
Abstract Networks
Organizational charts Human relationship charts (match-making as an example)
Jianfeng Mao 3 of 45
An Example of Network Optimization Model
For further details on, say, the Concorde TSP code, visit http://www.tsp.gatech.edu/sweden/index.html Jianfeng Mao 4 of 45
An Example of Network Optimization Model
Someone wants to tour the 24978 Cities in Sweden The Travelling Salesman Problem (TSP) asks for the cheapest possible tour through a given collection of cities SP
Network representation Tour finding - a popular topic Hard Problem to solve
Jianfeng Mao
5 of 45
An Example of Network Optimization Model
The TSP was solved in March 2004. The optimal tour has a length of approximately 72500 kilometers. The cumulative CPU time used in network optimization procedures was approximately 84.8 CPU years on a single Intel Xeon 2.8 GHz processor.
Jianfeng Mao
6 of 45
Directed and Undirected Networks
1 2 1 2
An Undirected Graph
An Directed Graph
Networks to transport commodities
Physical goods Communications Electricity
The field of Network Optimization is concerned with optimization problems on network.
Jianfeng Mao
7 of 45
Network Definitions
Path: Example: 5,2,3,4 No node is repeated Directions are ignored Directed Path: 1,2,5,3,4 No d is N node i repeated t d Directions are important Cycle: 1 2 3 1 1,2,3,1 A path with 2 or more nodes, except that the first node is the last node. Directions are i Di ti ignored d Directed Cyle: 1,2,3,4,1 No node is repeated, except that the first node is the last node Directions are important
5 1 2 5 1 2 2 1 4 2 1 4 3 3 3 4 3 4
Jianfeng Mao
8 of 45
The Shortest Path Problem
The shortest path problem aims to find the shortest path in a network from one node to another node. A labeling algorithm can be used to find the shortest g g paths from a particular node to all other nodes in the network, if all arcs in the network have nonnegative values. l Other criteria, such as time and cost, can be used. For example, we may want to find the route with the shortest traverse time from one node to another h i f d h node. Neither time nor cost needs to be linearly related to distance. distance
Jianfeng Mao 9 of 45
Problem Definition and Example Problem Data
Problem: Determine the shortest path from the origin to all destinations. destinations
Shipping routes from Los Angeles
Network of shipping routes
Jianfeng Mao
10 of 45
Problem Definition and Example Problem Data
Problem: Determine the shortest routes from the origin to all g destinations.
Shipping routes from Los Angeles pp g g
Network of shipping routes
Jianfeng Mao
11 of 45
Shortest Path Problem Solution Method Summary
Step 1: Let the shortest distance from the origin to itself be 0. Mark the origin node as a permanent node. Step 2: Select the node with the shortest direct route from the origin. Mark this node as a permanent node. Step 3: Determine all non-permanent nodes directly connected to a permanent node. Step 4: Select a node from the nodes identified in Step 3 which h the shortest route di tl extended from a hi h has th h t t t directly t d d f permanent node. Mark this selected node as a permanent node. Repeat Steps 3 & 4 until all nodes are marked as permanent nodes
Jianfeng Mao 12 of 45
Shortest Path Problem Solution Approach (1 of 7)
Determine the initial shortest route from the origin (node 1) to the l th closest node (3). t d (3)
Network with node 1 in the permanent set
Jianfeng Mao 13 of 45
Shortest Path Problem Solution Approach (2 of 7)
Determine all nodes directly connected to the permanent set.
Network with nodes 1 and 3 in the permanent set
Jianfeng Mao 14 of 45
Shortest Path Problem Solution Approach (3 of 7)
Redefine the permanent set.
Network with nodes 1 2 and 3 in the 1, 2, permanent set
Jianfeng Mao 15 of 45
Shortest Path Problem Solution Approach (4 of 7)
Redefine the permanent set.
Network with nodes 1, 2, 3, and 4 in the 1 2 3 permanent set
Jianfeng Mao 16 of 45
Shortest Path Problem Solution Approach (5 of 7)
Continue.
Network with nodes 1, 2, 3, 4, and 6 in the permanent set 1 2 3 4
Jianfeng Mao 17 of 45
Shortest Path Problem Solution Approach (6 of 7)
Continue.
Network with nodes 1, 2, 3, 4, 5, and 6 in the permanent 1 2 3 4 5 set
Jianfeng Mao 18 of 45
Shortest Path Problem Solution Approach (7 of 7)
Network with optimal routes from Los Angeles to all destinations
From Los Angeles to: Salt Lake City (node 2) Phoenix (node 3) Denver (node 4) Des Moines (node 5) Dallas (node 6) St. Louis (node 7)
Route 12 13 134 1345 136 1347
Total Hours 16 9 24 38 31 43
Shortest Travel Time from Origin to Each Destination
Jianfeng Mao 19 of 45
Shortest Path Problem Solution Approach
Dijkstra's algorithm
Single Source Nonnegative Distance
Bellmen-Ford algorithm
Slower Cover the cases with negative distance Efficiency vs. Ge e a ty c e cy s Generality
Linear Programming Li P i
Jianfeng Mao 20 of 45
Problem Definition and Example Problem Data
Problem: Determine the shortest Path from the origin, city 1 to g , y the target, city 7 in this directed graph.
Jianfeng Mao
21 of 45
Shortest Path Problem
Formulation as a 0-1 integer p g g programming problem. gp
Decision Variables:
1 xij = 0
if branch i - j is selected as part of the shortest route. if not
Objective Function:
Minimize Z = 16x12 + 9x13 + 35x14 + 12x24 + 25x25 + 15x34 + 22x36 + 14x45 + 17x 17 46 + 19 47 + 8 57 + 14 67 19x 8x 14x
Jianfeng Mao
22 of 45
Shortest Path Problem
Formulation as a 0-1 integer programming problem. (contd.)
Constraints:
subject to
x12 + x13 + x14= 1 x12 - x24 - x25 = 0 x13 - x34 - x36 = 0
x14 + x24+ x34 - x45 - x46 - x47 = 0 x25 + x45 - x57 = 0 x36 + x46 - x67 = 0 x47 + x57 + x67 = 1 xij = 0 or 1
Jianfeng Mao
23 of 45
Shortest Path Problem
Formulation as Linear Programming Problem. (contd.)
Constraints:
subject to x12 + x13 + x14= 1 x12 - x24 - x25 = 0 x13 - x34 - x36 = 0 x14 + x24+ x34 - x45 - x46 - x47 = 0 x25 + x45 - x57 = 0 x36 + x46 - x67 = 0 x47 + x57 + x67 = 1 xij 0 The problem can be ready solved as LP by deleting the binary restriction on xij as it is a special type of LP problem.
Jianfeng Mao
24 of 45
Problem Definition and Example Problem Data
Problem: Determine the shortest Path from the origin, city 1 to g , y the target, city 7 in this undirected graph.
Linear Programming Formulation?
Jianfeng Mao
25 of 45
Minimum Spanning Tree Problem
A tree is a set of connected arcs that does not form a cycle. A spanning tree is a tree that connects all nodes of a network. network The minimum spanning tree problem seeks to determine the minimum sum of arc lengths necessary to connect all nodes in a network. Other criteria, such as time and cost can be used. Neither time nor cost are necessarily linearly related to distance.
Jianfeng Mao 26 of 45
Problem Definition and Example Problem Data
Problem: Connect all nodes in a network so that the t t l b th total branch lengths are minimized. hl th i i i d
Network of possible cable TV paths
Jianfeng Mao
27 of 45
Minimum Spanning Tree Problem Solution Method
Step 1: Select any starting node. Step 2: Select the node closest to the starting node, node and connect it to the starting node. node Step 3: Select St 3 S l t a node not currently i the d t tl in th spanning tree that is closest to a node already in the spanning tree, and connect these two nodes. tree nodes Repeat Step 3 until all nodes have joined the spanning tree.
Jianfeng Mao 28 of 45
Minimum Spanning Tree Problem Solution Approach (1 of 6)
Start with any node in the network and select the closest node to join the spanning tree.
Spanning tree with nodes 1 and 3
Jianfeng Mao
29 of 45
Minimum Spanning Tree Problem Solution Approach (2 of 6)
Select the closest node not presently in the spanning area.
Spanning tree with nodes 1, 3, and 4
Jianfeng Mao
30 of 45
Minimum Spanning Tree Problem Solution Approach (3 of 6)
Select the closest node not presently in the spanning area.
Spanning tree with nodes 1, 2, 3, and 4
Jianfeng Mao
31 of 45
Minimum Spanning Tree Problem Solution Approach (4 of 6)
Select the closest node not presently in the spanning area. i
Spanning tree with nodes 1, 2, 3, 4 and 5
Jianfeng Mao
32 of 45
Minimum Spanning Tree Problem Solution Approach (5 of 6)
Select the closest node not presently in the spanning area.
Spanning tree with nodes 1, 2, 3, 4, 5 and 7
Jianfeng Mao
33 of 45
The Minimum Spanning Tree Problem Solution Approach (6 of 6)
Minimum spanning tree for cable TV network
Jianfeng Mao
34 of 45
Maximum Flow Problem
The maximum flow problem is concerned with dete determining t e maximum volume o flow from g the a u o u e of o o one node (called the source) to another node (called the sink). sink) In the maximum flow problem, each arc has a maximum arc flow capacity which limits the flow through the arc
Jianfeng Mao
35 of 45
Problem Definition and Example Problem Data
Problem: Maximize the amount of flow of items from an origin to a destination.
Network of railway system
Jianfeng Mao
36 of 45
Maximum Flow Problem Solution Method Summary
Step 1: Arbitrarily select any path in the network from origin to destination with a positive flow capacity. capacity Let the flow capacity of this path be f f. Increase the flow amount by f along that path. Step 2: Reduce the capacity of each branch on the path identified in Step 1 by f. Step 3: Increase the capacity of each branch on the opposite direction of the path identified in Step 1 by f Repeat Steps 1, 2 & 3 until no path with a positive capacity can be found
Jianfeng Mao 37 of 45
Maximum Flow Problem Solution Approach (1 of 5)
Arbitrarily choose any path through the network from origin to destination d hi d ti ti and ship as much as possible. h ibl
maximum flow for path 1256 a u o o pat 5 6
Jianfeng Mao
38 of 45
Maximum Flow Problem Solution Approach (2 of 5)
Re-compute branch flow in both directions and then select other feasible paths arbitrarily and determine maximum flow th f ibl th bit il dd t i i fl along the paths until flow is no longer possible.
maximum flow for path 146 a u o o pat 6
Jianfeng Mao
39 of 45
Maximum Flow Problem Solution Approach (3 of 5)
Re-compute branch flow in both directions and then select other feasible paths arbitrarily and determine maximum flow th f ibl th bit il dd t i i fl along the paths until flow is no longer possible.
maximum flow for path 136 a u o o pat 3 6
Jianfeng Mao
40 of 45
Maximum Flow Problem Solution Approach (4 of 5)
Re-compute branch flow in both directions and then select other feasible paths arbitrarily and determine maximum flow along the paths until flow is no longer possible.
maximum flow for path 134-6
Jianfeng Mao
41 of 45
Maximum Flow Problem Solution Approach (5 of 5)
maximum flow for railway network
Jianfeng Mao
42 of 45
Maximum Flow Problem
Formulation as Linear programming problem
2 5
Flow = x61
Add a new arc with a sufficient large capacity, say, the sum of capacities of arcs entering node 6.
Jianfeng Mao
43 of 45
Maximum Flow Problem
Formulation as Linear programming problem
xij = flow along branch i-j
Objective Function
maximize Z = x61
Node Flow-Conservation Constraints
subject to bj x61 - x12 - x13 - x14 = 0 x12 x24 x25 = 0 x13 x34 x36 = 0 x14 + x24+ x34 - x46 = 0 x25 - x56 = 0 x36 + x46 + x56 x61 = 0 (flow in & out of node 1) (node 2) (etc.)
Jianfeng Mao
44 of 45
Maximum Flow Problem
Formulation as Linear programming problem (contd.)
Arc Capacity Constraints
x12 6, 6 x24 3, x36 6, x61 17 x13 7 7, x25 8, x46 5, x14 4, 4 x34 2, x56 4,
Non-negativity Constraints
xij 0 for all i,j
Jianfeng Mao
45 of 45
