Integer Linear Programing - Using Binary Vaviables

Some tips about ILP transformaion using binary variables.

- Logic
  - Conjunction, A and B, A∩B => a+b = 2
  - Disjunction, A or B, A∪B => a+b ≥ 1
  - if A then B, A→B, ~A∪B => a ≤ b
  - A if only if B, A↔B => a = b
  - A = ~B => a+b = 1
  - C = A∩B => c ≤ a, c ≤ b, c ≥ a+b-1
  - C = A∪B => c ≥ a, c ≥ b, c ≤ a+b

---

- either-or constraint
        a1+b1 ≤ c1  or  a2+b2 ≤ c2

  =>  a1+b1 ≤ c1 + My
         a2+b2 ≤ c2 + M(1-y) , M is a massive number, y is binary

---

- p out of m constraints hold
        fi(x) ≤ bi, i = 1, 2, ..., m

  => fi(x) ≤ bi + Myi
       Σyi = m - p, i = 1, 2, ..., m, M is a massive number, yi is binary

---

- Functions with n possible values
      f(x) = b1 or b2 or b3, ... or bn

  => f(x) =  Σbiyi
        Σyi = 1, i = 1, 2, ..., n, yi is binary