Algorithmic Methods for Mathematical Models

(AMMM)

Greedy Algorithms
(for Combinatorial Optimization)

Luis Velasco
(lvelasco @ ac.upc.edu)
Campus Nord D6-107

Combinatorial Optimization

• A combinatorial optimization problem is defined by:

 N: finite ground set of elements, index i
 F: set of feasible solutions of N
 ci: cost of the element i
min
SN
c
iS
i

s.t. SF

• Combinatorial problems can be modeled using binary variables

xi{0,1}, one per element.

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 2

2
 Example: The Travelling Salesman Problem (TSP)

• Given a graph G(V,E) with a set of cities (V) and their pairwise distances
• The task is to find a shortest possible tour that visits each city exactly
once (Hamiltonian cycle).
• TSP is a combinatorial problem. Its search space is (n-1)!/2
 the ground set is that of all edges connecting the cities to be visited,
 F is formed by all edge subsets that determine a Hamiltonian cycle.
 f(S) is the sum of the distances of all edges in each Hamiltonian cycle
• What factorial means?
n search space
n search space 20 6.08E+16
3 1 30 4.42E+30
4 3 40 1.02E+46
5 12 50 3.04E+62 Information on the largest TSP instances solved
6 60 60 6.93E+79 to date can be found in:
7 360 70 8.56E+97 http://www.math.uwaterloo.ca/tsp/optimal/index.html
8 2,520 80 4.47E+116
9 20,160 90 8.25E+135
10 181,440 100 4.67E+155

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 3

The (n-1)!/2 combinations (n=5)

2 2 2 2
1 1 1 1

3 3 3 3

5 5 5 5
4 4 4 4
2 2 2 2
1 1 1 1

3 3 3 3

5 5 5 5
4 4 4 4

2 2 2 2
1 1 1 1

3 3 3 3

5 5 5 5
4 4 4 4

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 4

4
 Greedy algorithm

• A greedy algorithm builds the solution in an iterative manner.

 At each iteration, the best element from a candidate list is added to the
partial solution
• In general they have five pillars:
 A candidate set C, from which a solution is created
 A selection function, which chooses the best candidate to be added
 A feasibility function, to determine if a candidate can be used
 An objective function f(S), which assigns a value to a solution, or a partial
one
 A solution function, which indicate when we have a complete solution

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 5

Greedy Algorithm for Combinatorial Problems

C: Candidate set, index c

S⊆C: (partial) solution
q(c): quality of element c (greedy function). Added value of c for the
partial solution S. If c makes S not feasible, then q(c)=INFINITE.

Initialize C solution function

S←{}
while S is not a solution do selection function
evaluate q(c) ∀ c ∊ C
cbest ← argmax{q(c) | c ∊ C} feasibility function
S ← S U {cbest}
update C, e.g., C ← C \ {cbest} (you might want to exclude infeasible c)
return <f(S), S>

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 6

6
 Example: TSP

The nearest neighbor (NN) algorithm

Given graph G(V,E)
Partial
Solution
Tour ← {v}, where v is an arbitrary node (starting point) from V
while Tour ≠ V do V is the candidate set
C ← set of feasible links w.r.t. Tour ⊆ E
ebest ← (u ∈Tour, v ∉Tour) ← argmin{d(Tour, e) | e in C}
Tour ← Tour U {v}
return Tour

For |V| cities randomly distributed on a plane, the algorithm on

average yields length = 1.25 * shortest (optimal) length.

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 7

Example: TSP
2
1
1 2 3 4 5
1 - 10 12 7 9
2 - 11 17 4
3
3 - 5 14
5 4 - 9
4 5 -

10 2 10 2 10 2
1 1 12 1 11
12

9 7 3 9 3 9 14 3
17
5 5 5 5
4 9 4 4

2 2 2
1 11 1 11 1
4

3 3 3

5 5 5
4 4 4

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 8

8
 Example: TSP

• A greedy algorithm suffers from myopia.

 It looks for the best candidate at each iteration.

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 9

Other algorithms for the TSP

u
• Nearest Insertion (greedy): From a
cip+civ-cpv
small cycle, the algorithm expands the v
cycle by adding the nearest vertex. c ip+ciu-cpu
p

• Christofides algorithm: • Create the minimum spanning tree MST T of G.

• Denote O the set of vertices with odd degree in T
Produces solutions within • Find a perfect matching M with minimal weight in the
3/2 of an optimal solution, complete graph over the vertices from O.
i.e., Zheuristic ≤3/2 Z*. • Combine the edges of M and T to form a multigraph H.
• Form an Eulerian path in H (H is Eulerian because it is
connected, with only even-degree vertices).
• Transform the path found in last step to be Hamiltonian
by skipping visited nodes (shortcutting).

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 10

10
 Example 1: Assign tasks to computers (lab session 2)
Tasks Computers
t1
<t2, c1> c1
𝑟𝑒𝑠𝑖𝑑𝑢𝑎𝑙𝐶𝑎𝑝𝑎𝑐𝑖𝑦 𝑐 − 𝑟
1−
rt t2 <t2, c2> 𝑟
c2 rc 𝑞 < t, c > = 𝑚𝑎𝑥
𝑟𝑒𝑠𝑖𝑑𝑢𝑎𝑙𝐶𝑎𝑝𝑎𝑐𝑖𝑦 𝑐′
t3
1− | 𝑐 𝑖𝑛 𝐶, 𝑐 ≠ 𝑐
<t2, c3> 𝑟
c3
t4
S←∅
sortedT ← sort(T, rt, DESC)
for each c in C do residualCapacity(c) = rc
for each t in T do
C(t)←∅
for each c in C do
if rt ≤ residualCapacity(c) then C(t) ← C(t) U {c}
if |C(t)|=0 then return INFEASIBLE
cbest ← argmin{q(<t,c>) | c in C(t)}
residualCapacity(cbest) ← residualCapacity(cbest) - rt
S ← S U {<t, cbest>}
return S
Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 11

11

Assignment Tasks to computers: Iterative execution

Computers c1 c2 c3
rc 505.67 503.68 701.78
Tasks t1 t2 t3 t4 #3 task: t1 261.27
rt 261.27 560.89 310.51 105.8
C(t1) c2
Load if assignment
sortedTasks t2 t3 t1 t4
c2 0.5187
cbest c2
Computers c1 c2 c3
residualCap 505.67 503.68 701.78
Computers c1 c2 c3
residualCap 195.16 242.41 140.89
#1 task: t2 560.89 load 0.6141 0.5187 0.799
C(t2) c3 S {<t2,c3>,<t3,c1>,<t1,c2>}
cbest c3
#4 task: t4 105.8
Computers c1 c2 c3 C(t4) c1 c2 c3
residualCap 505.67 503.68 140.89 Load if assignment
load 0 0 0.799 c1 0.8233
S {<t2,c3>} c2 0.7288
c3 0.95
#2 task: t3 310.51 cbest c2
C(t2) c1 c2
Load if assignment Computers c1 c2 c3
c1 0.6141 residualCap 195.16 136.61 140.89
c2 0.6165 load 0.6141 0.7288 0.799
cbest c1 S {<t2,c3>,<t3,c1>,<t1,c2>,<t4,c2>}

Computers c1 c2 c3
residualCap 195.16 503.68 140.89 Solution
load 0.6141 0 0.799 S {<t2,c3>,<t3,c1>,<t1,c2>,<t4,c2>}
S {<t2,c3>,<t3,c1>} f(S) 0.799

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 12

12
 Set Covering

• Let M={1, 2, … , m} be the universe of elements to be covered.

• Let P={pj}j∊N, be a family of subsets pj, N={1, 2, … , n}
• Let cj be the cost associated with pj, e.g. its cardinality (|pj |).
• The set covering problem consists on finding the sub-family of elements {pj}j∊N*,
N* ≤N , with minimum cost such that Upj = M, i.e., covering M.

M/P p1 p2 p3 p4 p5 p6 p7 p8 Optimal solutions (cost 5)

1 X S={p6, p7}
2 X X X S={p2, p3, p6}
3 X X X X X
4 X X X X X Other feasible solutions
S={p1, p3, p6} (cost=6)
5 X X
S={p4, p6} (cost=6)
cost 2 1 1 3 3 3 2 1

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 13

13

Example: Greedy for set covering

Let S the solution sub-family
Let R the set of covered elements
Greedy function:
q(pj)=|pj ∩ (M\R)| = |pj \ (R∩pj)| → Number of additional elements of pj
If every pj has its own associated cost cj, the greedy function would be:
q(pj) = cj / |pj ∩ (M\R)|
S={}
R={}

compute q(pj) ∀ pj∊P\S q(p1) = 2 q(p5) = 3

Select the best element: p4 q(p2) = 1 q(p6) = 3
S={p4} q(p3) = 1 q(p7) = 2
R={2, 3, 4} q(p4) = 3 q(p8) = 1
compute q(pj) ∀ pj∊P\S q(p1) = 0 q(p5) = 1
Select the best element: p6 q(p2) = 0 q(p6) = 2
S={p4,p6} q(p3) = 0 q(p7) = 1
R=M q(p8) = 0
Cost: 6

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 14

14
 Example 2: Network planning
• A set of users U needs to be connected to the Internet. For that purpose, we
have a set of access point locations A where we could install routers (one per
access point at the most).
 For each user u, the amount cru of capacity units it consumes from the router it is
connected to is given.

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 15

15

Example 2: Network planning

• We have a set M of router models.

 Each model m with its fixed cost fm, capacity km, and reach dm.
 A router m can only connect users that are within a distance dm from the access point.
• We assume Euclidean distances, so for each user u and each access point a,
we know its Cartesian coordinates (x, y).
• We have to decide:
 which model of router, if any, should be installed in each access point,
 which access point each user should be connected to.
 The goal is to minimize the total cost, computed as the summation of the cost of all the
installed routers.

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 16

16
 Network planning: Greedy algorithm
qu   min{q(u , a)}
Infeasible either because of the reach or the load
  
 if d (u, a)  max{d m}  cru   max{km }   cru ' 
  u 'U ( a ) 
   User u can be served with the router currently
qu , a   0 if d (u, a)  d a  cru   ka   cru '  installed in location a
  u 'U ( a ) 
    
 f m  fa if d (u, a)  d a  cru   ka   cru ' , d (u , a )  d m  cru   km   cru ' 
  u 'U ( a )   u 'U ( a ) 
Router currently installed in location a needs to be upgraded because of the reach or the load
to serve user u

S ← ∅, C←U
Evaluate the incremental costs q(u) for all u ∈ C
while C ≠ ∅ do
umin ← argmin {q(u) | u ∈ C}
S ← S U {umin}
C ← C \ {umin}
Reevaluate the incremental costs q(u) for all u ∈ C
return S
Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 17

17

Network planning: Problem Instance

Users 10 9 APs
4 4

2
3 3

1
5 6
2 2
4 2
3,7 1,8
4
1 1
3

0 0

0 1 2 3 4 0 1 2 3 4
u 1 2 3 4 5 6 7 8 9 10
R1 R2 R3 d(u,a) x 1 2 0 4 1 2 0 1 3 2
f 100 140 180 y 1 3 1 1 2 2 1 1 4 4
k 6 8 10 1 2 3 2.2 0.0 2.8 2.8 1.4 1.0 2.8 2.2 1.4 1.0
d 2 3 4 2 1 2 1.0 1.4 1.4 3.2 0.0 1.0 1.4 1.0 2.8 2.2
3 1 1 0.0 2.2 1.0 3.0 1.0 1.4 1.0 0.0 3.6 3.2
4 0 2 1.4 2.2 1.0 4.1 1.0 2.0 1.0 1.4 3.6 2.8
5 1 3 2.0 1.0 2.2 3.6 1.0 1.4 2.2 2.0 2.2 1.4
a x y
Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 18

18
 Network planning: Iterative execution (1/5)
#1
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 100 100 100 140 100 100 100 100 100 100
a 3 1 3 1 2 1 3 3 1 1
d(u,a) 0.0 0.0 1.0 2.8 0.0 1.0 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R1
U(a) {1}
km-cr 4

#2
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 40 0 40 0 0 0 0 80 80
a 3 3 3 3 3 3 3 3 3 3
d(u,a) 0.0 2.2 1.0 3.0 1.0 1.4 1.0 0.0 3.6 3.2

a 1 2 3 4 5
m R1
U(a) {1,8}
km-cr 2

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 19

19

Network planning: Iterative execution (2/5)

#3
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 40 40 0 0 0 0 80 80
a 3 3 3 3 3 3 3 3 3 3
d(u,a) 0.0 2.2 1.0 3.0 1.0 1.4 1.0 0.0 3.6 3.2

a 1 2 3 4 5
m R1
U(a) {1,5,8}
km-cr 0

#4
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 80 80 40 40 40 80 80
a 3 3 3 3 3 3 3 3 3 3
d(u,a) 0.0 2.2 1.0 3.0 1.0 1.4 1.0 0.0 3.6 3.2

a 1 2 3 4 5
m R2
U(a) {1,5,7,8}
km-cr 1

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 20

20
 Network planning: Iterative execution (3/5)
#5
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 100 100 0 40 100 100
a 3 1 4 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 1.0 3.0 1.0 1.4 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R2
U(a) {1,4,5,7,8}
km-cr 0

#6
u 1 2 3 4 5 6 7 8 9 10
cr 2 3 4 1 2 2 1 2 3 4
q(u) 100 100 40 100 100
a 3 1 4 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 1.0 3.0 1.0 1.4 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R3
U(a) {1,4,5,6,7,8}
km-cr 0

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 21

21

Network planning: Iterative execution (4/5)

#7
u 1 2 3 4 5 6 7 8 9 10
cr 4 3 4 1 2 2 1 2 3 4
q(u) 100 100 100 100
a 3 1 4 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 1.0 3.0 1.0 1.4 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R1 R3
U(a) {2} {1,4,5,6,7,8}
km-cr 3 0

#8
u 1 2 3 4 5 6 7 8 9 10
cr 4 3 4 1 2 2 1 2 3 4
q(u) 40 0 40
a 3 1 1 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 2.8 3.0 1.0 1.0 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R1 R3
U(a) {2,9} {1,4,5,6,7,8}
km-cr 0 0

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 22

22
 Network planning: Iterative execution (5/5)
#9
u 1 2 3 4 5 6 7 8 9 10
cr 4 3 4 1 2 2 1 2 3 4
q(u) 80 80
a 3 1 1 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 2.8 3.0 1.0 1.0 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R3 R3
U(a) {2,9,10} {1,4,5,6,7,8}
km-cr 0 0

#10
u 1 2 3 4 5 6 7 8 9 10
cr 4 3 4 1 2 2 1 2 3 4
q(u) 100
a 3 1 4 3 3 3 3 3 1 1
d(u,a) 0.0 0.0 1.0 3.0 1.0 1.0 1.0 0.0 1.4 1.0

a 1 2 3 4 5
m R3 R3 R1
Solution Cost=460 U(a) {2,9,10} {1,4,5,6,7,8} {3}
km-cr 0 0 2

Algorithmic Methods for Mathematical Models (AMMM) Luis Velasco 23

23

Algorithmic Methods for Mathematical Models

(AMMM)

Greedy Algorithms

Luis Velasco
(lvelasco @ ac.upc.edu)
Campus Nord D6-107

24