Initializing help system before first use

Binary variables

Topics covered in this section:

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.

At most N of A, B, C,... a + b + c + ...≤ N
At least N of A, B, C,... a + b + c + ...≥ N
Exactly N of A, B, C,... a + b + c + ... = N
If A then B b ≥ a
Not B b- = 1-b
If A then not B a + b ≤ 1
If not A then B a + b ≥ 1
If A then B, and if B then A a = b
If A then B and C; A only if B and C b ≥ a and c ≥ a
or alternatively: a ≤ (b + c)/2
If A then B or C b + c ≥ a
If B or C then A a ≥ b and a ≥ c
or alternatively: a ≥
1
2
· (b+c)
If B and C then A a ≥ b + c - 1
If two or more of B, C, D or E then A a ≥
1
3
· (b + c + d + e - 1)
If M or more of N projects (B, C, D, ...) then A a ≥
b + c + d + ... -M +1
N-M+1

Minimum values

y = min{x1, x2} for two continuous variables x1, x2

  • Must know lower and upper bounds

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

  • Introduce binary variables d1, d2 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{x1, x2, ..., xn}

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

  • See Section General constraints for an alternative formulation via general constraints

Maximum values

y = max{x1, x2, ..., xn} for continuous variables x1, ..., xn

  • Must know lower and upper bounds

    Li ≤ xi ≤ Ui [1.i]

  • Introduce binary variables d1, ..., dn
    di=1 if xi 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]

  • See Section General constraints for an alternative formulation via general constraints

Absolute values

y = | x1 - x2| for two variables x1, x2 with 0 ≤ xi ≤ U

  • Introduce binary variables d1, d2 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]

  • See Section General constraints for an alternative formulation via general constraints

Logical AND

d = min {d1, d2} for two binary variables d1, d2, or equivalently
d = d1 · d2 (see Section Product values), or
d = d1 AND d2 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 {d1, d2, ..., dn}

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

    Note: equivalent to d = d1 · d2 · ... · dn
    and (as a logical expression): d = d1 AND d2 AND ... AND dn
  • See Section Boolean variables for an alternative formulation via Boolean variables

Logical OR

d = max {d1, d2} for two binary variables d1, d2, or
d = d1 OR d2 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 {d1, d2 , ..., dn}

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

    Note: equivalent to d = d1 OR d2 ... OR dn
  • See Section Boolean variables for an alternative formulation via Boolean variables

Logical NOT

d = NOT d1 for one binary variable d1

  • 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: d3 = d1 · d2

  • 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 L1 ≤ ∑i Ai xi ≤ U1 or L2 ≤ ∑i Ai xi ≤ U2 (with U1 ≤ L2)

    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]


© 2001-2022 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.