CS代写 COMP3530 Discrete Optimization

COMP3530 Discrete Optimization
Week 5: Applications
Julian of Computer Science University of and Refresher

Goal for Today
Show applications of Linear Programming duality.
|jf
.
PRIMAL
min c.✗
a- ✗ =b
1min
cartoon
✗30
DUAL
6. y Atg E C
y free
max
c- R”
1

Recall
Every minimization linear program has associated a maximization dual program.
Weak duality: The value of any feasible primal solution is an upperbound on the value of any feasible dual solution.
Strong dual: If the primal is feasible and bounded, so is the dual. And the value of their optimal solutions are the same.
2

Playing Zero-sum Games

Zero-sum Games
Def.: Zero-sum game is a triplet (S1, S2, P) where
• S1 = {a1, . . . , an} are the strategies of player 1, Crow player) • S2 = {b1, . . . , bn} are the strategies of player 2, ( column player • P 2 Rn⇥m is the payo↵ matrix.
Def.: Given a pair of (pure) strategies (ai , bj ),
• the payo↵ of player 1 is pij , and • the payo↵ of player 2 is pij.
)
-2
player
f (column)
trample : Rock – Rafer – ⇐E-IR. Pis}
Scissors
P,?
flayer )

p
s
p
o
3

(Pure) Equilibria
Def.: A (pure) outcome (ai , bj ) is a (pure) equilibrium if
• pij pkj forallk=1,…,n • pij pik for all k =1,…,m
✗ → fg- ‘ ‘ I 0-I
✗ Pij>try tKei,- n ,n
profit
from deviations
= D player Pij£KiktfK=d,–. .m
I
cannot
– Pio ? – kik
L
cannot profit from
deviations
=D
player
4

Mixed Strategies
Def.: A mixed strategy is a probability distribution over strategies:
• forplayer1isx1,…,xn 0wherePxi =1, i
• for player 2 is y1,…,xm 0 where i yi = 1. Def.: Given a pair of mixed strategies x and y, E
[ti;] i j ij j~Y
• thepayo↵ofplayer1isXXxyp ,and in ✗ ij
• the payo↵ of player 2 is XXxiyjpij. ij
✗=
=D
(5,1-3,1-3)
is a nequi librium m ixed
Expected foayolt = 0
Rock-paper-scissors
5
for

Mixed Equilibria
Def.: A mixed outcome (x,y) is a mixed equilibrium if • XXxyp XXxˆyp foranyxˆ,and
ij ij
i j ij i j ij ij ij
• XXxyp XXxyˆp foranyyˆ. i j ij i j ij
6

Existance of Mixed Equilibria
=
max
Thm.: Every two-player zero-sum game has a mixed equilibrium.
[[ tij ✗iii.
[
Yj(§✗ifij)
min ✗yij ✗Yj
m ax nin
= max
7
( 7 ) E x i t i j # 2- G o i
(t) Zein
✗i > o ti
= max min min t
[
ifij
Fi
✗ ✗ji
j
§y§P→. S t [Yj- I
Yj 70
V-j
z
free
t
free
7

Existance of Mixed Equilibria
Thm.: Every two-player zero-sum game has a mixed equilibrium.
=
min max -22%-1.1:j=
E)
z-I-tt.EE/i7Itij
ij
m in M a x ✗yijY✗i
Zxiyjti
= ma;
j
§ ✗ ifij E. Yjtij
min
min max yij
I
j
(
j
Strong
Duality :
(
* ✗
,
and
Mt)
7

Existance of Mixed Equilibria
Thm.: Every two-player zero-sum game has a mixed equilibrium.
Y’) form an equilibrium
Claim (✗*
2- I ? YI Exit
,
[ Eti TIE 1× Pij= ig.=i
i j i EjxItij -2¥? E- É 2 E E ✗I to; = EYE .
=D
ijji
No point in deviating from f i, YY
7

Matching in Bipartite Graphs

(Integer) Linear Program
Given a graph G = (V,E) with w : E ! R+, find a matching M✓E maximizingw(M)=Pe2Mwe. ¥
“”
we-4
=)-2 ”
max .we×e
et ;k• k
e
xp _zeÉÉsr uev
‘
relaxation
KP )
ee8lu) feet ”
✗ ec-fo.is ±p=
,
¥PE¥→
their
eedcn) feet
Xe> o 8
m a n Ewexe eat
E✗eEr

Integrality of Bipartite Matching .: If G is bipartite then the linear relaxation Maximum –
*Matching is integral.
Let ✗ be a b.f.s
LP *¥0T want to show ✗← c-40,1} feet A
.
of
f- =/ec-E.io < Xeci f⇒F=§ case1: f- has a cycle CONTRADICTION case2: f- doesn't have a cycle CONTRADICTION A B triangle is not bipartite 9 r Integrality of Bipartite Matching .: If G is bipartite then the linear relaxation Maximum Matching is integral. F-- feet : ocxecr § ✗ Gfs. pnas•8"' A B ICI is even feasible z = Exe Si em •ÉÑ 2- is ✗=Z¥ %É ✗ + ↳ YFX I E isnt EP ¥ ⇒✗ ⇒ ✗ is not b.f.s. y=✗+ Te 9 Integrality of Bipartite Matching .: If G is bipartite then the linear relaxation Maximum te ! Matching is integral. " . ocxecr } ÷ F-{e-E acyclic feasible : , y ,z t.IO#+--x=YtzZy.-x+o--I-.- are 4. 2- =/ * z=× =D ✗ is not EP ⇒ ✗ is snot b.f.s. 9 Vertex Cover in Bipartite Graphs (Integer) Linear Program Given a graph G = (V,E) with w : E ! R+, find a cover C ✓ V minimizing |C|. (LP) (Yn) max so lfuev eaten) (Dt) Yuko then>c-E Fue V
✗e30
min -2 Yu u←V
He) Yutyv>t
10

Integrality of Bipartite Vertex Cover .: If G is bipartite then the linear relaxation of Vertex Cover is integral.
If y then
b. f.s. YnE{ 915
to CDL) Fuev
→
←
1m15 /Vcr {
11
is a
g-
–
☒
Smallest
Largest
VC = 2 M = 2

K ̈onig’s Theorem
Thm.: In every bipartite graph the size of the largest matching equals the size of the smallest vertex cover.
✗
t
#
vertices
*
,y^I optimal
have same
value
# edges
in matching
defined by ✗
vertex cover ¥ ‘T
defined by *
0
.IM/–o4vcl–2
12

Administratrivia

Announcements
• Install Gurobi on your computer, apply for an academic license, and run the Jupyter notebook from the demo.
• Assignment 1:
• marks have been posted to Canvas.
• good quality submission (mean = 75, median = 84).
• submit a regrade request through Gradescope before Sep 24.
• Assignment 2:
• available in Ed (resource tab)
• due on September 10 (11:59pm)
• submission is via Gradescope (up and running)
13

Related Posts