Binary variables
Topics covered in this section:
- Logical conditions
- Minimum values
- Maximum values
- Absolute values
- Logical AND
- Logical OR
- Logical NOT
- Product values
- Disjunctions
- Minimum activity level
- 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 ≥
|
|||
If B and C then A | a ≥ b + c - 1 | ||
If two or more of B, C, D or E then A | a ≥
|
||
If M or more of N projects (B, C, D, ...) then A | a ≥
|
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]
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] - 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 make ≥ MAKEMIN · ifmake [1] make ≤ MAKEMAX · ifmake [2] - The ifmake binary variable also allows us to model fixed costs
- FCOST: fixed production cost
- VCOST: variable production cost
cost = FCOST · ifmake + VCOST · make [3] make ≥ MAKEMIN · ifmake [1] make ≤ MAKEMAX · ifmake [2]
© 2001-2023 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.