CS计算机代考程序代写 compiler DNA cache AI ant algorithm Microsoft PowerPoint - CSE101 1 Algorithms.pptx

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

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 solutionWorst-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

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 AT2: 2 AT3: 7 AT4: 8

n! possible solutions

9 2 7 8

13 12 16

CT4: 8
DT3: 9

CT2: 8
DT4: 4

CT4: 8
DT2: 6

CT2: 8
DT3: 9

CT3: 1
DT2: 6

24 26 33 23

… … …

As an exercise, you can work out these
three sub‐trees of the complete
enumeration tree.

CT3: 1
DT4: 4

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.

BT4: 7BT2: 4 BT3: 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

(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

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

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

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.

Knapsack:

Objects:

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

14
16

Knapsack:

Objects:

Weights

Capacity: 24

23 5 20 12 21 Values

O. Braun

55Algorithms and
Optimization
Problems

16
3

0/1 ‐ Knapsack problem

14
16

Knapsack:

Objects:

Capacity: 24

Weights

23 5 20 12 21 Values

O. Braun

56Algorithms and
Optimization
Problems

16
3

0/1 ‐ Knapsack problem

14
16

Total Value: 40

Knapsack:

Objects:

Weights

Capacity: 24

23 5 20 12 21 Values

O. Braun

57Algorithms and
Optimization
Problems

16
3

0/1 ‐ Knapsack problem

14
16

Total Value: 40

Total Value: 41

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.

Knapsack:

Objects:

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

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

O. Braun

63Algorithms and
Optimization
Problems

Complete Enumeration

–

out in

outout

out

Object A
Value: 6
Weight: 1

Object B
Value: 10
Weight: 2

Object C
Value: 12
Weight: 3

inoutout

out

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

–
0 | 0

B
10 | 2

AB
16 | 3

O. Braun

64Algorithms and
Optimization
Problems

Complete Enumeration

–

out in

outout

out

(22,5)
***

(28,6)

Object A
Value: 6
Weight: 1

Object B
Value: 10
Weight: 2

Object C
Value: 12
Weight: 3

inoutout

out

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

–
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

Related Posts