CO 250 Winter 2023: Quiz 1 online solutions – evening CO 250 Winter 2023: Quiz 1 online solutions – evening Q6(a). min 10xsa + 80xsc + 40xab + 30xac + 60xbd + 50xbt + 20xcd + 70xdt. Q6(b)-Version 1. xsa +xac +xbd +xdt ≥ 1. Q6(b)-Version 2. xsc +xac +xbd +xbt ≥1 Q6(b)-Version 3. xab +xbd +xdt ≥1 Q7(a). max P4i=1 vixi − pizi. Q7(b)-Version 1. x1 +x2 +y2 +z2 ≤M. Q7(b)-Version 2. x1 +x2 +x3 +y3 +z3 ≤M. Q7(c)-Version 1. Answer: y3 =y2 +z2 −f2(x1 +x2 +y2 +z2). The amount of fuel y3 at the start of the flight from city 3 is equal to the amount of fuel y2 +z2 in the plane right before departure from the second airport minus the amount of fuel f2(x1 +x2 +y2 +z2) that the plane consumes during the second flight, where x1 + x2 + y2 + z2 is the combined weight of cargo and fuel at the time of departure. Q7(c)-Version 2. Answer: y4 =y3 +z3 −f3(x1 +x2 +x3 +y3 +z3). The amount of fuel y4 at the start of the flight from city 4 is equal to the amount of fuel y3 +z3 in the plane right before departure from the third airport minus the amount of fuel f3(x1 +x2 +x3 +y3 +z3) that the plane consumes during the third flight, where x1 + x2 + x3 + y3 + z3 is the combined weight of cargo and fuel at the time of departure. Q8(a)-Version 1. x1 + x2 ≤ 3×3. Q8(a)-Version 2. x1 ≥ x2 + x3. Q8(b)-Version 1. Create an integer variable w ∈ Z and a binary variable z ∈ {0, 1}. Consider the constraint x2 + x3 = 2w + z. Note that z = 0 if and only if x2+x3 is even. We can use z to ensure that the condition x1 ≥ 2×2+5 is satisfied whenever z = 1, by using the following constraint: x1 +M(1−z)≥2×2 +5, where M is any upper bound on the value of 2×2 + 5 − x1 already implicit in the IP, such as M=145(since0≤x1,x2 ≤70). 8jJUrTR5xXP3Vw 8jJUrTR5xXP3Vw Q8(b)-Version 2. Create a binary variable z ∈ {0,1} that indicates if the condition x1 > x2 is satisfied (i.e., x1 + 1 ≥ x2). Consider the following constraints: (1 − z)M + x1 + 1 ≥ x2 x2 ≥ x1 − Lz x2 +3×3 ≤100+(1−z)Q, where M is any upper bound on the value of x2 − (x1 + 1) already implicit in the IP, such as M=70,−Lisanylowerboundonthevalueofx2−x1 suchas−L=−70,andQisanyupper bound on the value of x2 +3×3 −100 such as Q = 180. We can come up with these values of M, L, Q by noting that 0 ≤ x1, x2, x3 ≤ 70. Note that the first two constraints imply that z = 1 if and only if x1 > x2. Thus, the third constraint implies that if x1 > x2, then x2 + 3×3 ≤ 100 + 0 · Q = 100