Some modeling languages and solvers support indicator constraints of the form $$y=\hat{y} \implies \sum_j a_j x_j \le b,$$ where $y$ is a binary decision variable and $\hat{y}\in\{0,1\}$ is a constant. How do I enforce a more general logical implication $$\sum_j a_j x_j \le b \implies \sum_j c_j x_j \le d?$$
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can accomplish this by introducing a binary decision variable and splitting into two implications: \begin{align} \sum_j a_j x_j \le b &\implies y = 1 \tag1\label1 \\ y = 1 &\implies \sum_j c_j x_j \le d \tag2\label2 \end{align} Constraint \eqref{2} is already an indicator constraint. To rewrite \eqref{1} as an indicator constraint, use its contrapositive $$y = 0 \implies \sum_j a_j x_j > b,$$ which you can model as $$y = 0 \implies \sum_j a_j x_j \ge b + \epsilon$$ for some small constant tolerance $\epsilon > 0$. If $\sum_j a_j x_j$ and $b$ are integer-valued, you can take $\epsilon=1$.
Now either use the indicator constraints directly or linearize via big-M: \begin{align} b + \epsilon - \sum_j a_j x_j &\le M_1 y \\ \sum_j c_j x_j - d &\le M_2 (1-y) \end{align}