University of Zagreb, Croatia

Lecture 4.a
Heuristic Optimization Methods:
Greedy Algorithms
Slides prepared by Nina Skorin-Kapov and Lea Skorin-
Kapov

Academic year 2020/2021

Graduate Studies Programme
 Outline
University of Zagreb, Croatia

 General concepts of greedy algorithms

 Examples:

 Knapsack problem
 MST – minimum spanning tree problem
 TSP – travelling salesman problem
 SAT – satisfiability problem
 GC - Graph coloring problem

Zavod za telekomunikacije 2
 Optimization methods
University of Zagreb, Croatia

Exact Approximate
A*
methods methods
Simplex- Constraint
based for LP programming Approximation
algorithms
Heuristic
Branch and Bound, Dynamic
Cut , Price (B&B, programming algorithms
B&C, B&P)

Improvement (meta)heuristics
Constructive heuristics
• Local search
• Greedy algorithms
•Nature inspired
• Tabu search, Genetic
Hybrid methods
algorithms, Simmulated
• GRASP Annealing, Ant colony
•Problem specific
heuristics

Zavod za telekomunikacije 3
 Greedy algorithms
University of Zagreb, Croatia

 Constructive heuristic
 Always start from an empty solution and
construct a complete solution by assigning
values to decision variables one at a time
 In each step, it assigns a value to a decision
variable which contributes most to the objective
function, i.e. has the maximal profit in that step
 Hence the name ‘Greedy’
 No backtracking: once a decision variable is
assigned a value, it is never changed

Zavod za telekomunikacije 4
 Advantages
University of Zagreb, Croatia

 SIMPLICITY
 Usually the rules to assign the next decision variable
are easy to design and intuitive
 Usually easy to implement

 Generally, they are faster and less complex

than improvement algorithms and ends
deterministically

 Very common approach

Zavod za telekomunikacije 5
 Drawbacks
University of Zagreb, Croatia

 Local or myopic view does not guarantee good

global solutions
 Local optimality does not implicate global optimality
 This often decreases their performance

 Solution quality very dependent on problem

instance – hard to make a robust algorithm for
all problem instances

 Must run the algorithm to the end to get a

complete solution
Zavod za telekomunikacije 6
 Basic design issues
University of Zagreb, Croatia

 Basic design issues:

 Solution representation: define the elements which
comprise the solution, i.e. define a potential solution
as a set of elements so subsets can represent partial
solutions
 The selection method/heuristic in each constructive
greedy step
 Usually chooses the best element from the current list of
possible elements which contributes most
(maximizes/minimizes) the objective function, i.e., has the
largest profit
 The heuristic calculates the profit of each potential element

Zavod za telekomunikacije 7
 The greedy step
University of Zagreb, Croatia

 The heuristic to guide the greedy step can be:

 Static:the profit is calculated once at the beginning

and doesn't change
 e.g. knapsack greedy algorithm

 Dynamic: the profit is recalculated (updated) after

each step
 e.g. Minimum spanning tree greedy algorithm

Zavod za telekomunikacije 8
 Generic greedy algorithm
University of Zagreb, Croatia

Begin with empty solution set

do
Choose a solution element, i.e. assign a decision
variable, which brings maximal profit to the objective
while keeping feasibility
while solution is incomplete

Zavod za telekomunikacije 9
 Example: Knapsack problem
University of Zagreb, Croatia

 Given are 4 objects and a knapsack of size

C=9 units.
 Each object has value vi and size ci.
 Objective: Find the subset of object which fit in
the knapsack and have the maximal total value

v1=8 c1=9
v2=6 c2=5
v3=3 c3=3
v4=2 c4=1

Zavod za telekomunikacije 10
 Example: greedy approach for Knapsack
University of Zagreb, Croatia

 Greedy approach: In each step take the most valuable

object which fits
 Static greedy step heuristic – the value vi of an object
represents its profit, i.e., its contribution to the objective
function, and is always the same (doesn't have to be
updated)
 In this case, we would take only object 1; Total value:
v1=8, with capacity c1=9
v1=8 c1=9
v2=6 c2=5
v1=8 c1=9
v3=3 c3=3
v4=2 c4=1

Zavod za telekomunikacije 11
 Example: drawback of local view
University of Zagreb, Croatia

v1=8 c1=9
v2=6 c2=5 Greedy solution
Total value: v1=8 v1=8 c1=9
v3=3 c3=3
Total capacity: c1=9
v4=2 c4=1

A better feasible solution could be

obtained by choosing any other v2=6 c2=5
object first
v3=3 c3=3
Total value: v2+v3+v4=11
Total capacity: c2+c3+c4=9 v4=2 c4=1

Zavod za telekomunikacije 12
 Example: Private telephone network
University of Zagreb, Croatia

A bank has several local offices within a region and wants to

connect their local offices with their central office with a
private telephone network

Zavod za telekomunikacije 13
 Example: Private telephone network
University of Zagreb, Croatia

The telecom operator offers prices for connecting each pair of

offices proportional to their mutual distance

Zavod za telekomunikacije 14
 Example: Private telephone network
University of Zagreb, Croatia

Example approach: connect directly to central office

Expensive!
Zavod za telekomunikacije 15
 Example: Private telephone network
University of Zagreb, Croatia

Cheaper approach: Minimum spanning tree - minimize cost

Zavod za telekomunikacije 16
 Example: Kruskal’s algorithm for MST
University of Zagreb, Croatia

 MST: minimum spanning tree

 Given a weighted graph, a MST is a tree which
connects all nodes in the graph at minimal cost

 Kruskal’s algorithm:
1. Sort all edges according to weight from smallest to
biggest
2. Always add the edge with the smallest weight such
that it doesn’t form a loop until there are n-1 edges
in the tree
 OPTIMAL!
Zavod za telekomunikacije 17
 Example - Kruskal’s algorithm for MST
University of Zagreb, Croatia

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
Sorted edges:
6 1 e3 =4 e7=3
5 4 e10 =6 e3=4
e2
=5

3
4 7 e11=4
e7 =

e 9=
3

6
3
2=
e5=4
6

2 e8 = e1
5 e2=5 Makes cycle
1 6
e1=10

e4 =7

0
e8=5
=8

e9=6 Makes cycle

1=

-1
e6

e1

-2 5 e10=6 Solution has

-3 2 e 5=4 e12=6 n-1 edges
-4 e4=7 →done!
-5 e6=8
-6 n=7 nodes e1=10
Solution: n-1 edges

Zavod za telekomunikacije 18
 Example: Traveling Salesman Problem
University of Zagreb, Croatia

 Given n cities and their mutual distances, find

the shortest tour which visits each city once,
and only once (Hamiltonian cycle), and returns
to the original starting point.
 (n-1)! possible tours
Example application: circuit
2 manufacturing -
A B determining the best order in
which a laser will drill
thousands of holes (i.e.
3 4 1 3 planning the most efficient
motion of a robotic arm) in n
C D points on the surface of a VLSI
2 chip.

Zavod za telekomunikacije 19
 Example TSP
University of Zagreb, Croatia

 Greedy Travelling Salesman Problem

algorithms
 Greedy algorithm 1: ‘Nearest neighbor’: choose a
city at random and then always choose the city
closest not yet visited. If all cities are visited, return
to starting city
 Dependent on starting city
 Dynamic (the distance to the remaining nodes are updated
to be from the current node in each step)
 Greedy algorithm 2: Choose the shortest edge
avoiding those where cities are end nodes to more
than 2 edges. Stop when n-1 edges are chosen
 Static (the distances of the edges are not updated during
the process)
Zavod za telekomunikacije 20
 Example TSP
University of Zagreb, Croatia

Greedy algorithm 1: ‘Nearest neighbor’: choose a city at

random and then always choose the city closest not yet visited.
If all cities are visited, return to starting city
Dependent on starting city
Start node C:
A 2 B C-A-D-B-C:
distance=15
3 4 1 7
Start node A:
A-D-C-B-A:
C D distance=11
4

Zavod za telekomunikacije 21
 Example TSP
University of Zagreb, Croatia

Greedy algorithm 2: Choose the shortest edge avoiding those

where cities are end nodes to more than 2 edges; choose an edge
such that at least one node does not have any edge assigned
already. Stop when n-1 edges are chosen, and then close the
loop.
2 Sorted Edges:
A B A-D
A-B Node A has more than
3 4 7 A-C 2 edges
1
C-D
C D B-C
4 B-D

Solution: A-B-C-D-A: distance=11

Zavod za telekomunikacije 22
 Satisfiability problem (SAT)
University of Zagreb, Croatia

 SAT: Find a Boolean expression, can the

variables be assigned in such a way as to
make the formula evaluate to TRUE
 Decision problem

 Example:

• YES: truth assignments that satisfy

(a=0,b=1,c=0)
(a=1,b=1,c=1)
(a=1,b=0,c=0)

Zavod za telekomunikacije 23
 Example - Greedy approach for SAT
University of Zagreb, Croatia

 Greedy approach: for each variable in random

order, assign a truth value that results in
satisfying the greatest number of currently
unsatisfied clauses. If there are multiple such
cases, choose randomly.

 Dynamic greedy decision heuristic: depending on

previously assigned variables, the number of
(un)satisfied clauses of the variables change

Zavod za telekomunikacije 24
 Example- Greedy approach for SAT
University of Zagreb, Croatia

Example:
x1  ( x1  x2 )  ( x1  x3 )

If x1 is considered first:
If x1=TRUE it satisfies 2 clauses
If x1=FALSE it satisfies 1 clause
The greedy algorithm would assign x1=TRUE.
However, the first clause would always be FALSE and thus
the formula will never be TRUE→ NO SOLUTION

Zavod za telekomunikacije 25
 Example- Greedy approach for SAT
University of Zagreb, Croatia

Example:
x1  ( x1  x2 )  ( x1  x3 )
Suppose the order of nodes considred is: x2, x3, x1
For x2: if x2 =T→ 1 clause satisfied; if x2 =F→ 0 clauses satisfied
Set x2 =TRUE; Clause ( x1  x2 ) is now satisfied (no longer
considered)
For x3: if x3 =T→ 1 clause satisfied; if x3 =F→ 0 clauses satisfied
Set x3 =TRUE; Clause ( x1  x3 ) is now satisfied (no longer
considered)
For x1: if x1 =T→ 0 clauses satisfied (clauses ( x1  x2 ) and ( x1  x3 )
are no longer considered); if x1 =F→ 1 clause satisfied
Set x1 =FALSE;
Zavod za telekomunikacije 26
 Example- Greedy approach for SAT
University of Zagreb, Croatia

Example:
x1  ( x1  x2 )  ( x1  x3 )
Suppose the order of nodes considred is: x2, x3, x1
For x2: if x2 =T→ 1 clause satisfied; if x2 =F→ 0 clauses satisfied
Set x2 =TRUE; Clause ( x1  x2 ) is now satisfied (no longer
considered)
Dynamic
For x3: if x3 =T→ 1 clause greedyifdecision
satisfied; x3 =F→ 0 clauses satisfied
Set x3 =TRUE; Clause ( x1  x3 )The
heuristic! is number of (no longer
now satisfied
considered) clauses for x1 changed!
For x1: if x1 =T→ 0 clauses satisfied (clauses ( x1  x2 ) and ( x1  x3 )
are no longer considered); if x1 =F→ 1 clause satisfied
Set x1 =FALSE;
Zavod za telekomunikacije 27
 Example: Graph coloring (GC)
University of Zagreb, Croatia

 Given a graph, color its nodes with the

minimum number of colors such that no two
adjacent nodes share the same color
 Example application: wavelength assignment
1

5 2

colors = 3
4 3

Zavod za telekomunikacije 28
Example: Wavelength assignment
University of Zagreb, Croatia

Wavelength-routed WDM
optical network
LD4 1
LD1

2 4 5 2

1 LD5 LD2
LD3
6
4 3 W=3
3 5
Conflict graph:
Physical topology (optical fibers)
and routing scheme of lightpaths Nodes=connections
(all-optical connections) Links=connections which
Wavelength clash constraint cannot use the same
wavelength (share optical
Wavelength continuity constraint fibers)
Zavod za telekomunikacije 29
 Example: Greedy approach to GC
University of Zagreb, Croatia

 Greedy approach: considers nodes in a specific

order and assigns to each the smallest
available color not used by its neighbors. If
necessary, add a new color.
 Highly depends on chosen ordering
 Dynamic greedy evaluation: the fitness (or feasibility)
of a color depends on currently colored nodes

Zavod za telekomunikacije 30
 Example: Greedy approach to GC
University of Zagreb, Croatia

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6

6 1 e3 =4
5 4 e10 =6 Color 1
Ordering of
e2
=5

3
4 7
e7 =

considered Color 2
e 9=
3

6
3
2=
nodes:
6

2 e8 = e1
5 1,2,3,4,5,6,7 Color 3
1 6
e1=10

e4 =7

0 4 COLORS
=8

1=
4

-1 Color 4
e6

e1

-2 5
-3 2 e 5=4
-4
-5
-6

Zavod za telekomunikacije 31
 Example: Greedy approach to GC
University of Zagreb, Croatia

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6

6 1 e3 =4
5 4 e10 =6
e2
=5

3
4 7
e7 =

e 9=
3

6
3
2=
6

2 e8 = e1
5
1 6
e1=10

e4 =7

0
=8

Color 1
1=

-1
e6

e1

-2 5
Ordering of
considered Color 2
-3 2 e 5=4
-4 nodes:
Color 3
-5 7,6,5,4,3,2,1
-6
3 COLORS
Zavod za telekomunikacije 32
 An Event Scheduling Problem
University of Zagreb, Croatia

 Given: Events with starting and finishing times

 Feasible solutions: A set of events that do not

overlap.

 Objective: maximize the number of events

scheduled.

 Example application: Scheduling lectures in

lecture halls.
Zavod za telekomunikacije 33
 Example Greedy approaches
University of Zagreb, Croatia

 Greedy criterion: schedule the shortest event

first
 Motivation: more events may fit

Greedy=Optimal
Greedy

Greedy
Optimal

Zavod za telekomunikacije 34
 Example Greedy approaches
University of Zagreb, Croatia

 Greedy criterion: schedule the earliest event

first
 Motivation: better utilization – start using
available time as soon as possible

Greedy=Optimal
Greedy

Greedy
Optimal
Zavod za telekomunikacije 35
 Example Greedy approaches
University of Zagreb, Croatia

 Greedy criterion: schedule the event with least

conflictions
 Motivation: allows more events which can still
potentialy be scheduled

Greedy = Optimal

Greedy
Optimal

Zavod za telekomunikacije 36
 University of Zagreb, Croatia

Example of applying greedy algorithms:

HMO project from 2014/2015

Zavod za telekomunikacije 37
 Vehicle routing
University of Zagreb, Croatia

Vehicle routing Depot

Depot
problem (VRP)

Zavod za telekomunikacije 38
 Capacitated Vehicle Routing Problem with
Multiple Depots
University of Zagreb, Croatia

 Multiple potential depots can be used to

serve customers.

 Task: find the depots and constructed routes

that respect the capacity constraints of each
Depot 1
route, so as to visit each customer exactly
once and minimize overall costs.

 Objective: Find which depots should be

opened and construct routes such that
overall costs are minimized. Depot 2

Zavod za telekomunikacije 39
 Capacitated Vehicle Routing Problem with
Multiple Depots
University of Zagreb, Croatia

 We are given a directed graph G = (V, A, C).

 Given a set of V nodes that consists of a subset of I nodes, size m, as

possible depot locations, and a subset J=V/I of nodes that represent
customers. Subset I represents potential starting and ending nodes
(depots). All other nodes represent customers with a fixed capacity
demand.

 The weight of edge a = (i, j) from the set of edges A is given as Ca. For
each depot i∈I , the capacity of the depot is Wi and the cost of opening
the depot is Oi. Each customer j∈J has a capacity demand of dj. We are
given a set of K identical vehicles, each with a capacity of Q. Each
chosen vehicle has a fixed cost of F and can only execute one route,
i.e., it visits a subset of customers and returns back to the depot where
it started the route from.

Zavod za telekomunikacije 40
 Capacitated Vehicle Routing Problem with
Multiple Depots
University of Zagreb, Croatia

 Example problem instance: 105 nodes, 5 depots, 100 customers

Potential solution
with 3 of 5 depots
opened

Potential depots (the rest are customers)

Zavod za telekomunikacije 41
 University of Zagreb, Croatia

Good approach→ obtain an initial solution using a greedy

algorithm

Apply other heuristics for improving the solution (e.g.,

local search, tabu search, simulated annealing, ACO,
genetic algoithm, etc....) → more about this in the
upcoming lectures!

Zavod za telekomunikacije 42
 Example: Greedy 1
University of Zagreb, Croatia

Potential improvement (but not

necessarily): at the start, order
depots according to the ratio
of opening cost and capacity...

Zavod za telekomunikacije 43
 Example: Greedy 2
University of Zagreb, Croatia

 Phase 1, partitioning: each

node is assigned to the
nearest depot with available
capacity

 Phase 2, constructing routes

 As a first node, pick the farthest
customer
 Each subsequent customer is
the one nearest to the last
current customer and whose
demand can be met
 Objective: Visit the farthest
customers as soon as possible,
while minimizing route distance
Zavod za telekomunikacije 44
 Greedy algorithms - conclusions
University of Zagreb, Croatia

 Generally,
 Easy to understand
 Easy to implement
 Fast

 How good are they, though?

 For most optimization problems, they yield sub-
optimal solutions where the solution quality often
dependents on problem instance
 Sometimes also depends on starting point . Solution: can
be run as a multi-start algorithm if not time-critical
 However, some problems can be solved optimally
by a greedy algorithm
Zavod za telekomunikacije 45