Combinatorial Optimization

Lecture 4: Some classical combinatorial optimization

problems

Le Hai Yen, Institute of Mathematics, VAST

Master IATOM, USTH, Hanoi

2024

1/1
Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Basic concepts in graph theory

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Basic concepts in graph theory

Directed and undirected graphs

A directed graph G = (V, A) An undirected graph G = (V, E)

consists of consists of
a set V of vertices, and a set V of vertices, and
a set A of (directed) arcs a set E of (undirected) edges

Arc = ordered pair of Edge = unordered pair of

distinct vertices distinct vertices
2 4 2 4

1 5 7 1 5 7

3 6 3 6
 Basic concepts in graph theory

Directed and undirected networks

A directed network G = (N, A) An undirected network
consists of G = (N, E) consists of
a set N of nodes a set N of nodes
a set A of (directed) arcs a set E of (undirected) edges
(ordered pairs of distinct (unordered pairs of distinct
nodes) nodes)
numerical values associated numerical values associated
to each node and/or arc to each node and/or edge

6 6
2 4 7 2 4 4
4 4
4 2 2 4 2 2

2 2
1 0 5 7 1 9 0 3 5 7
6
3 2 3 2
3 3 3 3
3 6 5 3 6 4
3 3
 Basic concepts in graph theory

Some concepts in directed graphs (I)

Given a directed graph G = (V, A)

For an arc (i, j) ∈ A we say

i is a predecessor of j
j is a successor of i
(i, j) is an outgoing arc of vertex i
2 4
(i, j) is an incoming arc of vertex j
i and j are adjacent to each other
(i, j) is incident to i and j
1 5 7

For a vertex i ∈ V
The indegree of i is 3 6
the number of incoming arcs of i
The outdegree of i is
the number of outgoing arcs of i
The degree of i
= its indegree + its outdegree
 Basic concepts in graph theory

Some concepts in directed graphs (II)

Given a directed graph G = (V, A)
A walk in G is a sequence of vertices

i1 − i2 − . . . − ir
2 4
where ik is adjacent to ik+1
(with k = 1, . . . , r − 1)
Example: 1 − 2 − 4 − 5 − 2 − 3 1 5 7

A path in G is
a walk without repetition of vertices
3 6
Example: 1 − 2 − 4 − 5 − 6
Vertices i and j are connected if
there is at least one path from i to j
Example: 1 & 6 are connected

G is connected if every pair of its vertices is connected

 Basic concepts in graph theory

Some concepts in directed graphs (III)

Given a directed graph G = (V, A)

2 4
A cycle in G is a closed path
(start and end at same vertex)
Example: 2 − 4 − 5 − 2 1 5 7

A directed graph is acyclic if it

contains no directed cycle 3 6
 Basic concepts in graph theory

Some concepts in directed graphs (IV)

Given a directed graph G = (V, A)

A cut of G is
a partition of the vertex set V
into two parts S and S = V \ S 2 4

Notation: [S, S]
Note: cut [S, S] defines a set of arcs 1 5 7

having one endpoint in S and

another endpoint in S
3 6

Given two distinct vertices s and t.

An s − t cut is
a cut [S, S] with s ∈ S and t ∈ S
 Basic concepts in graph theory

Some concepts in directed networks

The mentioned concepts in directed graphs

are also applied to directed networks
 Basic concepts in graph theory

Some concepts in undirected graphs

Given an undirected graph G = (V, E)

For an edge {i, j} ∈ E we say

i is adjacent to j
{i, j} is incident to i and j
2 4

For a vertex i ∈ V
The degree of i
1 5 7
= the number of edges incident to i

The concepts of
3 6
walk, path, cycle
connected undirected graph
acyclic undirected graph
are defined as with directed graphs
 Basic concepts in graph theory

Some concepts in undirected networks

The mentioned concepts in undirected graphs

are also applied to undirected networks
 Shortest path problem Problem description

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Shortest path problem Problem description

Problem description
Input:
a directed network G = (N, A)
arc length cij associated with each (i, j) ∈ A
two distinct nodes s, t ∈ N

Definition: Length of a path = sum of lengths of arcs in the path

Objective: Find the shortest path from s to t
2
3 5
3
4

2 1 1
1 6

6 7
2
2 4
 Shortest path problem Problem description

Assumptions

All arc lengths are integers

The network contains a path from s to every other node

The network does not contain a cycle of negative length

 Shortest path problem Dijkstra’s algorithm

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm: principle

Compute shortest paths from source s to all other nodes
Key ideas based on
.
Property 1
.
If a path s = i1 − i2 − . . . − ih = t is a shortest path from s to t,
then for every q = 2, . . . , h − 1 the subpath s = i1 − i2 − . . . − iq is
a. shortest path from s to iq .

q
s
t

.
Property 2
.
Let d(i) be the shortest path distance from source s to node i.
Then a path P from s to node k is a shortest path if and only if
d(j)
. = d(i) + cij for every (i, j) ∈ P.
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0,
d(i) = ∞ ∀i ̸= s
Each iteration:
Node selection:
i := node of minimum temporary
label, make it permanent
Distance update:
If (i, j) ∈ A and d(j) > d(i) + cij ,
then set d(j) := d(i) + cij
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, ∞ ∞
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent ∞
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
∞ ∞
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, ∞
4
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent ∞
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
6 ∞
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, 6
4
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent ∞
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
6 5
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, 6
4
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent
12
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
6 5
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, 6
4
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent
9
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
6 5
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm via an example

Label-setting:
Each node i has a (distance) label d(i)
Permanent nodes: label = shortest distance from source
Temporary nodes:
label = upper bound on length of shortest path from source
Algorithm illustration:
Step 1: temporary labels d(s) = 0, 6
4
d(i) = ∞ ∀i ̸= s 3
2
5
Each iteration: 4
3
Node selection: 0
i := node of minimum temporary 1 2 1 1
6
label, make it permanent
9
Distance update: 6 7
If (i, j) ∈ A and d(j) > d(i) + cij , 2
2
4
then set d(j) := d(i) + cij
6 5
Stop when all nodes are permanent
 Shortest path problem Dijkstra’s algorithm

Dijkstra’s algorithm: pseudo-code

Require: Directed network G = (N, A), source node s ∈ N,

compute shortest paths from s to all other nodes
1: S := ∅, S := N, d(s) := 0, pred(s) := s, d(i) = ∞ ∀i ∈ N
2: while |S| < |N| do
3: i := argmin{d(j) | j ∈ S}
4: S := S ∪ {i}, S := S\{i}
5: for each j ∈ N with (i, j) ∈ A do
6: if d(j) > d(i) + cij then
7: d(j) := d(i) + cij , pred(j) := i
8: end if
9: end for
10: end while
 Max-flow problem Problem description

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Max-flow problem Problem description

Problem description
Input:
a directed network G = (N, A)
arc capacity cij associated with each (i, j) ∈ A
source node s ∈ N, sink node t ∈ N

Objective:
send maximum amount of (flow) units from s to t satisfying
arc capacities
flow conversation at all other nodes

3
4 5

s 1 3 4 t
2
1
2
 Max-flow problem Problem description

Problem description
Input:
a directed network G = (N, A)
arc capacity cij associated with each (i, j) ∈ A
source node s ∈ N, sink node t ∈ N

Objective:
send maximum amount of (flow) units from s to t satisfying
arc capacities
flow conversation at all other nodes

3
4 5
4 5
s 1 1 3 4 t
2 1
2 1
2
 Max-flow problem Problem description

Assumptions

All arc capacities are nonegative integers

The network does not contain a directed path from s to t

composed only of infinite capacity arcs

The network does not contain parallel arcs

 Max-flow problem Augmenting path algorithm

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Max-flow problem Augmenting path algorithm

Intuition

Start by sending some flow units from s to t

Compute residual capacity in each arc residual network
Send more flow units through a directed path from s to t
(if possible) augmenting path

3
4 5

s 1 3 4 t
2
1
2
 Max-flow problem Augmenting path algorithm

Intuition

Start by sending some flow units from s to t

Compute residual capacity in each arc residual network
Send more flow units through a directed path from s to t
(if possible) augmenting path

3
4↓3 5↓4
1 1
s 1 0 3↓3 4 t
2↓1 1
1 1↓0
2
 Max-flow problem Augmenting path algorithm

Intuition

Start by sending some flow units from s to t

Compute residual capacity in each arc residual network
Send more flow units through a directed path from s to t
(if possible) augmenting path

3
4↓0 5↓1
4 4
s 1 0 3↓3 4 t
2↓1 1
1 1↓0
2
 Max-flow problem Augmenting path algorithm

Intuition

Start by sending some flow units from s to t

Compute residual capacity in each arc residual network
Send more flow units through a directed path from s to t
(if possible) augmenting path

3
4↓0 5↓0
4 5
s 1 1 3↓2 4 t
2↓0 1
2 1↓0
2
 Max-flow problem Augmenting path algorithm

Residual network
“Remaining flow network” for carrying incremental flow
Intuitive idea:
Original network G: arc (i, j) has capacity cij
Given xij flow units in arc (i, j)
Up to cij − xij flow units can be sent i → j
Up to xij units can be sent j → i to cancel existing flow in (i, j)
Construction of residual network Gr (x):
Replace arc (i, j) in original network G by
arc (i, j) with residual capacity rij = cij − xij , and
arc (j, i) with residual capacity rji = xij
Remove arcs with residual capacity 0
3 3
4 5 1
3 5 5
3
1 2 3 4 1 2 1 4
s 2 0 t s t
2 1 2 1
2 Gr (x) 2
G, x
 Max-flow problem Augmenting path algorithm

Augmenting path

An augmenting path is
a directed path from source to sink in residual network
Residual capacity of an augmenting path is
the minimum residual capacity of any arc in the path
Always positive (by residual network construction)
Observation:
Additional flow can be sent s → t along augmenting path

3 3
1
3+1
3 5 5
1 2 1 4 1 1 1+1 4
s t s t
2 1 2 1
2 2
 Max-flow problem Augmenting path algorithm

Augmenting path: how to find

Input: Directed residual network Gr (x), source s ∈ N, sink t ∈ N

Objective: find a directed path from s to t in Gr (x)
Labeling algorithm:
1: Label source node s
2: LIST := {s}
3: while LIST ̸= ∅ and t is unlabeled do
4: Remove a node i∗ from LIST
5: for each arc (i∗ , j) in Gr (x) do
6: if j is unlabeled then
7: pred(j) := i∗
8: label j
9: LIST := LIST ∪ {j}
10: end if
11: end for
12: end while
 Max-flow problem Augmenting path algorithm

Augmenting path algorithm

Step 1: send no flow unit through network (x = 0)
Each iteration:
Compute residual network Gr (x)
Find an augmenting path in Gr (x)
If such path exists, then
Compute residual capacity δ of such path
Augment δ flow units along the path, and
update flow value in each arc
Stop when no augmenting path is found

3 3
4 5 4 5
0
0
1 0 3 4 1 3 4
s 0 0 t s t
2 1 2 1
2 Original 2 Residual
 Max-flow problem Augmenting path algorithm

Augmenting path algorithm

Step 1: send no flow unit through network (x = 0)
Each iteration:
Compute residual network Gr (x)
Find an augmenting path in Gr (x)
If such path exists, then
Compute residual capacity δ of such path
Augment δ flow units along the path, and
update flow value in each arc
Stop when no augmenting path is found

3 3
4 5 4 1
4
4 4
1 0 3 4 1 3 4
s 0 0 t s t
2 1 2 1
2 Original 2 Residual
 Max-flow problem Augmenting path algorithm

Augmenting path algorithm

Step 1: send no flow unit through network (x = 0)
Each iteration:
Compute residual network Gr (x)
Find an augmenting path in Gr (x)
If such path exists, then
Compute residual capacity δ of such path
Augment δ flow units along the path, and
update flow value in each arc
Stop when no augmenting path is found

3 3
4 5 4 1
4
4 4
1 0 3 4 1 3 4
s 1 1 t s 1 1 t
2 1 1
2 Original 2 Residual
 Max-flow problem Augmenting path algorithm

Augmenting path algorithm

Step 1: send no flow unit through network (x = 0)
Each iteration:
Compute residual network Gr (x)
Find an augmenting path in Gr (x)
If such path exists, then
Compute residual capacity δ of such path
Augment δ flow units along the path, and
update flow value in each arc
Stop when no augmenting path is found

3 3
4 5 4
5
4 5
1 1 3 4 1 3 4
s 2 1 t s 2 1 t
2 1
2 Original, optimal 2 Residual
 Max-flow problem Max-flow min-cut theorem

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Max-flow problem Max-flow min-cut theorem

Max-flow min-cut theorem

.
Theorem
.
The maximum value of the flow from a source node s to a sink
node t in a capacitated network equals the minimum capacity
among
. all s − t cuts.

Proof. Based on the observation:

Any flow s → t must pass through forward arcs of every s − t cut.

2 4

1 5 7
s t

3 6
 Traveling salesman problem Problem description

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Traveling salesman problem Problem description

Traveling salesman problem (TSP)

Given a list of cities and the distances between each pair of cities,
what is the shortest possible route
that visits each city and returns to the origin city?

49-city USA tour. Newsweek, July 26, 1954

 Traveling salesman problem Problem description

Symmetric TSP
Input:
An undirected network G = (N, E) in which
N is set of nodes
E consists of all possible edges
edge length cij associated with each {i, j} ∈ E
Objective: find a (Hamiltonian) cycle of minimum length
(that visits every node in the network)

2 5

3 4
 Traveling salesman problem Problem description

TSP: Why study?

First formulated in 1930

One of the most intensively studied problems in optimization
Wide range of application (chip designing, moving telescope
between sources, . . .)
Meanwhile, the Clay Mathematics Institute is offering
a $1 million prize to anyone who can show
whether TSP can be fully solved at all,
which the mathematician Jordan Ellenberg recently called
“the biggest open problem in complexity theory”.
 Traveling salesman problem Problem description

Milestones in the solution of TSP instances

 Traveling salesman problem Problem description

American tour: 13509 cities

13509-city USA tour. Spektrum der Wissenschaft, April 1999

Update: up to 115475 Towns and Cities in the United States, July, 2012
 Traveling salesman problem Problem description

Sweden tour: 24978 cities

http://www.math.uwaterloo.ca/tsp/sweden/index.html
 Traveling salesman problem Problem description

TSP: recent computational attempts

World TSP: 1,904,711-city instance

Current best lower bound on the length of a world TSP tour is
7,512,218,268 km
March 13, 2018:
A world TSP tour of length 7,515,772,107 km was found
(at most 0.0474% greater than the length of an optimal tour)
 Traveling salesman problem A heuristic solution approach

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Traveling salesman problem A heuristic solution approach

Try all solution?

The most direct solution approach would be

to list all feasible solutions and see which one is shortest
Computational attempts:
n nodes =⇒ n! feasible solutions.
If a CPU can generate and evaluate 109 solutions per second,
then to compute all solutions we need
n = 12: about 0.5 second
n = 20: more than 70 years
...
 Traveling salesman problem A heuristic solution approach

Nearest neighbor and pairwise exchange

Nearest neighbor (greedy algorithm):
Start at one node
Iteratively move to the nearest unvisited node
This gives an initial (might not optimal) solution of TSP
Pairwise exchange (2-opt technique):
Start with a solution
Replace two edges in the cycle by two different edges (of the
same nodes) in order to obtain new and shorter solution

3 3
2 2

1 4 1 4

5 5
 Traveling salesman problem MIP-based approaches

Contents

1. Basic concepts in graph theory

2. Shortest path problem

Problem description
Dijkstra’s algorithm

3. Max-flow problem
Problem description
Augmenting path algorithm
Max-flow min-cut theorem

4. Traveling salesman problem

Problem description
A heuristic solution approach
MIP-based approaches
 Traveling salesman problem MIP-based approaches

Observations

Each node is arrived at from exactly one other node

From each node there is a departure to exactly one other node
Sub-tours must be excluded

1 1

2 5 2 5

3 4 3 4
 Traveling salesman problem MIP-based approaches

Network representation

Set of nodes: N = {1, . . . , n}

Set of edges: E = {{i, j} | i, j ∈ N, i < j}
Variables
{
1 if edge {i, j} is in the cycle
xij =
0 otherwise
 Traveling salesman problem MIP-based approaches

Dantzig-Fulkerson-Johnson formulation

∑
min cij xij
{i,j}∈E
∑ ∑
s.t. xij + xji = 2 ∀i ∈ N
{i,j}∈E {j,i}∈E
∑
xij ≤ |Q| − 1 ∀ Q : ∅ ̸= Q ( N
i,j∈Q:{i,j}∈E

xij ∈ {0, 1} ∀i, j ∈ N

Remark: the last constraints exclude sub-tours

 Traveling salesman problem MIP-based approaches

Modified DFJ formulation

∑
min cij xij
{i,j}∈E
∑ ∑
s.t. xij + xji = 2 ∀i ∈ N
{i,j}∈E {j,i}∈E
∑
xij ≥ 2 ∀S ( N
{i,j}∈E(S)

xij ∈ {0, 1} ∀i, j ∈ N : {i, j} ∈ E

Remark: the last constraints exclude sub-tours, with

E(S) := {{i, j} ∈ E | either i ∈ S, j ̸∈ S or i ̸∈ S, j ∈ S}

 Traveling salesman problem MIP-based approaches

Miller-Tucker-Zemlin formulation
Set of arcs: A = {(i, j) | i, j ∈ N}
Variables: {
1 if the cycle goes from i to j
xij =
0 otherwise
Formulation:
∑
min cij xij
{i,j}∈A
∑
s.t. xij = 1 ∀i ∈ N
j∈N:(i,j)∈A
∑
xji = 1 ∀i ∈ N
j∈N:(j,i)∈A

ui − uj + nxij ≤ n − 1 2≤i<j≤n
ui ≤ n − 1 ∀i = 2, . . . , n
ui ∈ N ∀i = 2, . . . , n
xij ∈ {0, 1} ∀i, j ∈ N : {i, j} ∈ E
Remark: dummy variables ui are used to exclude sub-tours
 Thanks

Thank you for your attention!