Q1 Standard Form
CSC373 Fall’21 Tutorial 5 Solutions Nov 1, 2021
Consider the following linear program.
min 4x+3y 6z s.t. y 3z 2x+2
Copyright By PowCoder代写 加微信 powcoder
3x + 2y + 5z = 10 x, z 0
(a) Convert this LP into the standard form. (b) Write the dual of the LP from Part (a).
Solution to Q1
(a) (In an assignment or exam, you do not necessarily need to show the following calculations.
Simply writing the final LP in the standard form would su ce.) 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
Finally, let us address the fact that variable y is unrestricted by replacing y = y0 y00, where y0 and y00 are both non-negative.
max 4x 3y0 +3y00 +6z s.t. 2x y0 + y00 + 3z 2
3x + 2y0 2y00 + 5z 10
3x 2y0 + 2y00 5z 10
x,z,y0,y00 0
(b) In the final LP above, let the multipliers corresponding to the three constraints be 1, 2, and
3. Then, dual is as follows:
min 2 1 + 10 2 10 3 s.t. 2 1 +3 2 3 3 4
1 +2 2 2 3 3 1 2 2 +2 3 3
3 1 +5 2 5 3 6 1, 2, 3 0
Note that since the primal has four variables and three constraints, the dual has three variables and four constraints.
Note that the second and the third constraint, together, are equivalent to 1 2 2 + 2 3 = 3. These constraints correspond to y0 and y00, which were introduced to handle an unrestricted variable y.
Similarly, note that in the dual LP, the coe cient of 2 is always the negative of the coe cient of 3. Hence, we can replace 2 3 by a single unrestricted variable, say, 4. Note that 2 and 3 correspond to the two constraints that were created by replacing a single = constraint.
In class, we only saw how to construct a dual LP given a primal LP in the standard form. There are direct ways to construct duals from LPs that are not in the standard form, where unrestricted variables in the primal become equality constraints in the dual, equality constraints in the primal become unrestricted variables in the dual, and more. I highly encourage you to check these out. A good reference is https://jeffe.cs.illinois.edu/teaching/algorithms/notes/H-lp.pdf (Page 10).
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 2 {1, 2, . . . , n}
sj si + di, for i, j 2 {1, 2, . . . , n} s.t. i 6= j and pi,j is true si 0, for i 2 {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 Integer Linear Programming
Suppose you are writing down a binary integer linear program (i.e., an optimization problem with a linear objective, linear constraints, and each variable taking a value in {0, 1}). Three of the binary variables in your program are x, y, and z; you have already placed the constraint: x, y, z 2 {0, 1}.
Now, you want to encode the following relationships between x, y, and z. Show how to do so using linear constraints. Briefly justify your answers.
(a) LogicalAND,z=x^y:Youwantztobe1wheneverbothxandyare1,and0otherwise. (b) LogicalOR,z=x_y: Youwantztobe1wheneveratleastoneofxandyis1,and0
otherwise.
(b) Logical NOT, z = ¬x: You want z to be 1 whenever x is 0, and 0 otherwise.
Solution to Q3
(a) We use the following three constraints. Note that when x = 0 or y = 0, the only feasible value of z satisfying these constraints is z = 0. On the other hand, when x = y = 1, the only feasible value of z satisfying these constraints is z = 1.
zy z x+y 1
(b) We use the following three constraints. Note that when x = 1 or y = 1, the only feasible value of z satisfying these constraints is z = 1. On the other hand, when x = y = 0, the only feasible value of z satisfying these constraints is z = 0.
z x z y zx+y
(c) This is much simpler. We simply use z = 1 x. Note that when x = 0, we force z = 1, and when x = 1, we force z = 0.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com