Integer Linear Programming Modeling

Question 1

Either or constraints

Answer 1

At least 1 constraint hold but not necessarily both

y binary

x1 + x2 >= 2 + My
x2+x3 >= 1 +M(1-y)

thus if y = 0, the second one has its constrained relaxed, if y=1 its the other way around

Question 2

K out of N constraints must hold

Answer 2

have binary y for each constraint concerned

x1 + x2 >= 2 + My

add a constraint sum y <= N-K

y=1 means the corresponding constraint is relaxed, so at most N-K ys can be 1 such that their constraints don’t hold

Question 3

Functions with N possible values

x is this or this or this

Answer 3

let the values be {V1, V2, V3,.. }
ys binary

x = V1 y1 + V2 y2, V3 y3 + ….

sum y = 1
then x will only be able to be = to 1 value

Question 4

Fixed charge problem

Answer 4

if using x adds a cost a fixed cost F
then Min ci xi + F yi
y binary
x <= Myi
thus if y=0, x=0 (it is unused) and there is no F added
if y=1, then x constraint unbounded and F is added to the objective function

Question 5

have z = max(x1,x2)

Answer 5

z >= x1
z >= x2
z <= x1 + My
z <= x2 + M(1-y)
need to be smaller or equal to 1 of the 2, to obey the 2 other rules this will be the max

Question 6

have z = x or y

have z = x and y

Answer 6

OR
z>= x
z >= y
z <= x+Y

AND
z <= x
z<= y
Z >= (x+y -1)

Question 7

model a graph G=(V,E)

to check if can be 3 colorable

Answer 7

Xu,c is a binary variable u are Vertices and c are Colors

adjacent vertices can’t have the same color
thus for each edge u,v and each color c
Xu,c + Xv,c <= 1

vertices can only be assigned 1 color thus
Sum_c Xu,c = 1