Introduction to
Mathematical Optimization
(Lecture #12)
Shunsuke HAYASHI
Today’s topic
Network Optimization
（ネットワーク最適化）
What is the network optimization?
Optimization over the graph
Graph
Graph is defined by a vertex set V and an edge set E.
vertex
edge
vertex set （頂点集合）
edge set （辺集合）
Note: Every edge can be written as a pair of two vertices, equivalently.
Vertex（頂点） is also called node（接点）, point（点）, etc.
Edge（辺） is also called link（リンク）, branch（枝）, arc（弧，弦）, etc.
3
Directed and Undirected Graphs
Undirected graph （無向グラフ）
Each edge does not have direction.
Directed graph （有向グラフ）
Each edge has direction.
4
Network
In considering the network optimization, certain values
are assigned to each vertex or edge of the graph.
Each value means the length (distance), traffic capacity, cost,
travel time, or weight. (It depends on the mathematical model.)
Network
The graph including those values are also
called a network.
5
Network
vertex set （頂点集合）
edge set （辺集合）
weight （重み）
6
Examples of network optimization
• Minimum spanning tree problem （最小全域木問題）
• Shortest path problem （最短路問題）
• Traveling salesman problem （巡回セールスマン問題）
• Maximum flow problem （最大フロー問題）
• Maximum matching problem （最大マッチング問題）
• Minimum cut problem （最小カット問題）
7
Minimum spanning tree problem
（最小全域木問題）
Tree (木)
a connected graph with no cycle
Spanning tree (全域木)
8
Minimum spanning tree problem
（最小全域木問題）
minimum spanning tree
Application: design of transistor, electric circuit, etc.
9
Necessary and sufficient condition
to be a minimum spanning tree
minimum spanning tree
max
10
Necessary and sufficient condition
to be a minimum spanning tree
minimum spanning tree
How can we obtain the m.s.t.?
(1) Kruskal’s method
(2) Prim’s method
Both methods can find the m.s.t. efficiently.
11
Shortest path problem （最短路問題）
(Here, the weight of each edge is regarded as the length.)
Application: car navigation system, etc.
12
Shortest path tree （最短路木）
The shortest paths from the origin s to all other vertices
can be expressed as a spanning tree.
shortest path tree
the length of
shortest path
The shortest path tree can be found efficiently by well-known Dijkstra’s algorithm.13
Dijkstra’s algorithm （ダイクストラ法）
We want to find the minimum spanning
tree from the origin vertex
6
5
4
[Step 0]
6
5
2
4
5
2
2
6
2
4
3
2
4
6
4
4
2
Let
[Step 3]
Let
4
2
6
2
4
3
2
[Step 2]
6
5
5
4
6
2
2
3
3
5
[Step 1] Calculate
4
2
2
6
6
2
4
4
3
2
5
2
2
-- 1st iteration--
5
4
2
6
14
Dijkstra’s algorithm （ダイクストラ法）
5
5
4
6
2
5
5
2
4
2
5
5
4
2
2
4
4
2
Let
[Step 3]
Let
4
6
6
2
4
3
2
[Step 2]
2
6
5
4
8
2
3
5
2
6
Let
86
6
2
[Step 3]
4
3
2
4
4
2
6
2
8
[Step 1] Calculate
4
3
4
6
2
5
Let
2
6
2
4
5
4
3
2
5
-- 3rd iteration--
6
2
[Step 2]
6
56
2
8
6
2
[Step 1] Calculate
45 4
3
2
-- 2nd iteration--
4
2
6
6
15
Dijkstra’s algorithm （ダイクストラ法）
5
5
4
6
2
4
3
2
2
5
5
4
5
5
4
6
6
11
4
2
6
11
[Step 2]
Let
5
5
4
5
Let
4
4
6
6
6
6
10
4
2
[Step 1] Calculate
[Step 2]
Let
[Step 3]
Let
4
2
6
6
6
10
2
4
3
2
2
4
-- 5th iteration--
2
2
2
[Step 3]
4
3
5
4
2
3
2
6
6
4
4
6
2
5
11
10
6
2
2
3
2
[Step 1] Calculate
5
2
6
2
2
4
-- 4th iteration--
2
3
2
11
4
2
6
6
Finish!
16
Property of Dijkstra’s algorithm
• If we have n vertices, then the algorithm terminates
in n iterations.
The shortest path problem is not NP hard!
17
Traveling salesman problem (TSP)
（巡回セールスマン問題）
origin
The sales man wants to visit all points without duplication
minimizing the total traveling cost!
Application: delivery planning, analysis of protein structure, etc.
18
Traveling salesman problem (TSP)
（巡回セールスマン問題）
Example of the TSP for 532 cities in USA.
TSP is an NP hard problem (very difficult problem).
We can solve it only approximately, in general.
19
Hamiltonian circuit problem
（ハミルトン閉路問題）
Special version of TSP
For a given graph, does there exist a Hamiltonian circuit
(a cycle which covers all the vertices)?
How about this graph?
Hamiltonian circuit exists!
20
Hamiltonian circuit problem
（ハミルトン閉路問題）
Special version of TSP
For a given graph, does there exist a Hamiltonian circuit
(a cycle which covers all the vertices)?
Those graphs do not have Hamiltonian circuit.
(It is not easy to check…)
21
Maximum flow problem （最大フロー問題）
Consider the following network with a directed graph.
6
3
1
4
2
3
3
2
7
2
3
Each value at the edge denotes the flow capacity of the edge.
We want to find the maximum flow which does not
exceed the flow capacity at each edge.
What is flow?
22
Maximum flow problem （最大フロー問題）
Flow is an abstract of electric current, water flow, traffic flow, etc.
2
3
0
amount of flow
for each edge
4
2
3
1
0
3
0
3
• Each vertex except origin and destination must satisfy the
flow conservation principle （フロー保存則）.
• The amount of the flow coming out from the origin must be equal
to that going into the destination. (In this case, the amount is 6.)
23
Maximum flow problem （最大フロー問題）
Then, the maximum flow problem is
flow conservation principle
flow capacity condition
the amount of the flow coming out from the origin
(= the amount of the flow going into the destination)
This flow pattern does not attain the
maximum because we can still add
the flow of 2 appropriately.
24
How to solve maximum flow problem
In order to solve, we introduce the residual network （残余ネットワーク）.
We can still add flow
of 4 in this direction.
Original network
We can still add flow
of 2 in this direction.
We cannot add the flow in
the opposite direction.
Residual network
Based on the residual network, we judge whether or not
we can still add the flow from s to t (maximum or not).
25
How to solve maximum flow problem
Original network
Residual network
26
How to solve maximum flow problem
When the residual network becomes
unattainable from s to t, we obtain the
maximum flow.
27
Maximum Matching Problem
(最大マッチング問題）
Example: students
assignment problem
(students)
(lab)
28
How to solve the maximum matching problem
Network
Bipartite graph
such that
maximum matching problem
equiv.
maximum flow problem over N’
29
Minimum cut problem （最小カット問題）
Application
Sum of those values should be minimized.
• Each vertex denotes each student in the class, and the weight of
each edge denotes the amount of friendship.
• We want to divide those students into two groups with keeping
the friendship as strongly as possible.
This problem can be cast as a minimum cut problem.
Many efficient algorithms (e.g., MA ordering method) has been
proposed so far. (omitted here)
30