888411 OPERATIONS RESEARCH FOR DIGITAL INNOVATION
NETWORK OPTIMIZATION MODELS
LECTURER DR. SARONSAD SOKANTIKA
9TH FEB 2021
PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems
Find shortest-path from entrance O to station T
(The shortest-path problem)
PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems
Install Telephone Line to connect all stations
(The minimum spanning tree problem)
PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems
Tram ride from entrance O to station T is limited by the number of tram trips
can be made on each roads per day, due to the ecological reasons.
How to route the various trips to maximize the number of trips per day?
(the maximum flow problem)
You want to find a shortest path to patrol each station in this park and
comeback to the starting point.
PROTOTYPE EXAMPLE: SEERVADA PARK 4 Problems
(the traveling salesman problem (allow repeated visits))
THE TERMINOLOGY OF NETWORKS
Node or Vertex
Arc or Edge
THE TERMINOLOGY OF NETWORKS
Directed Arc/Edge
THE TERMINOLOGY OF NETWORKS
Undirected Arc or
Link
Directed network: have only directed arc
Undirected network: have only undirected arc
THE TERMINOLOGY OF NETWORKS
A path between two node is a sequence of distinct arc
connecting these nodes.
Example: one of the path connecting node O and T is
OB-BD-DT (O→B→ D→ T)
THE TERMINOLOGY OF NETWORKS
A directed path from node i to node j is a sequence of
connecting arcs whose direction (if any) toward node j.
An undirected path from node i to node j is a sequence of
connecting arcs whose direction (if any) can be toward or away
from node j.
THE TERMINOLOGY OF NETWORKS
Consider a path B → C→ A→ D from B to D.
is it directed or undirected path?
THE TERMINOLOGY OF NETWORKS
A path that begin and end at the same node is called cycle.
If it care about direction, we called it directed cycle. If it is not,
we called it undirected cycle.
Could you give some example?
THE TERMINOLOGY OF NETWORKS
Two node are connected if there exist an undirected path
between them.
A connected network is a network where every pair of nodes is
connected
THE TERMINOLOGY OF NETWORKS
A network G is a subnetwork of network H if each node/arc of G
is a node/arc of H.
THE TERMINOLOGY OF NETWORKS
A spanning tree of a connected network H is a connected subnetwork
that contain each node of H and has no undirected cycle.
Noted: If H has n node, then every spanning tree of H has n-1 arcs
THE TERMINOLOGY OF NETWORKS: Flows
Arc capacity: the maximum amount of flow that can be carried on a directed
Supply node: flow out of the node exceed flow into the node.
Demand node: flow into the node exceed flow out of the node.
Transshipment node : flow into the node equal to flow out of the node
THE TERMINOLOGY OF NETWORKS: Flows
Net Flow of a node is equal to flow out of the node minus
flow into the node.
EXAMPLE OF NETWORKS IN THE REAL WORLD
THE SHORTEST-PATH PROBLEM
Find shortest-path from entrance O to station T
The shortest-path problem is a special type of linear programming problem
Let formulate and solve in excel!
THE SHORTEST-PATH PROBLEM
Three Major Categories of Applications
• Minimize the total distance traveled
• Minimize the total cost of a sequence of activities
• Minimize the total time of a sequence of activities
THE MINIMUM SPANNING TREE PROBLEM
You wish to design the network by inserting enough links to satisfy the
requirement that there be a path between every pair of nodes.
That is, you want to find a minimum spanning tree.
THE MINIMUM SPANNING TREE PROBLEM
To solve this problem, we use a greedy algorithm as follows:
• Select any node arbitrarily to be a starting node, say node S.
• Let’s called any node connected node if it connect with node S.
Otherwise, called it unconnected node.
• Identify the unconnected node that is closest to a connected node, then
connect these two node. Break the tie arbitrary.
• Repeat this process until each node is connected node.
THE MINIMUM SPANNING TREE PROBLEM
Choose node O as a starting node. Connect it with the closest unconnected
node.
THE MINIMUM SPANNING TREE PROBLEM
Find closest unconnected node. Connect it with the closest unconnected
node.
THE MINIMUM SPANNING TREE PROBLEM
Find closest unconnected node. Connect it with the closest unconnected
node.
THE MINIMUM SPANNING TREE PROBLEM
Find closest unconnected node. Connect it with the closest unconnected
node.
THE MINIMUM SPANNING TREE PROBLEM
Find closest unconnected node. Connect it with the closest unconnected
node.
THE MINIMUM SPANNING TREE PROBLEM
Find closest unconnected node. Connect it with the closest unconnected
node.
Since each node is connected to the starting node, we stop the process
THE MINIMUM SPANNING TREE PROBLEM
• This greedy algorithm has iterative nature.
• Even though MST problems can be formulated by using linear programming,
the number of constraint is huge (exponential with respect to number of
nodes).
THE MAXIMUM FLOW PROBLEM
Tram ride from entrance O to station T is limited by the number of tram trips
can be made on each roads per day, due to the ecological reasons.
How to route the various trips to maximize the number of trips per day?
THE MAXIMUM FLOW PROBLEM
• Cut value of a cut is the sum of the arc capacities of the arcs (in the direction
from the source to the sink) of the cut.
This cut has cut value equal to 14.
THE MAXIMUM FLOW PROBLEM
The Max-Flow Min-Cut Theorem
For any network with the single source and sink, the maximum feasible flow from the
source to the sink equals the minimum cut value of cuts that separate the source and
the sink.
THE MAXIMUM FLOW PROBLEM
• If you write an algorithm based on The Max-Flow Min-Cut Theorem, it will have an
iterative nature.
• We can formulate this problem by using linear programming. Let’s see it in excel!
THE TRAVELING SALESMAN PROBLEM (allow repeated visits)
You want to find a shortest path to patrol each station in this park and
comeback to the starting point.
THE TRAVELING SALESMAN PROBLEM (allow repeated visits)
We can formulate this problem as an Integer programming.
Here, we will formulate this problem as a nonlinear non-smooth programming.
Let’s see in the excel.
THE MINIMUM COST FLOW PROBLEM
THE MINIMUM COST FLOW PROBLEM
THE MINIMUM COST FLOW PROBLEM
Here are some subproblem of minimum cost flow problem
• The transportation problem
• The assignment problem
• The transshipment problem
• The shortest-path problem
• The maximum flow problem
THE MINIMUM COST FLOW PROBLEM
THE MINIMUM COST FLOW PROBLEM
THE MINIMUM COST FLOW PROBLEM
Let’s formulate and solve this example in the excel.
Thank You for Your Attention!