MIE 335: Algorithms and Numerical Methods
Algorithms for Decision Making
Department of Mechanical and Industrial Engineering University of Toronto
January 19, 2021
M. Bodur
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 1
OUTLINE
I Operationsresearch/Optimizationapproaches I Specializedalgorithmsfordecisionmaking
I Greedyalgorithms
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 2
OR approaches
LET’S TALK ABOUT OR
Some broad classes of optimization problems: I Linearprogramming
I Integerprogramming
I Dynamicprogramming
I Nonlinearprogramming We will see:
I
I I
Aproblemthatcannotbeeasilycastintothesecategories,and which has its own algorithm
Somegreedyalgorithmsandtheirvalues
Someclassicalproblemsandtheirintegerprogramming formulations
M. Bodur
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 3
Stable marriage
~ THE STABLE MARRIAGE PROBLEM ~
I nmenandnwomenwishtogetmarried
I Themenwanttomarrywomen,thewomenwanttomarrymen I Everyoneisokaywitharrangedmarriages
I Eachmanhasrankedallthewomenfrombest(1)toworst(n) I Eachwomanhasrankedallthemenfrombest(1)toworst(n)
The stable marriage problem (SMP)
Create marriages so that no couple is left in “unrequited love’”, i.e., there is a man and a woman who would both rather be with each other than with the person to whom they are married.
(Note that this does not fit into the OR problems we stated.)
(It would be a real challenge to develop a constraint for “no unrequited love”.)
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 4
Stable marriage
A STABLE MATCHING
A matching is stable if no unmatched man and woman each prefers midterm the other to his or her spouse. proof stable on
Men’s preferences Women’s preferences
m1 w3w2 w1 m2 w1 w2 m3 w1w3 w3
w1
m1
w2
w3
w2
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 5
m1 m3
m2 m3 m2 m1
m3 m2
Stable marriage
AN UNSTABLE MATCHING
mmm
Men’s preferences
m1 m2 m3
I
Women’s preferences
w1 w2 w3
an 5h office hour
w1 w3 w2
w2
w2
w1 w3
m1 and w1 would both rather be with each other than with the person to whom they are married
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 6
m3
w3 w1
m1 m2
m3 m2
m1
m1
m3
m2
Stable marriage
QUESTIONS
I DoesSMPalwayshaveasolution?
That is, does a stable marriage always exist?
I Ifso,can/howwecomputesuchasolutionefficiently? I Iftherearemultiplesolutions,whichoneisthebest?
A Nobel Prize-worthy algorithm can answer those
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 7
Stable marriage
APPLICATIONS OF SMP
Matching
I studentstoschools
I employerstoemployees I athletestoteams
I usertowebservermatch
From nytimes.com
Match 75K students to 426 public high schools
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 8
Stable marriage
NATIONAL RESIDENT MATCHING PROGRAM
? Match (> 30K) med-school students to hospitals (just in 17 secs) From businessinsider.com
From forbes.com
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 9
Stable marriage
AND THE NOBEL PRIZE GOES TO..
The Gale-Shapley algorithm
I Developedin1962byDavidGaleandLloydShapley
I WontheNobelPrizeinEconomicsin2012:howtomatchdifferent agents as well as possible
I Originalapplications:
• Collegeapplications • Marriages
I Laterusedtomatch:
• Med-schoolstudentstohospitals
• Studentstoschools
• Organdonorstopatients
From nobelprize.org
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 10
Stable marriage
THE GALE-SHAPLEY ALGORITHM
Repeat:
1. Each free man proposes to the most preferred woman to whom he
has not yet proposed.
2. Each woman accepts the proposal from the most preferred suitor,
to whom she gets “engaged.” Until everyone is engaged
while (9 free man m 2 M who still has a woman w 2 W to propose to) w = m’s highest ranked woman to whom he has not yet proposed if (w is free)
all 3 menpropo 6 most wanted
woman
M. Bodur
(m, w) become engaged
else # w is already engaged, say to m0
if (w prefers m to m0)
(m, w) become engaged
m0 becomes free
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 11
OUR SIMPLE EXAMPLE
I 3
2,3
2I
f
213
32
I
i 31
All
Women’s preferences
w1 m1 m2 m3 0
3213 3321
1. m1 proposes to w1: she accepts, they become engaged
2. m proposes to w : she accepts, they become engaged 22
Men’s preferences
iterate
m1 w1 w3 w2
mwww wmmm
iterate m2 w2 w3 w1 w2 m1 m3 m2 200 O_O
12
Men’s preferences Women’s preferences
71112 3
I
I2
m1 w1 m2 w2
Ii
M. Bodur
m3
MIE 335_02
w3
Algorithms and Numerical Methods: Algorithms for Decision Making
12
w1 w2
w3 w2
w3 w1 w2 w1 w3
m1
m2 m3 m1 m3
m3 m2 m1
m2
Stable marriage
OUR SIMPLE EXAMPLE
Men’s preferences
Women’s preferences
w1 w2
w1 m2 m3 W judge meand
m1w3w2 iteratee m2 w3 w1
my M2
M3
m1
and m
3. m3 proposes to w2: she prefers m3 over m2, so she accepts, they i Wz
become engaged, m2 becomes free
4. m2 proposes to w3 (since he had already proposed to w2): she
accepts, they become engaged
Men’s preferences Women’s preferences
m1 w3w2 w1 m2 w1 w2 m3 w1w3 w3
Everybody is engaged, so we stop. Is this a stable matching?
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 13
iterate 3 O O 00
w2m1m3 wmmm
m2
mwww
O_O
3213
3321
w1
m1
w2
w3
m1 m3
m2 m3 m2 m1
m3 m2
w2
Stable marriage
Stable marriage
BACK TO OUR QUESTIONS
I DoesSMPalwayshaveasolution?
That is, does a stable marriage always exist? Yes!
I Ifso,can/howwecomputesuchasolutionefficiently?
Using the Gale-Shapley algorithm therecouldbemultiple
stable
• Itssolutionisalwaysstable • Everyonegetsmarried
solution
I Iftherearemultiplesolutions,whichoneisthebest?
• Thesolutionisstable,butnotnecessarilyoptimalfromall
individuals’ points of view
• Optimalfortheinitiatoroftheproposals(men)
• Maynotbeoptimalforthereceiveroftheproposals(women)
• Thus, skewed to perform better from the men’s perspective
I What is the max # iterations? n2 every man every M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making
women
14
Greedy algorithms
GREEDY ALGORITHMS
Algorithms for optimization problems:
I Typicallygothroughasequenceofsteps,withasetofchoicesat
each step
I Ateachstep,theymakethebestchoicestakingfuturestepsinto
account; so that they end up with a global optimal solution I Thatis,theythinkahead
A greedy algorithm:
I I I
I
Alwaysmakesthechoicethatlooksbestatthemoment Ignoresthefuturesteps
Makesalocallyoptimalchoicehopingthatthischoicewillleadto a globally optimal solution
Buildupasolutionpiecebypiece,alwayschoosingthenextpiece that offers the most obvious and immediate benefit
M. Bodur
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 15
Greedy algorithms
global
A SIMPLE INTEGER PROGRAM
Given three items with profits, decide which ones to pick Greedy algorithm: Pick an item with the maximum profit
local
max 20×1 + 15×2 + 10×3 greedy s.t. x1 + x2 1
x1 + x3 1 x1,x2,x3 2{0,1}
I Optimalsolution:x=(0,1,1)withtotalprofit25 I Greedysolution:x=(1,0,0)withtotalprofit20
Greedy algorithms do not always yield optimal solutions
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 16
Greedy algorithms
COMMENTS ON GREEDY ALGORITHMS
– –
They do not always yield optimal solutions
Sometimes their solutions can be totally useless, and even dangerous (e.g., in healthcare applications)
+ +
For some problem classes, they find optimal solutions They are efficient
M. Bodur
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 17
Greedy algorithms
THE KNAPSACK PROBLEM
The 0-1 knapsack problem:
I Athiefrobbingastorefindsnitems
I The i-th item is worth vi 2 Z+ dollars and weighs wi 2 Z+ kilos I Hewantstotakeasvaluablealoadaspossible
I He can carry at most W 2 Z+ kilos in his knapsack
I Whichitemsshouldhetake?
Greedy does not work!
The fractional knapsack problem:
I Thesetupisthesame,buthecantakefractionsofitems,rather
than having to make a binary (0-1) choice for each item
in this
case
Greedy works!
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 18
Greedy algorithms
ariable
of item I 0cm
A GREEDY ALGORITHM FOR FRACTIONAL KNAPSACK
(XnXn )v max vixi : wixi W, x 2 [0, 1]n decision
i=1 i=1
I Foreachitem,computethevalueperkilo:v/w
I Ifthesupplyofthatitemisexhausted,movetotheitemwiththenext greatest value per kilo Irt
XXz Xn
I Takeasmuchaspossibleoftheitemwiththegreatestvalueperkilo Oxision
items
⇧ Always finds an optimal solution
⇧ Complexity: O(n log n) (due to sorting items based on value per kilo)
ii
I ContinueuntilreachingtheweightlimitW greedy works
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 19
Greedy algorithms
EXAMPLE
valueperkilo calculate v1/w1 = 6
v2/w2 = 5 v3/w3 = 4
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 20
Greedy algorithms
FAILS FOR 0-1 KNAPSACK
if traction is not allowed optimal greedy
de de
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 21
Greedy algorithms
THE SET COVERING PROBLEM (SCP)
I Wehaveanumberoftownslocatedinaruralarea
I Wewouldliketobuildschoolsservingthestudentsinthesetowns I Wewanttohavetheleastnumberofschoolssuchthatthereisat
least one school located within a 30km radius of each town
L#
M K# J#
H# G#
I#
v
B# C# A#
r
F# D#
school at A Tsien
E#
build
M. Bodur
MIE 335_02
Algorithms and Numerical Methods: Algorithms for Decision Making 22
Greedy algorithms
ay
PARAMETERS FOR SCP
I n:#towns
I Covera⇢ge (based on distance): For all i = 1,…,n, j = 1,…,n,
1, if town i can be served by a school placed in town j 0, otherwise
A
aij =
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making
23
Greedy algorithms
INTEGER PROGRAMMING FORMULATION OF SCP
Parameters:
I n:#towns
I Covermatrix:A=[aij]
Decision variables: For all j=1,. . . ,n,
xj =⇢ 1, ifaschoolwillbeplacedintownj
0, otherwise Xn
min
s.t.
xj
aijxj 1,
j=1 Xn
Ei
for all i = 1,…,n
(Cover each town)
M. Bodur
for all j = 1,…,n
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 24
j=1
xj 2 {0,1},
Greedy algorithms
HOW TO SOLVE SCP?
I I
I
I
Integerprogrammingishard(especiallyforlargeinstances)
Unfortunately,greedydoesnotworkinthesensethatwecannot find an optimal solution via greedy
However,thereisagreedyalgorithmwhichproducessolutions which have an objective value within a known upper bound from the optimal objective!
Thatis,wewillknowatworsthowmanyschoolsovertheoptimal we will be using
M. Bodur
MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 25
Greedy algorithms
THEORETICAL PERFORMANCE
guaranteed performance
not efficiency
I ThisgreedyalgorithmisanO(logn)approximationalgorithmforSCP
I ThismeansthatiftheoptimalsolutionusesKschools(outofn possible), then the greedy algorithm finds a solution with at most K log n schools
I E.g.,ifK=3andn=13,then3ln(13)=3⇥2.56=7.68 So, greedy will not open more than 7 schools
notnecessarilyalways 7
I E.g.,ifn=13andwefoundagreedysolutionopening6schools,
then the actual optimal value K 6/ln(13) = 2.34, i.e., K 3 3 school needed
at least
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 26
Greedy algorithms
eedy atoe faster
IN PRACTICE..
solution
som
b
IP
Comp time (s)
0.01 0.04 0.43 1.13 4.62 8.30 19.14 36.90 1234.17 1867.57
u
Greedy
Obj fn Comp time (s)
3 0.00
2 0.00
3 0.00
3 0.00 3 0.00 3 0.00
3 0.00
4 0.00
4 0.00 4 0.00
n
Obj fn
gr
10 2 20 2 30 3 40 3 50 3 60 3 70 3 80 3
90 100
4.00⇤ 4.00⇤
Greedy vs IP optimization (using MATLAB’s bintprog function) ⇤ indicates that an integer solution was not found
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 27
Greedy algorithms
GREEDY APPROACH FOR SCP
set S
Let S = ; % represents the set of selected school locations
while (9 uncovered town)
as long as thereis uncovered 6M
Find s⇤ as the school location that covers the most uncovered towns
Add s⇤ to S
Update the cover matrix A
% remove the newly covered towns (rows) and selected schools (columns)
return S
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 28
Greedy algorithms
EXAMPLE
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 29
1,0
I
i
Greedy algorithms
EXAMPLE
builtat A
0
off inEsa
O
1
47 69 II’s
builtatA K
O
M. Bodur
MIE 335_02
T
Algorithms and Numerical Methods: Algorithms for Decision Making 30
Greedy algorithms
EXAMPLE
builtat AMG
0
builtat AKGB builtatAikaGD F
Solution: {A,K,G,D,F,I}
Greedy correct
ethnifientao bad can we dobetter
M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 31
Greedy algorithms
IMPROVEMENTS
I AfterselectingAinIteration1,Cnolongercoversanyelements.
) we can just remove it remote column thatcover 0 Tom
(same goes for H and J in Iteration 2, and B, L, and M in Iteration 3, etc.)
I FcanonlybeservedbyaschoollocatedinF ) Add F to the solution from the beginning ) Remove F from the cover matrix
I DalreadycoversallthetownscoveredbyE
) we can just remove E (since we will favor D over E)
beginn remove column that are
dominated byothers M. Bodur MIE 335_02 Algorithms and Numerical Methods: Algorithms for Decision Making 32
addallcolumn
automatically the that cover 1 town at