464 Midterm 1

Question 1

Construct linear constraint: x in [a,b]

Answer 1

a <= x <= b

Question 2

Construct linear constraint: x in [a,b] or x in [c,d]

Answer 2

y in {0,1} ay+c(1-y) <= x <= by+d(1-y)

Question 3

Construct linear constraint: x is one greater than a multiple of 3

Answer 3

x-1 = 3y, y in Z

Question 4

Construct linear constraint: x in {2,7,8,12,20}

Answer 4

y in {0,1}^5
x= 2y1+7y2+8y3+12y4+20y5
y1+y2+y3+y4+y5 = 1

Question 5

Construct linear constraint: y <= |x|

Answer 5

w in {0,1}
y-x <= Mw
y+x <= M(1-w)
(M large)

Question 6

Construct linear constraint: Ax <= b or Cx <= d

Answer 6

w in {0,1}
w(Ax) <= b
w(Cx) <= d

Question 7

Construct linear constraints where all variables are binary: x=1 or y=1

Answer 7

x+y >= 1

Question 8

Construct linear constraints where all variables are binary: x=1 xor y=1

Answer 8

x+y=1

Question 9

Construct linear constraints where all variables are binary: exactly 5 of {x1,…,xn} are 1

Answer 9

summation from k=1 to n xk = 5

Question 10

Construct linear constraints where all variables are binary: If x=1 then y=1

Answer 10

x<=y

Question 11

Construct linear constraints where all variables are binary: If x=1 then y=0

Answer 11

x<=1-y

Question 12

Construct linear constraints where all variables are binary: If x1=1 and x2=1 then x3=0

Answer 12

x1+x2+x3<=2

Question 13

Construct linear constraints where all variables are binary: If x1=1 and x2=0 then x3=0

Answer 13

x1-x2+x3<=1

Question 14

Construct linear constraints where all variables are binary: x=y1 or y2

Answer 14

x>= y1
x>=y2
x<=y1+y2

Question 15

Construct linear constraints where all variables are binary: x= y1 and y2

Answer 15

x<=y1
x<=y2
x>=y1+y2-1

Question 16

Construct linear constraints where all variables are binary: x = (not) y

Answer 16

x+y = 1