How to formulate if-then for two sums in an integer program

Question

I have two sets of Boolean variables, $x_1, \dots, x_n$ and $y_1, \dots, y_m$ and a positive integer $b$. I would like to add the constraint:

$$\text{If }\sum_i x_i = b \text{ then }\sum_i y_i > b$$

How can you formulate this as an integer program?

I have seen similar looking questions but as a beginner in OR I can't tell if they apply directly to my question.

Answer 1

The formulation by @joni is correct (+1) but can simplified and modified to use only two new binary variables, as follows. The second $\le$ in $(1)$ is not needed, and the first $\le$ can be replaced with $$(b+1)w_2 \le \sum_i y_i \tag6$$ Now $z_1$ and $(5)$ are no longer needed. You can also eliminate $w_2$, as @joni suggested. Think of $w_2$ as a slack variable for $(4)$, and substitute $w_2=1-w_1-w_3$ throughout, yielding only three constraints: \begin{align} (b+1)(1-w_1-w_3)&\le \sum_i y_i \tag7 \\ b-b w_1+w_3\le\sum_i x_i&\le b-w_1+(n-b)w_3 \tag8 \\ w_1+w_3&\le 1 \tag9 \end{align}

Answer 2

Your constraint is equivalent to the contraposition

$$ \sum_i y_i \leq b \implies \sum_i x_i \neq b. $$

By introducing additional binary variables $z_1, w_1, w_2, w_3$, it can be formulated as follows:

$$ \begin{align} (b+1) (1-z_1) &\leq \sum_i y_i \leq b z_1 + m (1-z_1) \tag{1} \\ b w_2 + (b+1) w_3 &\leq \sum_i x_i \leq (b-1)w_1 + b \cdot w_2 + n \cdot w_3, \tag{2}\\ w_1 + w_2 + w_3 &= 1, \tag{4}\\ z_1 &\leq w_1 + w_3 \tag{5}. \end{align} $$

Answer 3

With many solvers like CPLEX you can directly write logical constraints.

For instance with OPL CPLEX

int n=5;
int m=4;
int b=2;

dvar boolean x[1..n];
dvar boolean y[1..m];

subject to
{
  (b==sum(i in 1..n) x[i]) => (b<=-1+sum(i in 1..m) y[i]);
}

works fine