CS代考 COMP3530 Discrete Optimization

COMP3530 Discrete Optimization
Week 6: Integral Polyhedra

School of Computer Science University of and Refresher

Goal for Today
Understand why some times linear programs have integral solution.
min c.✗ relax
.
min c.x
s- t A-✗ E. b
”
✗ c- IR
3
t→
A✗ sb
5.
✗ c- 2¥
1

Recall
Last time we saw that maximum matching and minimum vertex cover have integal linear programming formation when the graph is bipartite.
Neither problem is integral when the underlying graph is not bipartite.
‘: so
min -2we ✗e
Exe
e – 8cm)
✗ e.30
Ye
LP = IP =
312
r
2

Totally Unimodular Matrices

Integral Polyhedra
Def.: We say that a polyhedron P is integral if all its extreme points are integral.
3

Integral Inverse Matrices
Lem.: Letx beabfsofanLPinstandardformandB beabasis
defining x. If A1 and b are integral so is x.
B min
C- ✗ A✗=b ✗ 20
✗i. =0 ✗ B. =
when
iEB ‘
A-B 6 is
St
Assume
A-‘Bb is
integral ? integral .
4

Cramer’s rule
Thm.: The inverse of a matrix M is Adj(M), where Adj(M) is the det(M )
adjugate matrix of M.
Ifdetfn)c-{r,- i} is integral
If M is integral, so is Adj(m)
This :
” ¥M
thou
5

Unimodular Matrices
Def.: A matrix A 2 Zm⇥n is unimodular if it has full-row-rank and for every basis B of A we have det(AB ) 2 {1, 1}.
Thm.: A matrix A 2 Zm⇥n is unimodular if and only if for all b2Zm thepolyhedronP={x2Rn :Ax=b,x0}isintegral.
*
A is on , modular ⇒ Pis integral
76
B
P and it’s defined fitB
lots of ✗i= -0
Leta be
✗D= A”Bb
= Is
i s integral
-→
↳ is ⇒ P
integral
integral
integral
is
6

Unimodular Matrices
Def.: A matrix A 2 Zm⇥n is unimodular if it has full-row-rank and
for every basis B of A we have det(AB ) 2 {1, 1}.
ei-E.li
Thm.: A matrix A 2 Zm⇥n is unimodular if and only if for all
b2Zm thepolyhedronP={x2Rn :Ax=b,x0}isintegral. i
P is let
integral
46 =D
(set2- to so ,
A is basis ofI
unimodal a r Am that× >o)
B be a 6 = AB2- tee.
✗☐= Afg6= A}(ArsZtei)= 2-+ Atei30;
P is integral = D ✗ , is integral ⇒ A- integral
A-‘BAB = I det (AIs) det (As) .- I ⇒ detail) c-{K- Y 6

Totally Unimodular Matrices
Def.: A matrix A 2 Zm⇥n is totally unimodular if for every square submatrix A0 of A we have det(A0) 2 {1, 0, 1}.
Thm.: Matrix A 2 Zm⇥n is totally unimodular if and only if for all b2Zm thepolyhedronP={x2Rn :Axb,x0}isintegral.
UNIMODULAR
ABM
EEÉE→→t#E } TBH oletCA.se/i.-i
7

Properties of Totally Unimodular Matrices
Lem.: Let A be a totally unimodular (TU) matrix . Then
• AllentriesofAare1,0,or1. ✓ • AT is TU. ✓
• The matrix [AI] is TU.
$”• The matrix [A A] is TU.
Aij is a valid square submatrixef A detcaij)- Aijc- {-1,91}
A → A’ }-1,0 } det(A)c- , ‘
4
→ AT ⇒ det(A” )e{-1,91}8
AT

Properties of Totally Unimodular Matrices
Lem.: Let A be a totally unimodular (TU) matrix . Then
• AllentriesofAare1,0,or1. • AT is TU.
• The matrix [AI] is TU.
• The matrix [A A] is TU.
=
mÉ] [A
i1 %
] [A- A]
I
8

Properties of Totally Unimodular Matrices
Lem.: Let A be a totally unimodular (TU) matrix . Then
(F)is to [It]is To
• All entries of A →are 1, 0, or 1. • AT is TU.
• The matrix [AI] is TU. → • The matrix [A A] is TU.
Co : If A is Tv matrix D= { IR” A-✗ Sb
is integral
✗c- : Ag.dg -✗
-✗
I :¥±tY÷)
☒ See
*
8

Alternative Characterizations

Matrix Bi-colorings
Def.: A column bi-coloring of a matrix A is a partition of its columns into “red” and “blue”. We say a bi-coloring is equitable if
X Aij X Aij  1 8i = 1,…,m j: red j: blue
Thm.: A matrix A is TU if and only if every columns submatrix of A admits an equitable column bi-coloring, or, equivalently, if every row submatrix of A admits an equitableErow bi-coloring%.
R✓
E. :3 R
😐
III.
:
9

Bipartite Matching Polytope
§ =
{✗ c-TE’ Axs
truer ,
✗30 is in
= .: The constraint matrix associated with the bipartite matching problem polyhedron is TU.
}
left shore RED
is in right shore BLUE
¥0K
:
Exe Er eedcn)
•
|-⇒ e- (a.v7
I.fm
E
?
Itu
u
⇒
n
10

Circulation Polytope
Thm.: The constraint matrix associated with the circulation problem polyhedron is TU.
P
.-
{
✗ c-
IRIE’ E✗e=E✗e : eosin e-8T¥
A ✗ = 0
V-uc-V.xz.co }
r
€7::
ii.→ •
E
e
R
11

Subset Selection Problems

Subset Systems
Def.: A subset system is a pair (U,I) where U is the ground set and I ✓ 2U is a collection of feasible subsets.
We assume that if A ✓ B ✓ U if B 2 I then A 2 I.
Def.: The canonical optimization problem definedPby (U,I) and
c:U!R+ istofindA2Imaximizingc(A)= x2Ac(x).
-E
¥: Uis
Given G=(V. E) I matching problem
MEE
:M
_-
{} matching
Given G- (4E) acyclic subgraph
u=E
Ex :
I-{TEE: Tis } acyclic
12

Rank Function
24=4AE u g Def.: The rank function of (U,I) is r : 2U ! Z+ where 124=2′ ar
r(S)=max{|A|:A✓S andA2I} rcs>< is r s ¢I⇐>
Lem.: For any S ✓ U we have r(S)  |S|. Furthermore, S 2 I if
and only if r(S) = |S|, E- SEE
‘-I’I— —I0z
r (s) -5 .
‘ r
2 ☒KI- r)
r(s)= (
K S
)
C
:
connected
conf of
13

Cannonical ILP Formulation
Def.: For a given subset systems (U,I) with rank function r, the
” P ) max-zcjxj-Zxjsrcsfs.su/ je s
canonical ILP formulation is given by
m e -28 x j Exjsrcs) FSEU
then
( P)
jell Xjzo T h = )itÉ Iia y i
j e s
✗ jetson }
subgraph
14

r
Matroids
Def.: A system (U,I) has the matroid property if for all S,T 2 I if |S| < |T| then exits x 2 T \ S such that S + x 2 I. Thm.: The relaxation of canonical ILP of a matroid is integral. acyclic subgraph system E± : has matroid trop EI : matching system d o e s n ' t h a v e → property •→ → S=o T= o_0 o_0 o-o • 15 Administratrivia Announcements • Assignment 1: • Regrade requests close on Sep 24. • Assignment 2: • we aim to post marks before semester break • Assignment 3: • to be released next week • due on November 8 (11:59pm) 16 17

Related Posts