Optimisation Methods
Kathleen Steinh ̈ofel and Tomasz Radzik
6CCS3OME
Complexity Classes, TSP, Approximation
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 1 / 26
NP, NP-Complete, and NP-Hard Problems
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 2 / 26
Problems and Complexity Classes
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 3 / 26
P, NP, NP-hard
One of the Millennium Problems: Click here
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 4 / 26
Methods
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 5 / 26
Hamiltonian Cycles
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 6 / 26
HCs in Complete Graphs
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 7 / 26
Classic TSP
The input a complete, weighted graph G(V,E,w), where set V represents the cities to be visited and E represents the edges between cities, the weights on edges given by w are all positive.
Decision problem: Given a target k, is there a tour which visits each city exactly once and has total weight less than k?
Optimisation problem: Determine the tour which visits each city exactly once and has the minimum possible total weight.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 8 / 26
Branch-and-Bound
Consider the following instance of a TSP with n = 5 cities.
The example is from ”Foundations of Algorithms” by R. Neapolitan and K. Naimipour (see Reading List).
1
2
3
4
5
1
0
14
4
10
20
2
14
0
7
8
7
3
4
5
0
7
16
4
11
7
9
0
2
5
18
7
17
4
0
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 9 / 26
Branch-and-Bound: Example
Branch-and-Bound is an exhaustive method that evaluates partial configurations and discards those which cannot lead to an optimal solution.
The root is the city we start from. Each leaf represents a complete tour. The number of leaves for a n-city instance of TSP:
(n − 1)(n − 2) · · · 2 = (n − 1)!
Forexample: 4!=1·2·3·4=24,15!≈1.3·1012
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 10 / 26
Branch-and-Bound: Notions
Root: There is a path from the initial partial configuration to any configuration.
Internal Node: Partially specified configuration, which can be extended to a number of complete configurations.
Branching: takes as input a partial configuration P (which is not a complete configuration) and produces partial configurations P1,P2,…,Pk which extend P.
Bounding: A bounding procedure computes for a given partial configuration P, a lower bound on the cost of any configuration which can be obtained by extending configuration P.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 11 / 26
Branch-and-Bound for TSP
For TSP with 1,2,··· ,n cities:
Partial configuration: a sequence of distinct cities starting at city 1. Formally, a sequence of integers ⟨i1, i2, · · · , ik ⟩, with 1 ≤ k ≤ n − 1 and i1 = 1. All i1, i2, · · · , ik being distinct. Example: ⟨1, 3, 2, 7⟩.
Initial Partial Configuration: ⟨1⟩
Branching: For a partial configuration ⟨i1 , i2 , · · · , ik ⟩ output all partial configurations that extend the sequence by one city, which is not included in the partial configuration: ⟨i1,i2,··· ,ik,x⟩ with
x ̸= ij,1 ≤ j ≤ k.
For example, if n = 6 and the input is ⟨1, 3, 4⟩ then the output is ⟨1,3,4,2⟩, ⟨1,3,4,5⟩ and ⟨1,3,4,6⟩
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 12 / 26
Branch-and-Bound for TSP
Bounding: A procedure that computes for a given partial configuration P, a lower bound on the cost of any configuration which can be obtained by extending configuration P.
An example of a bounding procedure for TSP is:
For a P = ⟨i1, i2, · · · , ik ⟩, with k ≤ n − 2, sum the cost of the partial tour and the minimum outgoing edge from cities not already connected in P.
More formally, the procedure calculates a bound via the following sum CLB (P ) = c (i1 , i2 ) + c (i2 , i3 ) + · · · + c (ik −1 , ik )+
min{c(ik,x) : x ̸∈ {i1,i2,··· ,ik}}+
v̸∈{i1,i3,···,ik} min{c(v,x) : x ̸∈ {i2,i3,··· ,ik,v}}.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 13 / 26
Observation
If the input is the initial partial configuration ⟨1⟩, then sum, over all cities, the minimum cost of a link outgoing from each city:
n
min{c(i, x) : x ∈ {1, 2, · · · , n} − {i}} i=1
This gives a lower bound on the cost of any TSP tour; in particular, a lower bound on the minimum cost of a TSP tour.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 14 / 26
Back to our Example
In our example, the bounding procedure on ⟨1⟩ = 21.
We have
c (1, 3) + c (2, 3) + c (3, 1) + c (4, 5) + c (5, 4) = 4 + 7 + 4 + 2 + 4 = 21.
Note: This is a lower bound, i.e., any tour of this TSP instance has a cost greater or equal to 21.
1
2
3
4
5
1
0
14
4
10
20
2
14
0
7
8
7
3
4
5
0
7
16
4
11
7
9
0
2
5
18
7
17
4
0
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 15 / 26
Back to our Example
For a partial tour P = ⟨1, 2, 3⟩ our bounding procedure returns 34.
Sum of the cost of C (P ) = c (1, 2) + c (2, 3) = 14 + 7 = 21 and minimum outgoing edge of 3 not going back min{c (3, 4), c (3, 5)} = 7 and minimum outgoing edges of cities not in P again not going back except for 1: min{c(4, 1), c(4, 5)} + min{c(5, 1), c(5, 4)} = 2 + 4 = 6. Therefore, we have 21 + 7 + 6 = 34.
1
2
3
4
5
1
0
14
4
10
20
2
14
0
7
8
7
3
4
5
0
7
16
4
11
7
9
0
2
5
18
7
17
4
0
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 16 / 26
Branch-and-Bound Pseudocode
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 17 / 26
Symmetric TSP with ∆ineq.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 18 / 26
Christofides’ Algorithm
For the symmetric TSP (∆ineq.) 2-approximation algorithms were known, e.g. Double Tree, Nearest Addition.
In 1976, Christofides published the following algorithm
1 Find the MST T with distance matrix [di,j].
2 Find the nodes of T with odd degree and find the shortest complete match M in the complete graph consisting of these nodes only. Let G be the multigraph with nodes {1, . . . , n} and edges those in T and M.
3 Find an Eulerian walk of G and an embedded tour.
It finds a 1.5-approximate tour.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 19 / 26
Example
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 20 / 26
Step 1 – MST
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 21 / 26
Step 2a – Odd Degree Nodes
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 22 / 26
Step 2b – Minimum Matching
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 23 / 26
Step 3a – Eulerian Walk
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 24 / 26
Step 3b – Embedded Tour
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 25 / 26
Proof
Definition (Theorem)
Christofides’ Algorithm is a 1.5-approximation algorithm.
Proof:
MST and matching can be done in polynomial time.
The constructed tour is feasible.
The cost of the produced tour is at most the cost of the Euler tour, which is cost(T) + cost(M).
We know that cost(T) < OPT.
We can show that cost(M) < OPT/2.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 26 / 26