Q1 Standard Form
CSC373 Fall’20 Tutorial 6 Solutions Oct 27, 2020
Convert the following linear program to the standard form.
min 4x+3y−6z s.t.
y − 3z ≥ 2x + 2 3x + 2y + 5z = 10 x, z ≥ 0
Solution to Q1 First, let us change the objective function to maximization.
max −4x−3y+6z s.t.
y − 3z ≥ 2x + 2 3x + 2y + 5z = 10 x, z ≥ 0
Next, let us address the greater-than-or-equal-to and equal-to constraints; we also bring all variables to the LHS and constants to the RHS.
max −4x−3y+6z s.t.
2x − y + 3z ≤ −2 3x + 2y + 5z ≤ 10
− 3x − 2y − 5z ≤ −10 x, z ≥ 0
Finally, let us address the fact that variable y is unrestricted by replacing y with y′ − y′′, where y′ and y′′ are both non-negative.
1
max −4x−3y′ +3y′′ +6z s.t.
2x − y′ + y′′ + 3z ≤ −2 3x + 2y′ − 2y′′ + 5z ≤ 10
− 3x − 2y′ + 2y′′ − 5z ≤ −10 x,z,y′,y′′ ≥ 0
Q2 Simple Scheduling with Prerequisites (SSP)
You are given n jobs with a list of durations d1,d2,…,dn. For every pair of jobs (i,j), you are also given a boolean pi,j: if this is true, then job i must finish before job j can begin (i.e. job i is a prerequisite for job j).
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 are met. Write a linear program to solve this problem.
Solution to Q2
For each job i, we have a variable si, which is the start time of job i. We also have a variable T, which is an upper bound on the total time to completion. The LP is as follows.
Minimize T
Subject to
T ≥ si + di, for i ∈ {1, 2, . . . , n}
sj ≥ si + di, for i, j ∈ {1, 2, . . . , n} s.t. i ̸= j and pi,j is true si ≥ 0, for i ∈ {1,2,…,n}
Justification: The third constraint ensures that start times are non-negative. The second con- straint ensures that prerequisites are met. The first constraint ensures that T is at least the completion time of each job; hence, T is an upper bound on the overall completion time. If we minimize T subject to this, in the optimal solution T will always be set equal to the overall com- pletion time because there are no other constraints on T. Hence, the optimal solution to this LP finds the minimum overall completion time.
Q3 Exercises From Class
(a) Show that the following optimization problem can be solved by solving one or more LPs.
2
max 12A + 23B + 15C s.t.
5A+15B+10C ≤500 4A+4B+7C ≤300 35A+20B+25C ≤1000 ¬(A > 0 ∧ B > 0)
A, B, C ≥ 0
(b) Show that the following optimization problem can be solved by solving one or more LPs.
max 12A+23B·C2 s.t.
5A+15B+10C ≤500 4A+4B+7C ≤300 35A+20B+25C ≤1000 C ∈ 1,…,100
A, B ≥ 0 (c) LetF={x∈Rn:Ax≤b∧x≥0}.Let
• O1 = arg maxx∈F cT1 x
// This is a usual LP as we maximize a linear objective subject to linear constraints;
• O2 = arg maxx∈O1 cT2 x
// Among the optimal solutions from before, break ties by maximizing another objective;
• O3 = arg maxx∈O2 cT3 x
// Break ties further by maximizing yet another objective.
Show how to find some x ∈ O3 by solving one or more LPs. Solution to Q3
(a) Note that ¬(A > 0∧B > 0) is equivalent to (A = 0)∨(B = 0). Hence, we can solve two LPs, one in which we substitute A = 0 everywhere and another in which we substitute B = 0 everywhere, and take the best of the two solutions.
(b) While we cannot directly restrict C to take integer values, we can try each discrete value of C separately. That is, we can solve 100 different LPs: in LP k, we substitute C = k everywhere (note that this also makes the objective function linear). Once we do this for each k ∈ {1, . . . , 100}, we can take the best solution out of all the LPs.
3
Note: The running time here is proportional to 100. Hence, if all the numbers were part of the input, the running time would not be polynomial in the input length (with C ≤ n, the running time will be proportional to n while the input length will increase as log n).
(c) The trick is to solve three LPs consecutively rather than in parallel as we did in the previous questions.
First, solve LP1:
max cT1 x s.t.
Ax ≤ b x≥0
Note that the feasible region of LP1 is F, so the set of optimal solutions of LP1 is O1. Suppose the optimal objective value of LP1 is v1∗. Then, add the constraint cT1 x = v1∗ to make O1 the feasible region, and maximize cT2 x over this region. That is, we solve LP2:
max cT2 x s.t.
Ax ≤ b
c T1 x = v 1∗ x≥0
Note that the feasible region of LP2 is O1, so the set of optimal solutions of LP2 is O2. Suppose the optimal objective value of LP2 is v2∗. Then, add the constraint cT2 x = v2∗ to make O2 the feasible region, and maximize cT3 x over this region. That is, we solve LP3:
max cT3 x s.t.
Ax ≤ b
c T1 x = v 1∗ c T2 x = v 2∗ x≥0
As before, we have that the set of optimal solutions to LP3 is precisely O3. Hence, any optimal solution x to LP3 satisfies x ∈ O3, as desired.
4