COMP3530 Discrete Optimization
Week 2: Simplex
Julian of Computer Science University of and Refresher
Goal for Today
Develop an algorithm for solving Linear Programs of the form
in ) Yfandard
form
High level line of attack: Move from one extreme point to the next as long as we improve the objective value.
we will use
b a s ic feasible solutions
man
minimize c · x subject to Ax = b
(
x 0
whereA2Rm⇥n hasrank(A)=m,x2Rn,b2Rm,andc2Rn.
i÷÷i¥÷¥÷÷
tto talk about these
” corner ” solutions OPTIMAL 1
Basic Solutions of Abitrary Linear Programs
Def.:Ax2Rn suchthatajTx=bj implies ajT y = bj for all j. If additionally x 2 P then we say that x
is a basic feasible solution.
min c. ✗ A:[a¥ / A ✗ 36 din
at, ✗ 3 bj : 9J✗ =bj}
‘
1- = }j
2
Basic Solution of Linear Programs in Standard Form
Def.: A subset B ✓ {1,…,n} is a basis if rank(AB) -= |B| = m. Obs.: Every basis B defines a basic solution x where xB = A 1b
andxj =0forj2/B.
Obs.: Every basic solution is defined by one or more bases.
If we set
✗ 30 IABXB _- b ←
Columns of A
A-✗ =b (m LI)indexedbyB
B
✗j=o tj¢B entries of ✗
B
min c. ✗
A✗=b
indexedby
✗j=otjeB(n- m
LI)
3
Basic Solution of Linear Programs in Standard Form
Def.: A subset B ✓ {1,…,n} is a basis if rank(AB) = |B| = m. Obs.: Every basis B defines a basic solution x where xB = A 1b
Obs.: Every basic solution is defined by one or more bases.
B Éa n d x j = 0 f o r j 2/ B .
?
it – .
it ? ] of :[ ]
{b) ¥ 1)⇒ (0.50-5)–113 [ [)=[
–
Ax > A 1–1
6.x
{
✗3=0 Ax-6 =D .
BY
✗c- –
-_ →
✗z=o A-e-b =D [z’ ? ;][1) )
][
I
AB
10.6.0.2
B={ 1,3}
⇒
XB- b t.z-AY.GG
✗B
”
(0990-2)
3
Developing Simplex
Simplifying Assumptions
I 1. We are given an initial basic feasible solution. 2. Every basic feasible solution is non-degenerate
✓
strict
inequality
(there are always exactly n tight constraints). 3. The feasible region is bounded.
Given basis B that defines initial basic feasible solution
2
3
f
1
Basically
m e a n s that
Pe E.c)
,
✗ B – ABG
>0 ”
–
4
Simplex Take One
SIMPLEX (A, b , c)
B ← some feasible basis
repeat
Afb forjets. – in}
✗←
☐
IB and GieB D ← B- bitj
basis then
ifCD• Yp((B• ✗B
B←Dand until basis hasn’t changed
return B
if
✗☐ ← A-☐’ 6
D is a
feasible
break
for loop
5
Going from x to y
(B) ✗ 0–01>1 (D) 1 dk-0
y – ✗ +0-01 -0>-0
because •)b
k¢Btj
– D=Btj bi
2 dj=
-A”BAj| Ay – b
( just
3 KEB Acey)=0
•
we wants! yzo
“→ Ibi –
– 3 db:< 0
tk¢B+i2%Z°%B%][%]=°
4
A- (-0-01)=0 Xt; -10-016; V-bic-BArgdgl-Aj.co
-
dbi > o =D 4020 ABd☐= Aj
do:
We used
when
a-c-
dbi
b-bic-B then ✗ = ✗ +0-01
to >_o
=dB3othe
c. Y = C. ✗ to §. unbounded
objective
i s
feasible
/
if
re tu rn ” LP has unbounded objective 10
Removing Non-Degeneracy Assumption
we used it G- =
to argue that 0-70 min-xbibic-Bdbidq.co
Bland ‘s ! pick
rule for j¢B
anti – cycling
Ej<0 dbico
t i e s by c h o o s i n g
breakties by
st . bi c-Bst.
choosing
smallest j
4 pick
b r e a k
min
-o¥
s m a l l e s t b i
11
Removing Need for Initial Basis
min ÉY; i-i
A-✗ +7--6 ✗70 430
) gonna
630
b
assume
y=
It LP has
=D 4--0
If
LP has optimal cost > 0 =D original LP was
infeasible
12
Time Complexity
13
Administratrivia
Announcements
• Tutorials start this week! • Assignment 1:
• available in Ed (resource tab)
• due on August 27 (11:59pm)
• submission is via Gradescope (up and running)
• you know everything you need to solve the assignment
14
15