Network Optimization

Problems
Graphs
•
Shortest Path Problem
• Finds the shortest path between any two given nodes. The nodes are
denoted usually by source (s) and sink (t)
1 7 2
5 6
5
6 8
s t
4
4 4
3
7 5 8

Find the shortest distance between s and t in the above graph

Shortest Path Problem - Formulation
•
Shortest Path Problem – General Formulation
•
Shortest Path Problem – Djikstra’s Algorithm
• Djikstra’s algorithm:
The shortest path problem can also be solved by an very efficient
algorithm known as Djikstra’s algorithm
Djikstra’s algorithm works only when the edge costs are
non-negative
SPP: Djikstra’s Algorithm – Steps -
Initialization
•

(0,p)
SPP: Djikstra’s Algorithm – Step 2
• Nodes 1,4,3 and 5 can be reached from s by distances 5,6,4 and 7.
• The labels of the nodes are changed as (5,t), (6,t), (4,p) and (7,t).
• The label for 3 is made permanent since reaching 3 from s through
any other node will always be greater than 4.
• Node 3 becomes the current node
SPP: Djikstra’s Algorithm – Step 3
• From node 3 one can reach nodes 4 and 5.
• Through 3 from s, node 4 can be reached in 8 and node 5 can be
reached in 9
• Since reaching 4 and 5 through s is cheaper, their respective labels is
not updated.
• Their respective labels are (6,t) and (7,t)
SPP: Djikstra’s Algorithm – Step 3
•
SPP: Djikstra’s Algorithm – Step 3
•
Shortest Path Problem

Find the shortest path from O to T

SPP – Undirected arcs
• Undirected arc indicates bidirectional arcs.
• To find the shortest path between two nodes in the case of a network
with undirected arcs, one has to ignore the arcs coming in source (s)
and arcs going out of destination (t)
Minimum Cost Flow Problem
• Considers flow through a network with limited arc capacities.
• There is a cost (distance) of traversing an arc.
• At least one node is a supply node
• At least one node is a demand node
• Nodes that are not either supply or demand nodes are transshipment
nodes.
• Network has enough arcs with sufficient capacity to handle all flows
generated in the network
• Cost of flow through an arc is proportional to the amount of flow
passing through the arc
Minimum Cost flow problem
• Consider the following network
Minimum Cost flow problem
•
Minimum Cost flow problem
•
Minimum Cost flow problem
[20] [0]
6
A C
3
5
2 E [-30]

3
4
B D
5
[10] [0]
Maximal flow problem
• Given a set of arcs connecting a set of nodes, maximal flow problem
studies the maximum amount of flow that can be sent through the
network from one node to another node.
• Each arc has a predefined capacity that should not be exceeded.
• The problem finds applications in oil transportation, urban
transportation design
Maximal Flow Problem

Problem Statement: Find the maximal amount of flow that can be sent from node 1 to node 6.
Maximal Flow Problem – Formulation
•
Maximal flow problem - Formulation
• Formulation:
Maximal flow problem - Formulation
•
Maximal flow problem – Algorithm
• To solve maximal flow problem, we use a shortest path augmenting
algorithm which is explained below:
• We first enumerate all paths connecting nodes 1 and 6.
• The paths are:
• 1–3–6
• 1–3–4–6
• 1–2–3–6
• 1–2–4–6
• 1–2–5–6
• 1–3–4–5–6
• 1–2–4–5–6
• 1–2–3–4–6
• 1–2–3–4–5–6
Maximal flow path problem - Algorithm
• In the second step, the paths are written in ascending order based on the
number of arcs or the number of nodes in a path
• The sorted order is as follows:
• 1–3–6
• 1–3–4–6
• 1–2–3–6
• 1–2–4–6
• 1–2–5–6
• 1–3–4–5–6
• 1–2–4–5–6
• 1–2–3–4–6
• 1–2–3–4–5–6
Maximal flow path problem - Algorithm
• In the third step, we analyse the maximal flow that be sent through
each of the paths as follows:
Path Arc 1 -2 (20) Arc 1 - 3 (60) Arc 2 - 3 (50) Arc 2 - 4 (30) Arc 2 - 5 (10) Arc 3 - 4 (35) Arc 3 - 6 (10) Arc 4 - 5 (30) Arc 4 - 6 (25) Arc 5 - 6 (50) f
1 - 3 - 6' 50 0 10
1-3-4-6 25 10 0 35
1 - 2 - 4 -6 20 30 0 35
1-2-3-6 20 50 0 35
1-2-5-6 10 0 40 45
1 - 3 - 4 -5 - 6 15 0 20 30 55
1-2-4-5-6 0 20 20 20 65
1 -2 - 3 - 4 - 6 0 50 0 0 65
1-2-3-4-5-6 0 50 0 20 20 65

For each of the path, the maximal flow that can be sent is the minimum of the arc capacities in the
path.
Using the above principle, flows are added and the optimal solution is 65 for the problem
Minimum Spanning Tree
• Before studying about spanning trees, we first define a tree in graph
terminology.
• When it comes to connectivity between nodes, there are two entities
in graph theory which defines it.
• One is a cycle and another is a tree.
• Consider the following two examples:
Minimum Spanning tree
Setting off from one node to Setting off from one node to
another node, in a cycle there are another node, In a tree there is
more than one ways of reaching only one way to reach a node
one node
1 a

2 3 b c

A Cycle A Tree
For example, starting from 1 to For example, starting from a to
node 2 one can take path 1 – 2, node b one can take path a – b,
Now if one needs to get back to 1, Now if one needs to get back to a,
there are two options: one is just there is only one option, which is
reverse traversal (2 - 1) or through reverse traversal (b - a)
2–3–1
Minimum Spanning tree
• Minimum spanning tree aims to create a tree of minimum cost that
spans across all the nodes in the network.
• This problem is particularly useful in cases where the cost of laying
arcs is very costly.
• Typical examples include: Telecommunication, Power distribution,
Road laying in rural areas etc.,
Minimum Spanning tree

• Consider the following network:

Construct a MST on this network

MST formulation:
•
MST formulation
•
MST formulation
• First constraint ensures that only 4 arcs are present in the MST.
(Observe that for any tree with N nodes, the number of arcs are N - 1)
• Remaining constraint ensures that cycles of shorter lengths are not
present in the solution.
• Notice that constraint are written for all possible combinations of
nodes namely, (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4),
(2,3,5), (2,4,5), (3,4,5), (1,2,3,4), (1,2,3,5), (1,2,4,5), (1,3,4,5), (2,3,4,5)
• For each of the node combinations, cycles are forbidden through the
RHS (<= N - 1)
MST – Prim’s algorithm
•
MST – Prim’s algorithm
• S = {1,3,5}; R = {2,4}
• Repeating the above step, node 2 is at distance of 4 units from 1
• S = {1,2,3,5}; R = {4}
• Repeating the above step, node 4 is at 5 units from 2.
• S = {1,2,3,4,5}; R= {}
• When the residual set is empty, the algorithm terminates.
• In the MST, following arcs are present: {(3,5), (3,1), (1,2), (2,4)}