Optimisation Methods
Kathleen Steinh ̈ofel and Tomasz Radzik
6CCS3OME
Combinatorial Optimisation, SAT, MST
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Combinatorial Optimisation
A combinatorial optimisation problem:
We can view an instance of a combinatorial optimisation problem as a pair (R, C), where
R– is a (finite) set of (combinatorial) configurations, given in some implicit way (that is, not given as an explicit list of all configurations), C– is a cost function, C : R → Real numbers, assigning to each configuration its cost; specified as a procedure for calculating the cost of a given configuration
Problem: find a configuration with the minimum cost. That is, find a configuration config ∈ R such that the cost C(config) of this configuration is as small as possible, i.e., there is no configuration with a smaller cost.
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Example
Let’s look at how solving a problem instance can also be formulated as an optimisation problem.
. . . I was really good this year, so please
bring me a present OR
bring my mum a present OR
DO NOT bring my little brother a present.
Let’s represent the letter: (x1 ∨ x2 ∨ x3)
There are 7 ways to satisfy this wish: (x1, x2, x3) =
{(000), (010), (011), (100), (101), (110), (111)}.
Combinatorial Optimisation, SAT, MST 3 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Can Santa satisfy all letters?
F =(x1 ∨x2 ∨x3) (x3 ∨x4 ∨x5) (x1 ∨ x5 ∨ x6) . . .
Definition (Satisfiability Problem – SAT)
For a given CNF (conjunctive normal form) of a Boolean function over vaiables (x1 , . . . , xn ) decide whether or not there is an assignment φ(x1,…,xn) with all xi ∈ {0,1} such that F(φ) = 1.
Satisfiability is one of the core combinatorial problems with many applications. First problem that was shown to be NP-complete, i.e. computationally hard.
Combinatorial Optimisation, SAT, MST 4 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Computationally Hard Problems
What is an algorithm?
What are the fundamental capabilities and limitations of computers? When should an algorithm be considered practically feasible?
What makes some problems computationally hard and others easy?
Combinatorial Optimisation, SAT, MST 5 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Time Complexity of Algorithms
Combinatorial Optimisation, SAT, MST 6 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Time Complexity of Problems
Combinatorial Optimisation, SAT, MST 7 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
NP, NP-Complete, and NP-Hard Problems
Combinatorial Optimisation, SAT, MST 8 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Back to Santa
Let’s restrict the letter size to three lines/wishes.
With n people sending possibly more than one letter, we have many
possible letters:
2n 2n · (2n − 1) · (2n − 2) 3 3 = 1·2·3 ≈n.
Santa decides for everyone whether they do or do not get a present. There are 2n possible combinations.
Definition (MAX-3-SAT)
For a given CNF with clause length three find a φ that maximises the number of satisfied clauses.
Combinatorial Optimisation, SAT, MST 9 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
3-SAT:
NP-complete decision problem. Reduced from general SAT. Just a few letters: likely to satisfy all.
Lots and lots of letters: probably not satisfiable. Phase-transition of 3-SAT.
MAX SAT:
It is a combinatorial optimisation problem.
There are 2n different φ among which we want to find one φmax that maximises the number of satisfied clauses.
Already for n ≥ 300 there are more φs than atoms in the observable universe.
It is computationally hard to find a φmax .
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Other Problems
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Number of Edges in Complete Graphs
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Number of Edges in Tree Graphs
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Spanning Trees
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Number of Spanning Trees
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Combinatorial Optimisation, SAT, MST 1 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Weighted Graphs
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Minimum Cost Spanning Trees (MST)
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Prim’s Algorithm for Finding MST
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Growing Forests to Find a MST
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Kruskal’s Algorithm for Finding a MST
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25
Complexity of MST Problems
Prim and Kruskal solve the MST problem in polynomial time.
Prim’s: O(|V|2) with a good choice of data structure O(|E|log|V|). Kruskal’s: O(|E|log|V|)
Related problems that we cannot solve that easily: Degree-constrained minimum spanning tree. Steiner Tree Problem.
Finding MST has many applications. Most variations arise in VLSI design.
Later during the course we will explore how an efficient algorithm for finding MST can help finding approximate solutions for the TSP.
Combinatorial Optimisation, SAT, MST 2 Kathleen Steinh ̈ofel (KCL) Lecture 1 / 25