Linear Programming Solving LP
2021-03-10 CSC373 Winter 2021 – Sam Toueg 1
Recall: Farmer Example
• Canplanttwokindsofcorncrop:!!(forhumanconsumption)and!”(foranimalfeed)
Planting Requirements per hectare Available Resources Profit per hectare
!!
3$
!#
2$
Labour (hours)
≤ 40
Seed (kg)
≤ 100
Pesticide (bags)
≤ 10
!!
!”
Labour (hours)
Pesticide (bags)
2
1
1
1
Seed (kg)
3
0
• Goal: Find how many hectares of !! and !” to plant to maximize profit under available resource constraints
Formulate it as an LP problem:
• Variables: “!, “” amount of hectares of !! and !” to plant, respectively • Objective function: max 3 % “! + 2 % “” [pro,it]
• Constraints: 2 % “! + “” ≤ 40 “! + 3 % “” ≤ 100
“! ≤ 10 “!, “” ≥ 0
[labour constraint] [seed constraint] [pesticide constraint]
2021-03-10
CSC373 Winter 2021 – Sam Toueg 2
Geometric Interpretation of this LP Problem
+”
40
30
20 10
‘()*+,- (/, !%)
• Variables: #!, #”
• Objective function: max 3 & #! + 2 & #”
• Constraints:
2 & #!+ #” ≤ 40 [labour] #! + 3 & #” ≤ 100 [seed]
#!≤ 10 #!,#” ≥0
[pesticide]
Region of feasible solutions: all the points (3#, 3$) that satisfy all the constraints
! ” #! + % ” #” = 76
) * +$+ +” ≤ -.
+$ + / * +” ≤ 0..
+$ ≤ 0.
+$, +” ≥ . 40 +$
3 ” 3# + 2 ” 3$ = 5
obj. function to maximize
2021-03-10
!”#! +%”#” =60 !”#! +%”#” =40
10
20 30
!”#! +%”#” =20
CSC373 Winter 2021 – Sam Toueg 3
Optimal solution
• A feasible region of solutions is a convex polygon
convex non-convex
• Fact: If an optimal solution to a LP exists,
then at least one optimal solution is a vertex of the feasible region
optimal solution
objective function
• This fact restrict the search for an optimal solution: Ø From an infinity of feasible (3, 5) in the feasible region
Ø To the vertices of the feasible region (a polygon)
2021-03-10 CSC373 Winter 2021 – Sam Toueg 4
Beyond 2 dimensions
• What if a farmer can plant 3 different crops !!, !” and !#?
• The LP problem now involves 3 variables “!, “” and “# Ø Each constraint = plane
Ø Feasible region = Convex polygon Ø Objective function = plane
3$
3#
2021-03-10
CSC373 Winter 2021 – Sam Toueg
6
3%
General Form of LP Objective function: min/max ∑$ & ‘ ”
Variables:”!,…,”$ ∈R
Constraints:∑$ ( ‘” ≤≥ , , ∀.∈ 1,…,2
%&!% % %&! ‘% % = ‘
forsome6&’,7&,8′ ∈R
3#,3$,….,3( ≥0
• Each LP can be formulated in way such that it has only one type of constraints:
∑$ (‘”≤, or∑$ (‘”≥, or ∑$ (‘”=,
%&! ‘% % ‘ %&! ‘% % ‘ %&! ‘% % Ø E.g. by multiplying by −1 or adding an extra variable to get =
‘
• Optimal solution may not exist because:
a) LP is infeasible (feasible region is empty)
Ø LP is overconstrained (incompatible constraints) b) LP is unbounded (e.g. max “! + “” s.t. “!,”” ≥ 0 )
Ø LP is underconstrained
2021-03-10 CSC373 Winter 2021 – Sam Toueg
7
LP algorithm/solvers
• Input:anLPinstance(mayacceptonly≥or≤or=typeofconstraints)
Infeasible
Unbounded
Values for 3#,…, 3( that maximize/miniminize the objective function and satisfy all constraints
• Output=
• Common LP terminology:
Ø Objective function: function to be minimized/maximized
Ø Solution: assignment of real values to the variables
Ø Feasible solution: solution that satisfies all the constraints
Ø Optimal solution: feasible solution that minimizes/maximizes the objective function
Ø Value (resp. cost ) of a solution: value of objective function at this solution
Ø Value (resp. cost ) of LP: value of objective function at an optimal solution
2021-03-10 CSC373 Winter 2021 – Sam Toueg 8
2021-03-10 CSC373 Winter 2021 – Sam Toueg 10
2021-03-10 CSC373 Winter 2021 – Sam Toueg 11
Simplex Algorithm
• Start from any vertex in the feasible region
• Check if there is any vertex neighbor that has a strictly better value
Ø If yes: go to this neighbor, and then repeat from there
Ø If no (no neighbor has a better value): return this vertex as the optimal solution • Can prove: this local optimum is a global optimum
• Simplex algorithm is commonly used:
Ø Very good in practice: can be used to solve LP problems with
tens of thousands of variables and constraints
Ø But exponential-time in the worst-case: the feasible region can have an exponential number of vertices!
2021-03-10 CSC373 Winter 2021 – Sam Toueg 12
+”
40
(@,!!.!)
30
20 10
Simplex Algorithm
Local Optimum
=Optimal!
max3″3# +2″3$
s.t. 2″3#+3$ ≤40 3# +3″3$ ≤100
3#≤ 10 3#, 3$ ≥ 0
) * +!+ +” ≤ -.
+! + / * +” ≤ 0..
+! ≤ 0.
+!, +” ≥ . 40 +!
(/,!%)
Value of LP=76
Value of LP=66.6
(@, @)
(A@, %@)
(A@, @)
10 20
Value of LP=0
Value of LP=70
30
2021-03-10
CSC373 Winter 2021 – Sam Toueg
13
Value of LP=30
Simplex Algorithm • Local optimum = Global optimum
Ø Due to convexity of feasible region
D
B
≤
A
C
A is better than B and C (A is local optimum) ⟹
A is better than all vertices (A is optimal)
A is better than B and C (A is local optimum) BUT
D is better than A (A is not optimal)
B
A
C
2021-03-10
CSC373 Winter 2021 – Sam Toueg
14
≥
≤
≥
Simplex Algorithm
• It is the most commonly used method
• Verygoodinpractice
• But is exponential time in the worst case • Is there a polynomial time LP algorithm?
Number of variables
• That is, polynomial in Number of constraints Size of the coefficients
2021-03-10 CSC373 Winter 2021 – Sam Toueg 18
Other Algorithms
• Ellipsoid algorithm (Khatchian, 1979) Ø Polynomial time in the worst case Ø but slow in practise
• Interior point method (Karmarkar, 1984)
Ø Polynomial time in the worst case
Ø good in practise (competitive with simplex method)
2021-03-10 CSC373 Winter 2021 – Sam Toueg 19
Linear Programming Integer LP
2021-03-10 CSC373 Winter 2021 – Sam Toueg 1
Integer LP (ILP)
• LP: solutions are allowed to be real numbers Øi.e.,variables!!,…,!” ∈R
• ILP: solutions are required to be integers Øi.e.,variables!!,…,!” ∈Z
• 0-1 LP: solutions are required to be binary Øi.e.,variables!!,…,!” ∈{0,1}
• The decision variants of ILP and 0-1 LP: are NP-complete! • Example of 0-1 LP:
Ø Expressing (Min) Vertex Cover as 0-1 LP
2021-03-11 CSC373 Winter 2021 – Sam Toueg 3
Min Vertex Cover
• * = (-, .): undirected graph
• vertex cover (VC): a subset -′ of the nodes of * that “touches’’
every edge of *, i.e., every edge has at least one endpoint in -′
• minimum vertex cover: a VC with minimum size
2021-03-11 CSC373 Winter 2021 – Sam Toueg 4
Min Vertex Cover • Input:anundirectedgraph!(#,%)
• Output:minimumsize#′⊆#s.t.∀ *,+ ∈%atleastoneof*,+∈#′ # % ‘
$ & (
Expressing min vertex cover as 0-1 LP:
• (Binary) Variables: -!, ∀* ∈ # [intuition: !! = 1 iff node ” is in the VC]
• Objectivefunction:./0∑!∈#-! [intuition:wanta“smallest’’VC]
•Constraints:∀*,+ ∈%,-!+-$≥1 0-1 LP -! ∈ 0, 1 , ∀* ∈ #
or
0≤-! ≤1, ∀* ∈#
ILP
2021-03-11
[every edge must be “covered’’ by a VC node]
-! ∈ Z, ∀* ∈ #
CSC373 Winter 2021 – Sam Toueg 5
Some LP exercises
2021-03-10 CSC373 Winter 2021 – Sam Toueg 23
a t
Tutorial 6 Solutions
y y 3 z 3 z 2 x 2+x 2+ 2 y3x +3z2 y +2×5+z 2= 10
CSC373 Fall’20
Subject to
max 4x 3y+6z 2x y + 3z 2
y
t
a
Oct 27, 2020
3x 3+x 2+y 2+y 5+z 5=z 1=0 10 3xx, z+ 2y0+ 5z = 10
totoStohotheltuheLteHLioLHSnHSaStnoadnQcdo1ncsoFtniarsnstta,snltetsotstutohosetchtRheaHeRnSRgH.eHSt.Sh.e objective function to maximization. to the LHS and constants to the RHS.
Q1 Standard Form Q1 Standard Form
r program to the standard form.
Convert the following linear program to the standard form. Convert the following linear program to the standard form.
to the LHS and constants to the RHS.
Tuto3rxia+l 26y S+o5lzut=io1n0s 3x + 2y + 5z = 10
Tutorial 6 Solutions
Oct 27, 2020
x, z 0
xO,czt 270, 2020
x , zx , z 0 0 x, z 0
Next, let us address the greater-than-or-equal-to and equal-to constraints; we also bring all variables
NNeNxexte,xtl,te,lteleuttsuassdaddredsrsetshsethgereegartreearat-teterh-rat-nht-haonar-n-oe-rqo-uera-qelu-qtauol-atalon-tdaonedaqnueadqlu-etaqol-uctaoln-cstotonrsactionrnatisn;ttrwsa;eiwnatlesoa;lwbsoreibnarglisnaogllbavrlalirnvigabrailalelbsvleasriables to tNhextL,HleSt uasnadddcorenssttahnetgsrteoattehr-ethRaHn-So.r-equal-to and equal-to constraints; we also bring all variables
max 4x 3y+6z
max 4x 3y+6z max 4x 3y+6z max 4x 3y+6z
max 4x 3y+6z max 4x 3y+6z
0 00
s.t.
max 4x 3y +3y +6z s.t.
min 4x+3y 6z s.t.
y 3z 2x + 2 3x + 2y + 5z = 10 x, z 0
Finally, let us address the fact that variable y is unrestricted by replacing y with y0 y00, where y0 Finally, let us address the fact that variable y is unrestricted by replacing y with y y , where y
s.t. s.t.
s.t. s.t.
s.t.
m i n 4 x + m3 y i n 46 xz + 3 y 6 z
s.t.
2x y+3z 2 y 3z 2x + 2
2x y +y +3z 2 0 00
2x y + 3z 2
2x y + 3z 2 2x y + 3z 2 2x y + 3z 2
0 00
s.t.
3x + 2y + 5z 10
3x + 2y + 5z 10 3x + 2y + 5z 10 3x + 2y + 5z 10
3x+2y 2y +5z10 0 00
y 3z 2x+2
3x +2y+55zz=1010
y 3z 2x + 2
3x 2y 5z 10
3x 2y 5z 10
3x 2y 5z 10 3x 2y 5z 10
3x 2y +2y 5z 10 0 00
3x+2y+5z=10 x, z 0
3x 2y 5z 10
3x + 2y + 5z = 10 x, z 0
x, z 0 x,z 0
x, z 0 x, z 0
x,z,y,y 0
x , zx , z 0 0
Next, let us address the greater-than-or-equal-to and equal-to constraints; we also bring all variables
0000000 0 FFiinallly, let usadddrreesssthtehefafcatcthtahtavtarviarbilaebyleisyuinsreusntriecstterdicbtyedrebpylacrienpglayciwnigthyyw it0hy y, w0 0heyre,ywhe0re y
000 000 0
us chaanFngdeinytyahlelyao0,r0belejbebtcotutihsvheannfdouondn-rcn-etnesigoesangtahittvoeievm.fea.acxtimthizaattivoanr.iable y is unrestricted by replacing y with y y , where y and y00 are both non-negative.
and y are both non-negative.
Solution to Q1 First, let us change the objective function to maximization.
00 Q2 Simple Scheduling with Prerequisites (SSP) and y are both non-negative. Standard form:
Solution to Q1 First, let us change the objective function to maximization. 1. Change the objective function to maximization
2. mChaaxn ge4≥x an3dy=+t6oz≤ s.t.
max 4x 3y+6z
You are given n jobs with a list of du
s.t. alsogivenabooleanpi,j: ifthisistru max 4x 3y+6z
For ever shbefore
jobcanst uring tha
3x + 2y + 5z = 10
that the total time to complete all jobs 3x + 2y + 5z = 10
a prerequisite for job j). s . t . m2 x a x y + 4 3 x z 3 y 2 + 6 z
• all the variables are on the left and constant is on the right
y 3z 2x + 2
3. Restrict all variables to ≥ 0
1 y 3zx Y+o22uxyr+g+o2a5lzist1o0findstarttimess ,s ,.
• , is unrestricted → replacing , with ,′ − ,′′ s.t. ,′, ,′′ ≥ 0
x, z 0 x, z 0
x, z 0
s.t. 1 1 2 1
1
3x 2y 5z 10
y 3z 2x + 2
x, z 0 Next,letusaddressthegreater-than-or-equal-toandequal-toconstraints;wealsobringallvaria0bles00 0
ter-than-or-equal-to and equal-to constraints; we also bring all variables
Finally, let us address the fact that variableSoyluistuionnretstoriQct2ed by replacing y with y y , where y
to the LHS and constants to the RHS. o the RHS. 00
1
are met. Write a linear program to solve this problem.
3x + 2y + 5z = 10
and y are both non-negative.
Next, let us address the greater-than-or-equal-to and equal-to constraints; we also bring all variables
For each job i, we have a variable si, which is the start time of job i. to the LHS and constants to the RHS. which is an upper bound on the total time to completion. The LP is
max 4x 3y+6z s.t.
max 4x 3y+6z
s.t. Minimize T
rations d1,d2,…,dn. e, then job i must fini
..,sn for the jobs (no is minimized while ens
t
t
m m
Q2 Simple Scheduling with Prerequisites (SSP)
Q3 Exercises From Class
)
r
r e
i
m c
o t
t
T T
a
n n
h
h c
w w
m
P e
Q2 Simple Scheduling with Pr3exr+eq2yu+is5itze=s1(0SSP)
You are given n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j
x, z 0
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you a
max 4x 3y+6z 1 2 n
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you a
also given a boolean pi,j : if this is true, then1 jo2b i munst finish before job j can begin (i. also given a boolean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i
also given a boolean p : if this is true, then job i must finish before job j can begin (i.e. job i a presr.etq.uisite for job ji,j).
a prerequisite for job j). a prerequisite for job j).
Q2 Simple Scheduling with Prerequisites (SSP)
y 3z 2x + 2
Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than ti Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) su
1122nn
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you are
Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) suc
1212nn
3x + 2y + 5z = 10
that the total time to complete all jobs is minimized while ensuring that the prerequisite c
that the total time to complete all jobs is minimized while ensuring that the prerequisite constrain also given a boolean p : if this is true, then job i must finish before job j can begin (i.e. job i is
that the total time to complete all jobs is minimized while ensuring that the prerequisite constrain
Solution to Q2
Solution to Q2 Solution to Q2
i,j
a prerequisite for job j).
araeremmete.t.Wrrititee a linear prrooggrarmamtotososlvoelvtehitshpisropbrleomb.lem.
x, z 0
are met. Write a linear program to solve this problem.
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such that the total time to complete all jobs is minimized while ensuring that the prerequisite constraints
han-or-equal-to and equal-to constraints; we also bring all variables
are met. Write a linear program to solve this problem.
e RHS.
For each job i, we have a variable s , which is the start time of job i. We also have a variable
i • Variables?
For each job i, we have a variable s , which is the start time of job i. We also have a variable
For each job i, we have a variablei s , which is the start time of job i. We also have a v • Variables 4! = start time of job 5 i
which is an upper bound on the total time to completion. The LP is as follows.
Q3 Exercises From Class
which is an upper bound on the total time to completion. The LP is as follows.
w• hi6ch= tihseaconmuppleptioenrtbimoeuonfdallojnobsthe=tmoatxa{l3#t+im4#e,5 t∈o{1c,2o,m…,p8l}e}tion.• ThevLalPueitso baesofpotlilmoiwzesd.?
Minimize T
(a) Show that the following optimization problem can be solved by solving one or more LPs.
mMainxim ize4Tx 3y + 6z MinimizeT =max{3 +4,5∈{1,2,…,8}}
Ø Expressed in terms of variables • Constraints?
Subject to Subject to
##
s.t. Subject to
T si + di, for i 2 {1, 2, . . . , n} T si + di, for i 2 {1, 2, . . . , n}
T s s s++dd, ,foforrii,2j {21{,12,,2.,….,.n, n}} s.t. i 6= j and p
j ii ii i,j
2x y + 3z 2
max 12A + 23B + 15C
is true sj si + di, for i, j 2 {1, 2, . . . , n} s.t. i 6= j and pi,j is true
s 0, for i 2 {1,2,…,n} s.t.
s i s+d,fori,j2{1,2,…,n}s.t.i6=jandp istrue
s 0, for i 2 {1,2,…,n}
jii i,j
3x + 2y + 5z 10 5A + 15B + 10C 500 4A+4B+7C 300
i
si 0, for i 2 {1,2,…,n}
Justification: The third constraint ensures that start times are non-negative. The second co 3x 2y 5z 10
Justification: The third constraint ensures that start times are non-negative. The second co 35A+20B+25C 1000
straint ensures that prerequisites are met. The first constraint ensures that T is at least t straint ensures that prerequisites are met. The first constraint ensures that T is at least t
Justifixc,azti on0: The third constraint ensures that start times are non-negative. The se ¬(A > 0 ^ B > 0)
completion time of each job; hence, T is an upper bound on the overall completion time. If
completion time of each job; hence, T is an upper bound on the overall completion time. If straint ensures that prerequisites are met. The first constraint ensures that T is at
A, B, C 0
minimize T subject to this, in the optimal solution T will always be set equal to the overall co
minimize T subject to this, in the optimal solution T will always be set equal to the overall co hat variable y is unrestricted by replacing y with y y , where y
completion time of each job; hence, T is an upper bound on the overall completion ti pletion time because there are no other constraints on T. Hence, the optimal solution to this L
000 0
pletion time because there are no other constraints on T. Hence, the optimal solution to this L m(bi)niSmhoiwzethTat sthuebfjoellcowtintog otphtims,iziantiotnhperoobpletmimcaanlbseosloulvteidonbyTsolwvinilgloanlewoarymsorbeeLPses.t equal to the ov
finds the minimum overall completion time. finds the minimum overall completion time.
pletio2n021t-0i3m-1e0 because there are noCSCo3t7h3 eWrintceor 2n0s21tr- aSaimntTosueogn T . Hence, the optimal s2o5lution t finds the minimum overall completion time.
t
u n
t
m m
0 00 Q2 Simple Scheduling with Prerequisites (SSP)
)
Q3 Exercises From Class
w m
r
r e
m c
i
a
o t
i
t
T T
a
n n
h
h c
w w
mo
P
t e
Q2 Simple Scheduling with Pr3exr+eq2yu+is5itze=s1(0SSP) x,z,y0,y00 0
You are given n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j
x, z 0
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you a
max 4x 3y+6z 1 2 n
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you a
also given a boolean pi,j : if this is true, then1 jo2b i munst finish before job j can begin (i. also given a boolean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i
also given a boolean p : if this is true, then job i must finish before job j can begin (i.e. job i a presr.etq.uisite for job ji,j).
a prerequisite for job j).
aQp2reSriemqupisleiteSfcohrejdobulji)n.g with Prerequisites (SSP)
Q2 Simple Scheduling with Prerequisites (SSP)
y 3z 2x + 2
Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than ti Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) su
1122nn
You are given n jobs with a list of durations d ,d ,…,d . For every pair of jobs (i,j), you are
You are given n jobs with a list of du1ra2tions dn ,d ,…,d . For every pair of jobs (i,j), you Your goal is to find start times s1, s2, . . . , sn for t1he 2jobs (non job can start earlier than time 0) suc
3x + 2y + 5z = 10
that the total time to complete all jobs is minimized while ensuring that the prerequisite c
that the total time to complete all jobs is minimized while ensuring that the prerequisite constrain also given a boolean p : if this is true, then job i must finish before job j can begin (i.e. job i is
also given a boolean p : if this is true, then job i must finish before job j can begin (i.e. job thatthetotaltimetocoi,mj pletealljobsisminimizedwhileensuringthattheprerequisiteconstrain
i,j
a prerequisite for job j).
araeremmete.t.Wrrititee a linear prrooggrarmamtotososlvoelvtehitshpisropbrleomb.lem.
a prereqxui,szite fo0r job j).
are met. Write a linear program to solve this problem.
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) s that the total time to complete all jobs is minimized while ensuring that the prerequisite constraints
han-or-equal-to and equal-to constraints; we also bring all variables
Solution to Q2
Solution to Q2
Solution to Q2
that the total time to complete all jobs is minimized while ensuring that the prerequisite constrai
are met. Write a linear program to solve this problem.
e RHS.
aFroer meaecth. Wjobritie, wa elinheaavre parovagriaambletoss,owlvheicthisisptrhoeblsetmar.t time of job i. We also have a variable
i • Variables?
For each job i, we have a variable s , which is the start time of job i. We also have a variable
For each job i, we have a variablei s , which is the start time of job i. We also have a v • Variables 4! = start time of job 5 i
which is an upper bound on the total time to completion. The LP is as follows.
Q3 Exercises From Class
which is an upper bound on the total time to completion. The LP is as follows.
w• hi6ch= tihseaconmuppleptioenrtbimoeuonfdallojnobsthe=tmoatxa{l3#t+im4#e,5 t∈o{1c,2o,m…,p8l}e}tion.• ThevLalPueitso baesofpotlilmoiwzesd.?
Solution to Q2
Minimize T
(a) Show that the following optimization problem can be solved by solving one or more LPs.
For each job i, we have a variable s , which is the start time of job i. We also have a variable
mMainxim ize4Tx 3y + 6z Ø Expressed in terms of variables
Minimize T Subject to
Subject to i
• Constraints?
s.t. Subject to
T s +d,fori2{1,2,…,n}
which is an upper bound on the total time to completion. The LP is as follows.
T s i + d i, for i 2 {1, 2, . . . , n}
i i max 12A+23B+15C
T s s s++dd, ,foforrii,2j {21{,12,,2.,….,.n, n}} s.t. i 6= j and p
j ii ii i,j
is true sj si + di, for i, j 2 {1, 2, . . . , n} s.t. i 6= j and pi,j is true
2x y + 3z 2
Minimize T s.t.
s 0, for i 2 {1,2,…,n}
s i s+d,fori,j2{1,2,…,n}s.t.i6=jandp istrue
s 0, for i 2 {1,2,…,n}
jii i,j
3x + 2y + 5z 10 5A + 15B + 10C 500 Subject to
i
si 0, for i 2 {1,2,…,n}
4A+4B+7C 300 T s +d,fori2{1,2,…,n}
Justification: The third constraint ensures that start times are non-negative. The second co 3x 2y 5z 10
ii
Justification: The third constraint ensures that start times are non-negative. The second co
s s +d,fori,j2{1,2,…,3n5A}+s.2t.0Bi+6=2j5Cand10p00 istrue jii i,j
straint ensures that prerequisites are met. The first constraint ensures that T is at least t straint ensures that prerequisites are met. The first constraint ensures that T is at least t
Justifixc,azti on0: The third constraint ensures that start times are non-negative. The se
s 0,fori2{1,2,…,n} ¬(A>0^B>0) i
completion time of each job; hence, T is an upper bound on the overall completion time. If
completion time of each job; hence, T is an upper bound on the overall completion time. If straint ensures that prerequisites are met. The first constraint ensures that T is at
A, B, C 0
minimize T subject to this, in the optimal solution T will always be set equal to the overall co
minimize T subject to this, in the optimal solution T will always be set equal to the overall co hat variable y is unrestricted by replacing y with y y , where y
coJmupstleifiticoantitoinm:eTohfeetahcihrdjocobn;sthreanincte,enTsuirsesatnhautpspteartbtoimunesdaoren ntohne-noevgeartaivlle.coTmheplseetciondtci pletion time because there are no other constraints on T. Hence, the optimal solution to this L
pletion time because there are no other constraints on T. Hence, the optimal solution to this L straint ensures that prerequisites are met. The first constraint ensures that T is at least
m(bi)niSmhoiwzethTat sthuebfjoellcowtintog otphtims,iziantiotnhperoobpletmimcaanlbseosloulvteidonbyTsolwvinilgloanlewoarymsorbeeLPses.t equal to the ov finds the minimum overall completion time.
finds the minimum overall completion time.
completion time of each job; hence, T is an upper bound on the overall completion time. If
pletio2n021t-0i3m-1e0 because there are noCSCo3t7h3 eWrintceor 2n0s21tr- aSaimntTosueogn T . Hence, the optimal s2o6lution t
minimize T subject to this, in the optimal solution T will always be set equal to the overall co finds the minimum overall completion time.
000 0
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such Your goal is to find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) such
times s1 , s2 , . . . , sn for the jobs (no job 1can2 start enarlier than time 0) such
that the total time to complete all jobs is minimized while ensuring that the prerequisite constraints
that the total time to complete all jobs is minimized while ensuring that the prerequisite constraints plete all jobs is minimized while ensuring that the prerequisite constraints
are met. Write a linear program to solve this problem. prograrme tmoesto.lvWe rtihties aprloinbleeamr.program to solve this problem.
Q3 Exercises From Class lass Q3 Exercises From Class
wing optimization problem can be solved by solving one or more LPs.
(a) Show that the following optimization problem can be solved by solving one or more LPs.
(a) Show that the following optimization problem can be solved by solving one or more LPs.
(a) max 12A+23B+15C s.t.
5A + 15B + 10C 500 4A+4B+7C 300 35A+20B+25C 1000 ¬(A > 0 ^ B > 0)
(b) max 12A+23B·C2 max 12A + 23B + 15C
A, B, C 0
wing optimization problem can be solved by solving one or more LPs.
max 12A + 23B + 15C s.t. ss..tt..
5A + 15B + 10C 500 5A+15B+10C55000 4A+4B+7C 300
4A+4B+7C300 35A+20B+25C 1000 35A+20B+25C 1000
35A+20B+25C 1000
Not standard LP restrictions C 2 1, . . . , 100
¬(A > 0 ^ B > 0) ¬(A > 0 ^ B > 0)
A, B 0 (c) LetF={x2Rn:Axb^x 0}.Let
A, B, C 0 A, B, C 0
(b) Show that the following optimization problem can be solved by solving one or more LPs. (b) Show that the following optimizHaotwiontoprerodbulcemtocLaPn?be solved by solving one or more LPs.
1
• O1 = arg maxx2F cT1 x
// This is a usual LP as we maximize a linear objective subject to linear constr
•O2=argmaxx2O1 cT2x
// Among the optimal solutions from before, break ties by maximizing another
1 •O3=argmax 1 cTx
x2O2 3
// Break ties further by maximizing yet another objective.
2021-03-10
Show how to find some x 2 O3 by solving one or more LPs.
CSC373 Winter 2021 – Sam Toueg 27
t m
C
o
y 3z 2x + 2
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such
o
C
oo
o
o t e
s
t
o
a l
o
o
mplete all jobs is minimized while ensuring that the prerequisite constraints 3x + 2y + 5z = 10
3x + 2y + 5z = 10
thYatouthr egotaoltaisl toimfiendtosctaormt ptilmetesasll ,jsob,s. .is. ,ms infiomr itzheed jwobhsil(eneonjsoubricnagntshtatrttheaerplireerrtehqaunistiitme eco0n)ssturachints
12n
artehmateth.eWtortiatel taimlienteoarcopmropglertaemaltlojosboslvisemthinisimpirzoebdlewmhi.le ensuring that the prerequisite constraints
program to solve this problem. x, z 0
x, z 0
Q2 Simple Scheduling with Prerequisites (SSP)
are met. Write a linear program to solve this problem.
lass
Q3 Exercises From Class cheduling with Prerequisites (SSP)
(a) Show that the following optimization problem can be solved by solving one or more LPs. olean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i is
Q3 Exercises From Class
wing optimization problem can be solved by solviYnoguoanre ogrivmenonrejLobPss.with a list of durations d1, d2, . . . , dn. For every pair n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j), you are
find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) such
From Class
5A+15B+10C 500 4A+4B+7C 300
s.t.
12n
¬(A > 0 ^ B > 0)
the following optimization problem can be solved3b5yAso+lvi2n0gBon+e o2r5mCore L1P0s0.0
also given a boolean p : if this is true, then job i must finish before job j c i,j
a prerequisite for job j).
(a) Show that the following optimization problem can be solved by solving one or more LPs.
for job j).
(a) max12A+23B+15C Yourgoalistofindstarttimess1,s2,…,sn forthejobs(nojobcanstartear
max 12Ath+at t2h3eBto+tal1t5imCe to complete all jobs is minimized while ensuring that the pr ime to complete all jobs is minimized while ensuring that the prerequisite constraints
5A+15B+10C 500 a linear program to solve this problem.
max 12Aar+e m2e3tB. W+ri1te5Ca linear program to solve this problem. s.t.
⟺4A(<+≤40B) ∨+(?7C≤0)300
(a) Show that the following optimization problem can be solved by solving
4A+4B+7C 300
35A + 20B + 25C 1000
s.t. 5A+15B+10C 500 Q3 Exercises From Class
A, B, C 0
LP1: max 12A+23B+15C
35A+20B+25C 1000
wing optimization problem can be solved by sAol,vBing,Con e o0r more LPs.
¬(A > 0 ^ B > 0) ¬(A > 0 ^ B > 0)
LP2 :
max 12A + 23B + 15C s.t.
A, B, C 0
(b) Show that the following optimization problem can be solved by solving one or more LPs.
s.t.
5A+15B+10C 500
5A+15B+10C 500 4A+4B+7C 300
(b) Show that the following optimization problem can be solved by solving one or more LPs.
4A+4B+7C 300 35A+20B+25C 1000
¬(A > 0 ^ B > 0) <≤0
A, B, C 0
t the following optimization problem can be solved by solving one or more LPs.
35A+20B+25C 1000 ¬(A > 0 ^ B > 0)
A, B, C 0
1
?≤0
1 1
(b) Show that the following optimization problem can be solved by solving
2021-03-10
CSC373 Winter 2021 – Sam Toueg 1 28
1
y 3z 2x + 2
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such
o
C
oo
o
o t e
s
t
o
a l
o
o
mplete all jobs is minimized while ensuring that the prerequisite constraints 3x + 2y + 5z = 10
3x + 2y + 5z = 10
thYatouthr egotaoltaisl toimfiendtosctaormt ptilmetesasll ,jsob,s. .is. ,ms infiomr itzheed jwobhsil(eneonjsoubricnagntshtatrttheaerplireerrtehqaunistiitme eco0n)ssturachints
12n
artehmateth.eWtortiatel taimlienteoarcopmropglertaemaltlojosboslvisemthinisimpirzoebdlewmhi.le ensuring that the prerequisite constraints
program to solve this problem. x, z 0
x, z 0
Q2 Simple Scheduling with Prerequisites (SSP)
are met. Write a linear program to solve this problem.
lass
Q3 Exercises From Class cheduling with Prerequisites (SSP)
(a) Show that the following optimization problem can be solved by solving one or more LPs. olean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i is
Q3 Exercises From Class
wing optimization problem can be solved by solviYnoguoanre ogrivmenonrejLobPss.with a list of durations d1, d2, . . . , dn. For every pair n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j), you are
find start times s ,s ,…,s for the jobs (no job can start earlier than time 0) such
s.t.
12n
also given a boolean p : if this is true, then job i must finish before job j c i,j
a prerequisite for job j).
(a) Show that the following optimization problem can be solved by solving one or more LPs.
for job j).
(a) max12A+23B+15C Yourgoalistofindstarttimess1,s2,…,sn forthejobs(nojobcanstartear
max 12Ath+at t2h3eBto+tal1t5imCe to complete all jobs is minimized while ensuring that the pr ime to complete all jobs is minimized while ensuring that the prerequisite constraints
max 12Aar+e m2e3tB. W+ri1te5Ca linear program to solve this problem. s.t.
⟺4A(<+≤40B) ∨+(?7C≤0)300
(a) Show that the following optimization problem can be solved by solving
s.t.
5A+15B+10C 500 a linear program to solve this problem.
s.t. 5A+15B+10C 500 Q3 Exercises From Class
From Class
4A+4B+7C 300
35A + 20B + 25C 1000
5A+15B+10C 500 4A+4B+7C 300
¬(A > 0 ^ B > 0)
the following optimization problem can be solved3b5yAso+lvi2n0gBon+e o2r5mCore L1P0s0.0
A, B, C 0
LP1: max 12A+23B+15C Takethebestof
wing optimization problem can be solved by sAol,vBing,Con e o0r more LPs.
35A+20B+25C 1000
¬(A > 0 ^ B > 0) ¬(A > 0 ^ B > 0)
LP2 :
max 12A + 23B + 15C s.t.
A, B, C 0 LP1 and LP2
5A+15B+10C 500 (b) Show that the following optimization problem can be solved by solving one or more LPs.
5A+15B+10C 500
(b) Show that the following optimization problem can be solved by solving one or more LPs.
4A+4B+7C 300 35A+20B+25C 1000
¬(A > 0 ^ B > 0) <≤0
A, B, C 0
t the following optimization problem can be solved by solving one or more LPs.
4A+4B+7C 300 35A+20B+25C 1000
¬(A > 0 ^ B > 0) ?≤0
A, B, C 0
1
1 1
(b) Show that the following optimization problem can be solved by solving
2021-03-10
CSC373 Winter 2021 – Sam Toueg 1 29
1
: l
p t
2
e
Your goal is to find start times s1, s2, . . . , sn for the jobs (no job can start earlier than time 0) such
a
axx2O c2x
o
•O x2O1 2
thYatouthr egotaoltaisl toimfiendtosctaormt ptilmetesasll ,jsob,s. .is. ,ms infiomr itzheed jwobhsil(eneonjsoubricnagntshtatrttheaerplireerrtehqaunistiitme eco0n)ssturachints 12n
artehmateth.eWtortiatel taimlienteoarcopmropglertaemaltlojosboslvisemthinisimpirzoebdlewmhi.le ensuring that the prerequisite constraints are met. Write a linear program to solve this problem.
Q3 Exercises From Class Q3 Exercises From Class
(a) Show that the following optimization problem can be solved by solving one or more LPs. (a) Show that the following optimization problem can be solved by solving one or more LPs.
(b) max 12A+23B·C2 s.t.
LP1 :
max 12A + 23B + 15C 5A+15B+10C500 max12A+23B+15C
4A+4B+7C 300 s.t.
35A+20B+25C 1000 C 2 1,…,100
A, B 0
s.t. 5A+15B+10C 500 5A+15B+10C 500
max12A+23B·C2 Axb^x 0}. Let
⋯
cT x s.t.
1 5A+15B+10C 500
4A+4B+7C 300 Cannot restrict C to integer
Take the best of LP1, …, LP100
4A+4B+7C 300 35A+20B+25C 1000
But we can try 100 LPs with C = 1,…,100
35A+20B+25C 1000
¬(A > 0 ^ B > 0) ¬(A>0^B>0)
A, B, C 0 A, B, C 0
LP100: max12A+23B·C s.t.
2
5A+15B+10C 500 (b) Show that the following optimization problem can be solved by solving one or more LPs.
LP as we maximize a linear objective subject to linear constraints;
(b) Show that the following optimization problem can be solved by solving one or more LPs.
4A+4B+7C 300
1 c2x 35A+20B+25C1000 35A+20B+25C1000
T 4A+4B+7C 300
timal solutions from before, break ties by maximizing another objective;
1 1
C@ =2 1,0.0. . , 100 A, B 0
2 cT3x
her by maximizing yet another objective.
Rn:Axb^x 0}.Let
x 2 O3 by solving one or more LPs.
(c) LetF={x2Rn:Axb^x 0}.Let • O1 = argmaxx2F cT1 x
// This is a usual LP as we maximize a linear objective subject t
C@ =2 1, . . . , 100 A, B 0
axx2F cT1 x
usual LP as we maximize a linear objective subject to linear constraints;
2021-03-10 CSC373 Winter 2021 – Sam Toueg 30
T 2 = arg max cT x