CS代考 COMP3530 Discrete Optimization

COMP3530 Discrete Optimization
Week 8: Large Scale Optimization
Julian of Computer Science University of and Refresher

Goal for Today
We show how to deal with very large LPs without having to explicitly having to write down the whole model.
We we also develop an alternative algorithm for solving LPs called the Ellipsoid method.
1

Recall
A Linear Program in standard form looks as follows minimize c · x
subject to Ax = b x0
where A 2 Rm⇥n, x 2 Rn, b 2 Rm, and c 2 Rn. II
n=# vers m =#cons
Simplex solves these LPs by finding a basis B ✓ {1, . . . , n}
inducing an optimal solution xB = A1b and xi = 0 for i 2/ B. B
113km
2

Large Number of Constraints

Traveling Salesman Problem
Given a graph G = (V,E) and edge weights w : E ! R+, we want to find a tour T ✓ E that visits all vertices minimizing w (T ).
i
-.
11
÷ ; s
;EE
are 2
IV1 –
2
choices
of
minimize Xwexe
i.
?
¥¥
s
subjectto
e 2 XE e2(u)
xe =2 ✓
8u2V
8 ; ⇢ S ⇢ V
8 e 2 E
X
–
e2(S)
xe 2 xe 0
There
3

Row Generation
( 1¥.ie ) P= x2R|E| : x((u))=2 8u2V
+ x((S))2 8;⇢S⇢V Q=nx2R|E| : x((u))=2 8u2Vo
do
✗*←argininev.✗ : ✗c-
c-P return ✗ *
add ✗ (Sls))>2 to @ repeat
+
Q
QEQO
* if else
÷4″
*
‘
( 81st)< & s: :✗ ←subsetofV*2 ' :p 4 . Separation Oracle Def.: A separation oracle for a polyhedron P takes as input a solution x and it either declares that x 2 P, or x 2/ P and returns a violated constraint. For TSP 1 4 Idea : polyhedron constraints ✗ (Hn))=z ✗ ( Sls) ) > 2
true ✓
degree
if
[ Xe e. £81s)
C S
CU
connectivity constraint
Find
OICSCV
that minimizes
Simply a global m in
– cut
problem
CLAIM :
guess two vertices s and t
confute min s- t cut
g
vis
T 815)
5

Large Number of Variables

Edge Coloring
Given a graph G = (V , E ), we want to partition E into a collection ofmatchingsM1,M2,…,Mk usingasfewmatchingsaspossible.
minimize X w ✗ MM
✗
m =LEl
M2M
X rows
subjectto xM =1 8e2E M 2M:e 2M
xM 0 8 M 2 M where M is the collection of all matchings of G.
complete7
::¥¥¥
T in
.
1 h 1 3 n ! too many
•
n
6

Column Generation
Have Simplex only materialize-AB and to use an oracle for finding which variable to bring into the basis in each iteration.
B= {Mr,M2, – – – , MEG basis
✗ B. =
In
Afb
T is LEI HEI matrix
Cm EB Ats Am =no-1-
Xm_-o 4M¢B
CBEIRM
reducei
costefxm
Finding Xm with
Angeli” ” E.it?sc-R
Am
–
d
1
yt
1-
→ ¢M μ¥m
M with [Ye m ax een 7
[ ye een
AMEIR
”
–
%
m
0
m in
Em _=
Finding

Ellipsoid Algorithm

Ball, Ellipsoids, and Ane Transformations
*
Def.: An ane transformation f : R!Rn is f (x) = Mx + s where M 2 Rn⇥n is non-singular and b 2 Rn.
Def.: An ellipsoid E is the range of the unit ball under some ane transformation f ; namely, E = {f (x) : x 2 Bn},
E- Ex Def.: The n-dimensional unit ball Bn is {x 2 Rn : xT x  1}.
n
‘
R# B-
→
-4€
⇐
8

Simplifying Assumptions
Given a P.be a polyhedron. The Ellipsoid Algorithm will test if P = ;. To simplify the presentation we make some assumptions:
1
we c a n fit P inside a ball Beefradius R PEB
9

Simplifying Assumptions
Given a P be a polyhedron. The Ellipsoid Algorithm will test if P = ;. To simplify the presentation we make some assumptions:
!
Eithe 8=0 or
it contains a ball radius e of
P
9

Simplifying Assumptions
Given a P be a polyhedron. The Ellipsoid Algorithm will test if P = ;. To simplify the presentation we make some assumptions:
§
E
Given ellipsoid E centered at s and
halt space It= {✗c-R” E> En’t
vol¢
¥2
a.✗ >a.s then w e c a n find another ellipsoid E ‘
:
•
v01 (E) < • 9 The Ellipsoid Algorithm Ellipsoid (P, R , E) E← BTR) ← s←0 while s¢P if else assumption 1 uses hfzntz) use assumfti iterated In Rz times 4 > return ” 3=0 ” ←
w e have
i.P It={✗: a.✗Ia.s} HadE
E. s ← new ellipsoid from t use assunfhin ” 8=101 ”
oracle suchthat a.s>6
c a ll separation
to find
a . ✗ sb
return
10

Analysis
LetE0,E1,…,Ek theellipsoidsthealgorithmgoesthrough.
0¥ : 662 :
06-5
PE Ei ti
v01 (Eu) < v01 ( BTS) 3=01 If k=h (zntz) Ink I then they = D Ellipsoid is correct a. . : i If K= nczntz) In Rz 11 Closing comments 1 separation ⇒ feasibity checking → • ftiniyat. tin is performance in practice poly (n ,m , LI) Tp #bitsused ! Running poor #vars #cons to encode other algorithms that have fdy-ti-co-fle.it, 4) AB,C , 4 but a r e treasonable in practice ( interior looiit method 2 Simples has good performance bet exf ronni, time 12 Administratrivia Announcements • Assignment 2: • marks posted to Canvas • regrade request open until Oct 15 • Assignment 3: • include your code for Problem 4 • due on October 8 (11:59pm) • Assignment 4: • to be released next week • due on October 22 (11:59pm) 13