Transcript How defuse combinatorial explosions

How defuse combinatorial explosions
By
Dr Simon Martin
Computational Heuristics, Operational Research
and Decision Support Group
University of Stirling
What is Operational Research?
Operational research (OR) is a discipline that
deals with the application of advanced analytical
methods to help make better decisions*.
It is also known as management science or
decision science .
*http://en.wikipedia.org/wiki/Operations_research 14/02/15
Amazon
Services*
Online shopping, Web hosting,
Content Distribution
Revenue
US$ 88.988 billion (2014)
Operating income
US$ 178 million (2014)
Net income
US$ -241 million (2014)
Total assets
US$ 54.505 billion (2014)
Total equity
US$ 10.741 billion (2014)
Employees
154,100 (December 2014)
In Scotland:
•Dunfermline Fulfilment Centre, Scotland
•Edinburgh research facility – AI techniques, mathematics
*http://en.wikipedia.org/wiki/Amazon.com -17/02/15
Objectives
In this talk we will find out about:

Complex explosive problems

Algorithms


Exact algorithms

Heuristics
Practical Problems
Task
27 x 13?
Answer
Method 1
27 x
13
81
+
270
3 51
2
1
Method 2
200
70
60
21 +
351
20
10
3
7
200
70
60
21
OR…
Use the calculator on your mobile!
But..
1. Get smartphone out of pocket
2. Go to calculator app
3. Type numbers
4. Press equals
5. Call out answer
This is also an algorithm!!
Algorithm
An algorithm is a procedure or formula for
solving a problem. The word derives from
the name of the mathematician,
Mohammed ibn-Musa al-Khwarizmi, who
was part of the royal court in Baghdad and
who lived from about 780 to 850.*
*whatis.techtarget.com/definition/algorithm – 15/02/15
Task
Get from A to B
Blindfolded!
Computers execute algorithms
start
r1= r2?
Solve 9-7?
Yes
R1 R2 R3 R4 R5
9 7 0 0 0 0
No
r2= r2+1
....
R1 R2 R3 R4 R5
9 8 1 0 0 0
....
R1 R2 R3 R4 R5
r3= r3+1
9 9 2 0 0 0
....
R1 R2 R3 R4 R5
No
9 9 2 0 0 0
r1= r2?
Yes
r3→ R1
stop
....
R1 R2 R3 R4 R5
2 9 2 0 0 0
....
Can you find the shortest route round?
E
G
F
A
B
C
D
Find the shortest Circuit
7 cities or vertices
21 connections or
Edges
360 Possible Routes!
E
G
F
A
B
C
D
Find the shortest Circuit
Find the short test Circuit
8 cities or vertices
28 connections or
Edges
2520 Possible Routes!
E
G
F
H
A
B
C
D
Find the shortest Circuit
Find the short test Circuit
9 cities or vertices
36 connections or
Edges
20160 Possible Routes!
E
G
F
H
A
B
J
C
D
Combinatorial Explosion
No. of
Cities
As the number of cities increases the number of
tours explodes!
No. of
Tours
3
1
200000
4
3
180000
5
12
160000
6
60
7
360
2520
9
20160
No of tours
8
140000
120000
100000
80000
60000
10
181440
40000
20000
100
0
4.66631
07722e
+155
0
Boom!
2
4
6
No. of Cities
8
10
12
Amazon's product delivery problem
is worse!
?????????????
What do we do?
Answer
We Cheat!
We use
Heuristics
Heuristics
A heuristic technique is any approach to problem solving,
learning, or discovery that employs a practical
methodology not guaranteed to be optimal or perfect, but
sufficient for the immediate goals.
Where finding an optimal solution is impossible or
impractical, heuristic methods can be used to speed up
the process of finding a satisfactory solution.
Heuristics employ common sense knowledge of “rules of
thumb” to help solve a problem
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
Nearest Neighbour Heuristic
E
G
F
A
B
C
D
2-opt (edge sapper)
E
G
F
A
B
C
D
2-opt (break 2 edges)
E
G
F
A
B
C
D
2-opt (Add 2 Edges)
E
G
F
A
B
C
D
TSP Video
By poprythum https://www.youtube.com/watch?v=SC5CX8drAtU 17/02/15
Remember Amazon's delivery problem?
Millions of deliveries
Need many - trucks all
different sizes
Drivers to drive
Millions of gallons of
fuel
Not taking into account
warehouse staff, web
staff, etc etc ……
Operational Research





Gives practical solutions to explosive problems
Helps companies make complex operational
decisions
We use heuristic techniques
We employ computer science and mathematical
techniques
We save companies millions of pounds!
Thank you