Assume you have a linear expression, e.g. the summation of a set of decision variables \(\sum_{i}{x_i}\), and you need to detect when it is in the interval \([a, b]\) by capturing that information in a binary variable called \(w\).
Let \( M \) be a sufficiently large constant. First, add auxiliary binary variables \( z_1 \) and \( z_2 \) to the model. Then, the following constraints will force \( w \) to be equal to \( 1 \) if and only if \( \sum_i x_i \in [a, b]\):
- \(a w - M (1-w) \leq \sum_{i}{x_i}\)
- \(\sum_{i}{x_i} \leq b w + M (1-w)\)
- \(\sum_{i}{x_i} - a + 1 \leq M z_1\)
- \(b - \sum_{i}{x_i} + 1 \leq M z_2\)
- \(w \geq z_1 + z_2 - 1\)
To see why this works, consider the following scenarios:
- If \(\sum_{i}{x_i} < a\), then by constraint 1 it holds that binary variable \( w \) equals \( 0 \).
- If \(\sum_{i}{x_i} > b\), then by constraint 2 it holds that binary variable \( w \) equals \( 0 \).
- If \(a \leq \sum_{i}{x_i} \leq b \), then:
- By constraint 3, binary variable \( z_1 \) equals \( 1 \).
- By constraint 4, binary variable \( z_2 \) equals \( 1 \).
- Because both \( z_1 \) and \( z_2 \) equal \( 1 \), then by constraint 5 it holds that \( w \) equals \( 1 \).
Note on infinite bounds:
- If the interval is unbounded above (\(b = +\infty\)), then one must omit constraints 2 and 4, and replace constraint 5 with \(w \geq z_1 \).
- If the interval is unbounded below (\(a = -\infty\)), then one must omit constraints 1 and 3, and replace constraint 5 with \(w \geq z_2 \).
Further Information: