Integer Linear Programming with binary value variables

Integer Linear Programs are very useful on networking optimization problems. In some of this problems the integers variables are restricted to values {1,0}.

Some of the traditional problems in this variant are:

1. Grouping problem

2. Fixed Charge problem

Yi = 1 if location i is chosen,

Xij = quantity transported from i to j,

Fi = cost to establish factory i,

Cij = cost to transport from factory i to client j,

p = is limit of number of factorys established,

Uij = limit of quantity transported from i to j,

Ai = capacity to be transported in factory i,

Dj = demand of client j,

minimize: Z = ∑Fi.Yi + ∑Xij.Cij,

subject to: ∑Yi ≤ p,

Xij ≤ Uij,

∑Xij ≤ Ai.Yi ∀ i ∈ Z,

∑Xij ≥ Dj ∀ i ∈ Z

Xij ≥ 0 , Yi = {1,0}

3. Travel Salesman problem

4. Jobshop scheduling problem

Contains "either/or" constraints where a variable M which should approximate ∞ is added in order to make a constraint always true or always false in its inequalities.

From this video

another interesting studying aid:

Hillier, F.; Lieberman, G. & Liberman, G. (1990), Introduction to operations research, McGraw-Hill New York.