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 ≤ 3x3.

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 ≥ 2x2+5 is satisfied whenever z = 1, by using the following constraint:

x1 +M(1−z)≥2x2 +5,

where M is any upper bound on the value of 2x2 + 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 +3x3 ≤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 +3x3 −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 + 3x3 ≤ 100 + 0 · Q = 100.