Microsoft PowerPoint – CSE101 1 Algorithms.pptx
O. Braun
1Algorithms and
Optimization
Problems
Algorithms
O. Braun
2Algorithms and
Optimization
Problems
Algorithmic Framework
An algorithm is a method for solving a problem (on a computer).
1. What problem are we solving? problem specification
2. How do we solve the problem? algorithm description
3. Why do these steps solve the problem? proof of correctness
4. When do we get an answer? time analysis
Problem solving = “The Spirit of Computing”, driven by real‐world necessity:
• Logistics
• Scheduling: production planning, resource allocation, …
• Bin Packing: storage on container ships, airline logistics, …
• Shortest paths: warehouses, factory hall, distribution center, roads, …
• DNA Sequencing
• Evolutionary Trees (edit distance, Steiner trees…)
• Finding homologues, evolutionary significance (string‐matching)
• Conformational Analysis
• Drug Design (minimum‐energy configuration)
• Autonomous Robotics, Vehicles
• managing smart highways, collision avoidance / path planning, …
• Design of integrated circuits
• placement, wiring, …
O. Braun
3Algorithms and
Optimization
Problems
Algorithmic problems
Optimization problems:
• Find the schedule with minimum number of delayed jobs
• Find the shortest path from a vertex s to a vertex t in a network
• Find the minimum possible number of bins
• Find the production program that leads to maximum profit
Decision problems (yes or no answer):
• Does there exist a schedule with no more than k delayed jobs?
• Does there exist a path from s to t with length < k?
• Does there exist a packing with no more than k bins?
• Does there exist a production program that results in a profit > k?
O. Braun
4Algorithms and
Optimization
Problems
Algorithmic problems
• An algorithmic problem is defined by:
• input domain n jobs with given processing times and deadlines
• output specification schedule that minimizes the number of delayed jobs
• A problem with the input specified is a problem instance.
n=3, pA=5, pB=8, pC=6, dA=7, dB=10, dC=11
• An algorithm must be effective, i.e. give a correct answer and terminate.
• An algorithm should be efficient time analysis.
O. Braun
5Algorithms and
Optimization
Problems
Algorithmic problems
For a specific optimization goal there are often:
• Upper bounds (“at most this hard, at most this much effort”)
e.g. there is a schedule where u jobs are delayed
we won’t accept a solution where more than u jobs are delayed
• Lower bounds (“at least this hard, at least this much effort”)
e.g. as a result of certain decisions, we know that in the end at least l jobs will be
delayed
We will also consider upper and lower bounds in terms of time analysis of algorithms:
• Upper bounds e.g. no more than u comparisons to sort n numbers
• Lower bounds e.g. at least l comparisons to sort n numbers
Other important concepts are:
• Reductions “solving this problem boils down to solving that problem”
• Intractability “believed impossible to solve efficiently”
O. Braun
6Algorithms and
Optimization
Problems
Continuous vs. discrete
optimization
O. Braun
7Algorithms and
Optimization
Problems
Continuous vs. discrete optimizaion
Can you solve the following problem?
O. Braun
8Algorithms and
Optimization
Problems
Real‐world optimization problems and algorithms
You are the operation manager in your company managing the
re‐organization of the container production. The containers have to be
open on the top, must contain at least 10.00 m3 volume,
and their length must be the double of the height (see diagram).
Material costs for the BASE PLATE are $10.00 per m2,
the SIDEWALLS cost $6.00 per m2.
• Determine the optimal height of a container (in meters and centimeters).
Note that the company can only produce with an accuracy in centimeters.
• Howmuch does that minimal cost container cost?
Remember: A problem is defined by
• input domain / problem instance volume=10, c_Base=10, c_Side=6
• output specification h (in meters and centimeters) such that the container
has at least 10.00 m3 and the total costs are minimized
O. Braun
9Algorithms and
Optimization
Problems
Container example
(Remark: limited to this dpmain just for display reasons)
O. Braun
10Algorithms and
Optimization
Problems
Container example
Practical Solution:
h b=5/(h^2) b Vol=2(h^2)b c(h,b)
1,38 2,62550 2,63 10,02 161,85 €
1,39 2,58786 2,59 10,01 161,57 €
1,40 2,55102 2,56 10,04 161,73 €
1,41 2,51496 2,52 10,02 161,42 €
1,42 2,47967 2,48 10,00 161,08 €
1,43 2,44511 2,45 10,02 161,19 €
1,44 2,41127 2,42 10,04 161,28 €
1,45 2,37812 2,38 10,01 160,89 €
1,46 2,34566 2,35 10,02 160,95 €
1,47 2,31385 2,32 10,03 160,99 €
1,48 2,28269 2,29 10,03 161,02 €
1,49 2,25215 2,26 10,03 161,04 €
1,50 2,22222 2,23 10,04 161,04 €
1,51 2,19289 2,20 10,03 161,03 €
1,52 2,16413 2,17 10,03 161,00 €
1,53 2,13593 2,14 10,02 160,96 €
1,54 2,10828 2,11 10,01 160,90 €
1,55 2,08117 2,09 10,04 161,32 €
1,56 2,05457 2,06 10,03 161,24 €
1,57 2,02848 2,03 10,01 161,14 €
1,58 2,00288 2,01 10,04 161,54 €
1,59 1,97777 1,98 10,01 161,42 €
1,60 1,95313 1,96 10,04 161,79 €
continuous vs. discrete
optimization
O. Braun
11Algorithms and
Optimization
Problems
Time Complexity,
Combinatorial Explosion and
Approximation algorithms
O. Braun
12Algorithms and
Optimization
Problems
Algorithms and Complexity of algorithms
• An algorithm is a method for solving a problem (on a computer) as a
sequence of steps and some algorithms need less steps to solve a certain
problem instance than other algorithms.
• We are interested in the number of steps an algorithm requires in the
worst‐case (i.e. for a problem instance that forces the algorithm to use the
largest possible number of single steps).
• The worst‐case time complexity of an algorithm is the computational effort
of the resource running time. Other resources are space or energy.
• Other types of analysis of algorithms in terms of running time are average‐
case analysis and best‐case analysis.
• The actual running time for each of these steps on a computer system
depends on the Hardware (CPU, climate, cache) and Software
(programming language, compiler).
• We are only interested in the order of magnitude of the running time.
As an example, we want to make a statement that the running time of
an algorithm increases at most quadratically with the input size.
O. Braun
13Algorithms and
Optimization
Problems
Running times of algorithms
O(n!) factorial
O(2n) exponential
O(n2) quadratic
O(n log n) log-linear
O(n) linear
O(log n) logarithmic
O(1) constant
(At least)
exponential time:
• Knapsack
• Partition
• Bin Packing
• Scheduling
• Graph Coloring
(At most)
polynomial time:
• Sorting
• Linear Search
• Merging
• Binary Search
O(nk) polynomial
O. Braun
14Algorithms and
Optimization
Problems
Big O and its relatives
Exercise: Which is true?
O. Braun
15Algorithms and
Optimization
Problems
Time complexity of algorithms
n 25 50 75 100
2n
10-13
Seconds
6
Microsec.
IBM Summit: 200 Peta Flops (02/2020)
The fastest supercomputer in the world IBM Summit performs 200 Peta Flops = 1015
floating point operations per second. This corresponds to the processing power of
more than 500.000 commercial PCs (400 Giga Flops = 109 Flops).
188
Seconds
200
Years
Even if we had a new supercomputer which would have
1000‐fold computing power of IBM Summit,
then this computer would still need the following times to perform
2n
floating point operations:
O. Braun
16Algorithms and
Optimization
Problems
Combinatorial Explosion
25 50 75 100 125 150
n2
3.1.10-18
seconds
1.2 .10-17
seconds
2.8.10-17
seconds
5.0.10-17
seconds
7.8.10-17
seconds
1.1.10-16
seconds
n10
4.7.10-7
seconds
0.4
millisec.
28
millisec.
0.5
seconds
4.6
seconds
28.8
seconds
n15
4.6
seconds
42
hours
773
days
158
years
4506
years
69427
years
n100 10111
years
10142
years
10159
years
10172
years
10181
years
10189
years
2n
10-13
seconds
5.6.10-6
seconds
188
seconds
200
years
109
years
1017
years
n!
22
hours
1036
years
1081
years
10130
years
10181
years
10234
years
O. Braun
17Algorithms and
Optimization
Problems
What to do with hard problems?
Heuristics (Variable Neighborhood Search, Tabu Search, Simulated Annealing,
Ant algorithms, …)
or
Approximation Algorithms
A(I) approximate solution for a problem instance I
OPT(I) optimal solution for a problem instance I of (here as an example) a MINIMIZATION problem
Absolute performance:
Relative performance:
Combined:
Goal is to minimize α and c such that the approximate solution for any problem instance I is as close
as possible to the optimal solutionWorst-case analysis
O. Braun
18Algorithms and
Optimization
Problems
Examples for approximation results
O. Braun
19Algorithms and
Optimization
Problems
What to do with NP‐complete problems?
Unqualified Heuristics = Heuristics
Simulated Annealing: probabilistically decide whether to move to a new solution or stay with the
current one
Tabu Search: make it hard to return to a previous solutions
Ant Algorithms: iteratively move towards a more complete intermediate solution
Cuttlefish Algorithm: mimics the mechanism of color changing behaviour of the cuttlefish to find
global optimal solution
Compact Genetic Algorithm: uses a vector to hold the probability of including each component in the
next solution
Variable Neighborhood Search: look in the neighborhood of a solution and get out of it from time to
time
Benmansour, R., Braun, O., Hanafi, S., The single processor scheduling problem with time restrictions: complexity and related problems,
Journal of Scheduling, DOI 10.1007/s10951-018-0579-8, 2018
O. Braun
20Algorithms and
Optimization
Problems
Algorithms
Assignment Problem
O. Braun
21Algorithms and
Optimization
Problems
Assignment problem
Four students (Julia, Marie, Daniel, Nick) have to accomplish four tasks
(T1, T2, T3, T4). Each student must be assigned to exactly one of the tasks.
The students need different amounts of time to accomplish these tasks.
Question: What task should be assigned to which student such that the total
time needed to complete all four tasks is as small as possible?
the Assignment problem is a MINIMIZATION problem
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
O. Braun
22Algorithms and
Optimization
Problems
Greedy Heuristic (greedy = choose the locally best alternative)
1. Look for the smallest number in the table and assign that person to that task.
2. Delete the corrresponding row and column from the table and repeat Step 1.
Smallest‐Number‐Heuristic
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
O. Braun
23Algorithms and
Optimization
Problems
Smallest‐Number‐Heuristic
1.
2.
3.
4.
Smallest‐Number‐Heuristic:
1+2+4+6=13
Upper Bound UB1 = 13
The optimal solution is for sure
never ever larger than 13,
possibly smaller, but not larger.
Therefore, 13 is an upper bound
of the optimal solution value.
C T3: 1
A T2: 2
D T4: 4
B T1: 6
O. Braun
24Algorithms and
Optimization
Problems
Smallest‐Number‐Heuristic
What to do when there is more than one smallest number?
Rule for this class:
Prefer that agent with the smaller index and if there are more than one tasks with the
same length then prefer that task with the smaller number.
Example:
Tasks
T1 T2 T3 T4
A 1 10 1 10
Agents B 5 4 1 10
C 1 4 4 1
D 10 10 10 1
A T1
B T3
C T4
D T2
O. Braun
25Algorithms and
Optimization
Problems
Find a problem instance where the heuristic fails.
T1 T2
A ? ?
B ? ?
Smallest‐Number‐Heuristic
O. Braun
26Algorithms and
Optimization
Problems
Find a problem instance where the heuristic fails.
T1 T2 Greedy: A‐>T1 (1), B‐>T2(1000)
A 1 2 Optimal solution: A‐>T2(2), B‐>T1(2)
B 2 1000 The Smallest‐Number‐Heuristic can be
arbitrarily bad, i.e. the ratio (Greedy/OPT)
can be arbitrarily large.
Smallest‐Number‐Heuristic
O. Braun
27Algorithms and
Optimization
Problems
Complete Enumeration
Complete Enumeration enumerates all possible solutions.
It works for small problem instances but not for large instances (if the
number of possible solutions grows exponentially with the input size).
O. Braun
28Algorithms and
Optimization
Problems
Complete Enumeration
A T1: 9 AT2: 2 AT3: 7 AT4: 8
n! possible solutions
9 2 7 8
13 12 16
30
CT4: 8
DT3: 9
CT2: 8
DT4: 4
CT4: 8
DT2: 6
CT2: 8
DT3: 9
CT3: 1
DT2: 6
24 26 33 23
… … …
As an exercise, you can work out these
three sub‐trees of the complete
enumeration tree.
CT3: 1
DT4: 4
18
Last level: If e.g. (C) Daniel does T3, then
the only remaining task for Nick is T4.
That‘s why on the last level there are always
the last two remaining assignments.
BT4: 7BT2: 4 BT3: 3
If (A) Julia does T1,
then (B) Marie can
only do T2 or T3 or
T4.
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
O. Braun
29Algorithms and
Optimization
Problems
Complete Enumeration
How many vertices are constructed with Complete Enumeration?
n=2 2
n=3 9
n=4 40
n=5 205
General case?
O. Braun
30Algorithms and
Optimization
Problems
Branch‐And‐Bound
We always start with a feasible solution that has to be found (in all of the exam
questions) with the Smallest‐Number‐Heuristic. This value gives an upper bound on the
optimal solution value as we will clearly not accept a solution with a larger value than
this upper bound (the Assignment problem is a minimization problem!). The hope is to
possibly find a solution with a better, i.e. smaller, total value of the assignment times.
The idea for a Branch‐And‐Bound algorithm is to use the structure of a Complete
Enumeration tree where at each node a lower bound and possibly an upper bound has
to be computed.
What is a lower bound? A lower bound is a value about that we can the following say:
In this part of the tree no solution will have a smaller value than this lower bound,
i.e. all solutions in this part of the tree need at least these lower bound ‐many time
units to solve the Assignment problem.
Then it is clear that we can cross out that part of the tree as soon as the lower bound is
larger or equal to the best (i.e. smallest) upper bound we have computed so far.
O. Braun
31Algorithms and
Optimization
Problems
Too abstract?
Wait a minute,
here are some examples.
O. Braun
32Algorithms and
Optimization
Problems
Branch‐And‐Bound: Idea
Upper Bound = actual value (e.g. achieved by a
heuristic: „a definitely possible result“)
Lower Bound = smallest, possibly achievable total
sum („it doesn‘t go any better than that“)
Row‐Min „if each agent could do what he/she can
do best“
Given that (A) Julia performs task T1, any solution in this part of the
tree cannot be better than 9. Therefore, 9 is a lower bound on the solution
values in this part of the tree.
But we actually can determine a better, i.e. larger, lower bound:
(B) Marie, (C) Daniel, and (D) Nick have also to perform tasks.
Marie needs at least 3 time‐units (min of 4, 3, 7),
Daniel needs at least 1 time‐unit (min of 8, 1, 8), and
Niclas needs at least 4 time‐units (min of 6, 9, 4).
This brings our lower bound to 17 and we can cross out that vertex and that
whole part of the tree as all solutions in this part of the tree have a
solution value > 17, but we have found already a solution value of only 13
with the Smallest‐Number‐Heuristic.
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
O. Braun
33Algorithms and
Optimization
Problems
Lower Bounds
Remark: Obviously, Column‐Min („if each task could be done in minimal
possible time“)
would as well be a possibility to determine lower bounds and we can choose
either Row‐Min or Column‐Min or the maximum of those two values to
determine Lower Bounds.
When bound?
Whenever
Lower Bound („it doesn‘t go any better than that“)
>
Upper Bound („a definitely possible result“).
O. Braun
34Algorithms and
Optimization
Problems
Implementation
How would you implement the search for the row‐min?
What is the running time?
O. Braun
35Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
(A) Julia gets task T1, therefore (A) Julia and T1 are out of the game.
Given that T1 is assigned to (A) Julia, we have the following situation:
(B) Marie has to perform either T2, or T3, or T4 and needs at least min{4,3,7}=3 time units.
(C) Daniel has to perform either T2, or T3, or T4 and needs at least min{8,1,8}=1 time units.
(D) Nick has to perform either T2, or T3, or T4 and needs at least min{6,9,4}=4 time units.
We can conclude that no solution in this subtree can be better than 17, the lower bound is 17. As we
have already a solution with only 13 time‐units (upper bound UB1=13), we can cross out that vertex.
O. Braun
36Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
(A) Julia gets task T2, therefore (A) Julia and T2 are out of the game.
Given that T2 is assigned to (A) Julia, we have the following situation:
(B) Marie has to perform either T1, or T3, or T4 and needs at least min{6,3,7}=3 time units.
(C) Daniel has to perform either T1, or T3, or T4 and needs at least min{5,1,8}=1 time units.
(D) Nick has to perform either T1, or T3, or T4 and needs at least min{7,9,4}=4 time units.
We can conclude that no solution in this subtree can be better than 10, the lower bound is 10. The
currently best solution has 13 time‐units (upper bound UB1=13), so we cannot cross out that vertex
as we might find a solution with a smaller total value in this subtree.
O. Braun
37Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
(A) Julia gets task T2, therefore (A) Julia and T2 are out of the game.
Given that T2 is assigned to (A) Julia, we have the following situation:
(B) Marie has to perform either T1, or T3, or T4 and needs at least min{6,3,7}=3 time units.
(C) Daniel has to perform either T1, or T3, or T4 and needs at least min{5,1,8}=1 time units.
(D) Nick has to perform either T1, or T3, or T4 and needs at least min{7,9,4}=4 time units.
We can conclude that no solution in this subtree can be better than 10, the lower bound is 10. The
currently best solution has 13 time‐units (upper bound UB1=13), so we cannot cross out that vertex
as we might find a solution with a smaller total value in this subtree.
In this case, we always want to compute an upper bound with the
smallest number heuristic, GIVEN THAT (in this problem instance)
(A) Julia gets task T2. The SNH for the remaining agents and
tasks gives (C) Daniel ‐> T3 (1), Nick‐>T4 (4), Marie‐>T1 (6)
with a total value of A2+C1+D4+B6=13.
If this upper bound is better (i.e. strictly smaller) than the
currently best (i.e. smallest) upper bound, we replace the upper
bound and test all lower bounds of those vertices that have not
been crossed out yet if their lower bound is > this new upper
bound. If it is, we can cross out that vertex.
O. Braun
38Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
(A) Julia gets task T3, therefore (A) Julia and T3 are out of the game.
Given that T3 is assigned to (A) Julia, we have the following situation:
(B) Marie has to perform either T1, or T2, or T4 and needs at least min{6,4,7}=4 time units.
(C) Daniel has to perform either T1, or T2, or T4 and needs at least min{5,8,8}=5 time units.
(D) Nick has to perform either T1, or T2, or T4 and needs at least min{7,6,4}=4 time units.
We can conclude that no solution in this subtree can be better than 20, the lower bound is 20. As we
have already a solution with only 13 time‐units (upper bound UB1=13), we can cross out that vertex.
O. Braun
39Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
(A) Julia gets task T4, therefore (A) Julia and T4 are out of the game.
Given that T4 is assigned to (A) Julia, we have the following situation:
(B) Marie has to perform either T1, or T2, or T3 and needs at least min{6,4,3}=3 time units.
(C) Daniel has to perform either T1, or T2, or T3 and needs at least min{5,8,1}=1 time units.
(D) Nick has to perform either T1, or T2, or T3 and needs at least min{7,6,9}=6 time units.
We can conclude that no solution in this subtree can be better than 18, the lower bound is 18. As we
have already a solution with only 13 time‐units (upper bound UB1=13), we can cross out that vertex.
O. Braun
40Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
The only possibility to improve the currently best upper bound is to branch at the second vertex.
We do this recursively in the same way as we did before, but this time with a 3×3 matrix (Marie,
Daniel, Nick are the remaining agents, and T1, T3, T4 are the remaining tasks).
O. Braun
41Algorithms and
Optimization
Problems
Branch‐And‐Bound
T1 T2 T3 T4
(A) Julia 9 2 7 8
(B) Marie 6 4 3 7
(C) Daniel 5 8 1 8
(D) Nick 7 6 9 4
All vertices are crossed out. The greedy solution with the
Smallest‐Number‐Heuristic was for this problem instance the
optimal solution with a total of 13 time‐units.
O. Braun
42Algorithms and
Optimization
Problems
Mathematical Program
T1 T2 T3 … Tj … Tn
A1
A2
A3
…
Ai cij
…
An
O. Braun
43Algorithms and
Optimization
Problems
Hungarian algorithm
Remark:
There is a polynomial‐time algorithm to solve the Assignment problem optimally.
H. W. Kuhn (1955):
The Hungarian method for the assignment problem,
Naval Research Logistics Quarterly 2, 83–97
J. Munkres (1957):
Algorithms for the Assignment and Transportation Problems,
Journal of the Society of Industrial and Applied Mathematics 5, 32–38
O. Braun
44Algorithms and
Optimization
Problems
In the following
there are two
sample questions
and solutions.
We start with the
same problem
that we had before.
O. Braun
45Algorithms and
Optimization
Problems
Problem 1
O. Braun
46Algorithms and
Optimization
Problems
Problem 1: Solution (Smallest‐Number‐Heuristic)
C T3: 1
A T2: 2
D T4: 4
B T1: 6
1.
2.
3.
4.
Smallest‐Number‐Heuristic:
1+2+4+6=13
Upper Bound UB1 = 13
O. Braun
47Algorithms and
Optimization
Problems
Problem 1: Solution (Branch‐And‐Bound)
Remark: The vertices are always constructed from the left to the right, one after the other and
level‐by‐level, i.e. we perform a kind of a Breadth‐First‐Search.
O. Braun
48Algorithms and
Optimization
Problems
Problem 2
O. Braun
49Algorithms and
Optimization
Problems
Problem 2: Solution (Smallest‐Number‐Heuristic)
B T1: 3
A T2: 6
D T4: 7
C T3: 11
1.
2.
3.
4.
Smallest‐Number‐Heuristic:
3+6+7+11 = 27
Upper Bound UB1 = 27
O. Braun
50Algorithms and
Optimization
Problems
Problem 2: Solution (Branch‐And‐Bound)
O. Braun
51Algorithms and
Optimization
Problems
Problem 2: Solution (Branch‐And‐Bound)
New upper bound! This vertex is vertex #6 that is
computed. From vertices 1, …, 5 there are only the
two vertices #2 (with LB=24) and #5 (with LB=25)
open, i.e. not crossed out yet.
Both LB are smaller than 26, therefore we cannot
cross out these vertices.
O. Braun
52Algorithms and
Optimization
Problems
Knapsack
Problem
O. Braun
53Algorithms and
Optimization
Problems
0/1 ‐ Knapsack problem
0/1‐Knapsack problem:
You can take an object at most 1
time.
No fractions allowed.
16
10
3
14
Knapsack:
Objects:
3
23 5 20 12 21 Values
Weights
Capacity: 24
Applications:
• home energy management
• cognitive radio networks
• resource management in software r
• Relay selection in secure cooperative
wireless communication
• production planning
• cognitive radio networks
• 5G mobile edge computing
• selection of renovation actions
• secure cooperative wireless communication
• optimizing power allocation to electrical
appliances
• offloading in wireless multi-hop networks
• network selection for mobile nodes
• plastic bags waste management
O. Braun
54Algorithms and
Optimization
Problems
16
3
0/1 ‐ Knapsack problem
10
3
14
16
3
Knapsack:
Objects:
Weights
Capacity: 24
23 5 20 12 21 Values
O. Braun
55Algorithms and
Optimization
Problems
16
3
0/1 ‐ Knapsack problem
10
3
14
16
3
10
Knapsack:
Objects:
Capacity: 24
Weights
23 5 20 12 21 Values
O. Braun
56Algorithms and
Optimization
Problems
3
16
3
0/1 ‐ Knapsack problem
10
3
14
16
3
Total Value: 40
Knapsack:
Objects:
Weights
Capacity: 24
23 5 20 12 21 Values
O. Braun
57Algorithms and
Optimization
Problems
3
16
3
0/1 ‐ Knapsack problem
10
3
14
16
3
Total Value: 40
16
3
10
12
14
3
Total Value: 41
10
14
23 5 20 12 21
Capacity: 24
Knapsack:
Objects:
Weights
Capacity: 24
23 5 20 12 21 Values
O. Braun
58Algorithms and
Optimization
Problems
Mathematical program
0/1‐Knapsack problem:
You can use an object at most 1 time.
No fractions allowed.
16
10
3
14
Knapsack:
Objects:
3
23 5 20 12 21 Values
Weights
Capacity: 24
i 1 2 3 4 5
values vi
weights wi
capacity c
x* = (0,0,1,0,1)
O. Braun
59Algorithms and
Optimization
Problems
Complete Enumeration
Objects Values Weights
A (Cash) v1 = 6 Mio $ w1 = 1
B (Jewellery) v2 = 10 Mio $ w2 = 2
C (Paintings) v3 = 12 Mio $ w3 = 3
Capacity of the
knapsack: c=5
You could pack only object A or objects A and B, and so on.
How many solutions are there to this problem
a) for n=3 objects?
b) for n objects?
O. Braun
60Algorithms and
Optimization
Problems
Complete Enumeration
Objects Values Weights
A (Cash) v1 = 6 Mio $ w1 = 1
B (Jewellery) v2 = 10 Mio $ w2 = 2
C (Paintings) v3 = 12 Mio $ w3 = 3
Capacity of the
knapsack: c=5
You could pack only object A or objects A and B, and so on.
How many solutions are there to this problem
a) for n=3 objects? 23=8
b) for n objects? 2n
O. Braun
61Algorithms and
Optimization
Problems
Complete Enumeration
out inObject A
Value: 6
Weight: 1
Capacity of the knapsack: c=5
A
6 | 1
–
0 | 0
value
weight
O. Braun
62Algorithms and
Optimization
Problems
Complete Enumeration
out in
out in
Object A
Value: 6
Weight: 1
Object B
Value: 10
Weight: 2
out in
Capacity of the knapsack: c=5
A
6 | 1
AB
16 | 3
B
10 | 2
A
6 | 1
–
0 | 0
–
0 | 0
O. Braun
63Algorithms and
Optimization
Problems
Complete Enumeration
–
out in
outout
out
in
in
Object A
Value: 6
Weight: 1
Object B
Value: 10
Weight: 2
Object C
Value: 12
Weight: 3
inoutout
out
in
in
in
Capacity of the knapsack: c=5
A
6 | 1
AB
16 | 3
ABC
28 | 6
B
10 | 2
BC
22 | 5
C
12 | 3
AC
18 | 4
A
6 | 1
A
6 | 1
–
0 | 0
–
0 | 0
–
0 | 0
B
10 | 2
AB
16 | 3
O. Braun
64Algorithms and
Optimization
Problems
Complete Enumeration
–
out in
outout
out
in
in
(22,5)
***
(28,6)
Object A
Value: 6
Weight: 1
Object B
Value: 10
Weight: 2
Object C
Value: 12
Weight: 3
inoutout
out
in
in
in
Capacity of the knapsack: c=5
A
6 | 1
AB
16 | 3
ABC
28 | 6
B
10 | 2
BC
22 | 5
C
12 | 3
AC
18 | 4
A
6 | 1
A
6 | 1
–
0 | 0
–
0 | 0
–
0 | 0
B
10 | 2
AB
16 | 3
O. Braun
65Algorithms and
Optimization
Problems
Complete Enumeration
a) How many leaves are constructed?
b) How many vertices in total?
O. Braun
66Algorithms and
Optimization
Problems
Complete Enumeration
a) How many leaves are constructed? 2n
b) How many vertices in total? 2n + 2n-1 + 2n-2 + … + 21 = 2n+1-2
O. Braun
67Algorithms and
Optimization
Problems
Heuristic
Capacity: c=122
A B C D E
values 90 60 70 80 63
weights 60 30 35 50 36
Develop your own heuristic algorithm to solve this problem.
Describe your algorithm as precisely as possible.
O. Braun
68Algorithms and
Optimization
Problems
Largest‐Relative‐Value‐Heuristic
Capacity: c=122
A B C D E
values 90 60 70 80 63
weights 60 30 35 50 36
Greedy Heuristic „Largest‐Relative‐Value“ [Dantzig 1957]
1. Sort the objects in non‐increasing order of their relative values vi / wi.
2. Pack the object with the largest relative value in the knapsack and
delete it from the list (if this object does not fit in the knapsack,
try the next object of the list).
3. Repeat Step 2 until no objects are left.
O. Braun
69Algorithms and
Optimization
Problems
Largest‐Relative‐Value‐Heuristic
Capacity: c=122
A B C D E
values 90 60 70 80 63
weights 60 30 35 50 36
Greedy Heuristic „Largest‐Relative‐Value“ [Dantzig 1957]
1. Sort the objects in non‐increasing order of their relative values vi / wi.
2. Pack the object with the largest relative value in the knapsack and
delete it from the list (if this object does not fit in the knapsack,
try the next object of the list).
3. Repeat Step 2 until no objects are left.
B C E D A
values 60 70 63 80 90
weights 30 35 36 50 60
relative values 2.0 2.0 1.75 1.6 1.5
O. Braun
70Algorithms and
Optimization
Problems
Largest‐Relative‐Value‐Heuristic
Capacity: c=122
A B C D E
values 90 60 70 80 63
weights 60 30 35 50 36
Greedy Heuristic „Largest‐Relative‐Value“ [Dantzig 1957]
1. Sort the objects in non‐increasing order of their relative values vi / wi.
2. Pack the object with the largest relative value in the knapsack and
delete it from the list (if this object does not fit in the knapsack,
try the next object of the list).
3. Repeat Step 2 until no objects are left.
B C E
values 60 70 63 = 193
weights 30 35 36 = 101 (no space left for any other object)
Important remark: Not necessarily only the first k objects are chosen with this heuristic.
Try to pack additional objects in the knapsack as long you can find an object that still fits in the knapsack.
O. Braun
71Algorithms and
Optimization
Problems
Largest‐Relative‐Value‐Heuristic
Find a problem instance where the Largest‐Relative‐Value‐Heuristic fails.
O. Braun
72Algorithms and
Optimization
Problems
Largest‐Relative‐Value‐Heuristic
Find a problem instance where the Largest‐Relative‐Value‐Heuristic fails.
O. Braun
73Algorithms and
Optimization
Problems
How to branch?
Branch: Take at first that object with the largest value. Then use Breadth‐First‐
Search.
Example:
C is the object with the largest value (12), followed by B (10), and finally C (6).
Remarks:
1. There are other Selection Rules such as „Ban at first tht object with the largest weight“ and so
on. In this class, we only use „Take at first that object with the largest value“.
2. There are other Graph Traversal Strategies like „Depth‐First‐Search“ of „Best‐First‐Search“.
In this class, we only use „Breadth‐First‐Search“.
O. Braun
74Algorithms and
Optimization
Problems
Upper Bound
Compute an Upper bound („it doesn‘t go any better than that“) with the
Largest‐Relative‐Values‐Strategy:
• Add all the values of the items that are already definitely in the knapsack.
• Take the remaining objects (that are not banned yet) in the order of their
relative values (i.e. value / weight) and put them in the virtual knapsack until
the first object does not fit anymore.
• Add the portion of that first object that does not fit anymore in the
knapsack,
such that the knapsack would be 100% full.
O. Braun
75Algorithms and
Optimization
Problems
Bound
Only if the upper bound is greater than the currently largest lower bound:
Compute a Lower bound („a definitely possible result“) as follows:
• Add all the values of the items that are already definitely in the knapsack.
• Apply the Largest‐Relative‐Value‐Heuristic to the remaining objects
(that are not banned yet).
O. Braun
76Algorithms and
Optimization
Problems
When can we cross out a vertex?
When bound?
1. If the object does not fit in the knapsack anymore.
2. If there are no objects left.
3. If the upper bound (i.e. the best possibly achievable value) is smaller than
the largest lower bound.
O. Braun
77Algorithms and
Optimization
Problems
MAX (Knapsack) MIN (Assignment)
Lower
Bounds
Largest actually possible value
(„a definitely possible result“)
Smallest possibly achievable value
(„it doesn‘t go any better than that“)
Upper
Bounds
Largest possibly achievable value
(„it doesn‘t go any better than that“)
Smallest already achieved value
(„a definitely possible result“)
Bound Upper Bound ≤
Largest Lower Bound
Lower Bound ≥
Smallest Upper Bound
no objects left, capacity
Knapsack vs. Assignment
O. Braun
78Algorithms and
Optimization
Problems
Example Problem
O. Braun
79Algorithms and
Optimization
Problems
Example Problem
O. Braun
80Algorithms and
Optimization
Problems
Example Problem
O. Braun
81Algorithms and
Optimization
Problems
Example Problem: Sample Solution