Binary variables

Binary decision variables

• take value 0 or 1
• model a discrete decision
  • yes/no
  • on/off
  • open/close
  • build or don't build
  • strategy A or strategy B

Logical conditions

Projects A, B, C, D, ... with associated binary variables a, b, c, d, ... which are 1 if we decide to do the project and 0 if we decide not to do the project.

Minimum values

y = min{x₁, x₂} for two continuous variables x₁, x₂

• Must know lower and upper bounds

  L1 ≤ x1 ≤ U1	[1.1]
  L2 ≤ x2 ≤ U2	[1.2]

• Introduce binary variables d₁, d₂ to mean

  di	1 if xi is the minimum value;
  	0 otherwise

• MIP formulation:

  y ≤ x1	[2.1]
  y ≤ x2	[2.2]
  y ≥ x1 - (U1 - Lmin)(1 - d1)	[3.1]
  y ≥ x2 - (U2 - Lmin)(1 - d2)	[3.2]
  d1 + d2 = 1	[4]

• Generalization to y = min{x₁, x₂, ..., x_n}

  Li ≤ xi ≤ Ui	[1.i]
  y ≤ xi	[2.i]
  y ≥ xi - (Ui - Lmin)(1 - di)	[3.i]
  ∑i di = 1	[4]

Maximum values

y = max{x₁, x₂, ..., x_n} for continuous variables x₁, ..., x_n

• Must know lower and upper bounds

  Li ≤ xi ≤ Ui

  [1.i]

• Introduce binary variables d₁, ..., d_n
  d_i=1 if x_i is the maximum value, 0 otherwise
• MIP formulation

  Li ≤ xi ≤ Ui	[1.i]
  y ≥ xi	[2.i]
  y ≤ xi + (Umax - Li)(1 - di)	[3.i]
  ∑i di = 1	[4]

Absolute values

y = | x₁ - x₂| for two variables x₁, x₂ with 0 ≤ x_i ≤ U

• Introduce binary variables d₁, d₂ to mean

  d1 : 1 if x1 - x2 is the positive value

  d2 : 1 if x2 - x1 is the positive value

• MIP formulation

  0 ≤ xi ≤ U	[1.i]
  0 ≤ y - (x1-x2) ≤ 2 · U · d2	[2]
  0 ≤ y - (x2-x1) ≤ 2 · U · d1	[3]
  d1 + d2 = 1	[4]

Logical AND

d = min {d₁, d₂} for two binary variables d₁, d₂, or equivalently
d = d₁ · d₂ (see Section Product values), or
d = d₁ AND d₂ as a logical expression

• IP formulation

  d ≤ d1	[1.1]
  d ≤ d2	[1.2]
  d ≥ d1 + d2 - 1	[2]
  d ≥ 0	[3]

• Generalization to d = min {d₁, d₂, ..., d_n}

  d ≤ di	[1.i]
  d ≥ ∑i di - (n - 1)	[2]
  d ≥ 0	[3]

  Note: equivalent to d = d₁ · d₂ · ... · d_n
  and (as a logical expression): d = d₁ AND d₂ AND ... AND d_n

Logical OR

d = max {d₁, d₂} for two binary variables d₁, d₂, or
d = d₁ OR d₂ as a logical expression

• IP formulation

  d ≥ d1	[1.1]
  d ≥ d2	[1.2]
  d ≤ d1 + d2	[2]
  d ≤ 1	[3]

• Generalization to d = max {d₁, d₂ , ..., d_n}

  d ≥ di	[1.i]
  d ≤ ∑i di	[2.i]
  d ≤ 1	[3]

  Note: equivalent to d = d₁ OR d₂ ... OR d_n

Logical NOT

d = NOT d₁ for one binary variable d₁

• IP formulation

  d = 1 - d1

Product values

y = x · d for one continuous variable x, one binary variable d

• Must know lower and upper bounds

  L ≤ x ≤ U

• MIP formulation:

  Ld ≤ y ≤ Ud	[1]
  L(1 - d) ≤ x - y ≤ U(1 - d)	[2]

Product of two binaries: d₃ = d₁ · d₂

• MIP formulation:

  d3 ≤ d1

  d3 ≤ d2

  d3 ≥ d1 + d2 -1

Disjunctions

Either 5 ≤ x ≤ 10 or 80 ≤ x ≤ 100

• Introduce a new binary variable:
  ifupper: 0 if 5 ≤ x ≤ 10; 1 if 80 ≤ x ≤ 100
• MIP formulation:

  x ≤ 10 + (100 - 10) · ifupper	[1]
  x ≥ 5 + ( 80 - 5) · ifupper	[2]

• Generalization to Either L₁ ≤ ∑_i A_i x_i ≤ U₁ or L₂ ≤ ∑_i A_i x_i ≤ U₂ (with U₁ ≤ L₂)

  ∑i Ai xi ≤ U1 + (U2 - U1) · ifupper	[1]
  ∑i Ai xi ≥ L1 + (L2 - L1) · ifupper	[2]

Minimum activity level

Continuous production rate make that may be 0 (the plant is not operating) or between allowed production limits MAKEMIN and MAKEMAX

• Introduce a binary variable ifmake to mean

  ifmake :	0 if plant is shut
  	1 plant is open

  MIP formulation:

  make ≥ MAKEMIN · ifmake	[1]
  make ≤ MAKEMAX · ifmake	[2]

  Note: see Section Minimum activity level for an alternative formulation using semi-continuous variables
• The ifmake binary variable also allows us to model fixed costs
  • FCOST: fixed production cost
  • VCOST: variable production cost
  MIP formulation:

  cost = FCOST · ifmake + VCOST · make	[3]
  make ≥ MAKEMIN · ifmake	[1]
  make ≤ MAKEMAX · ifmake	[2]