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

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.

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}

• That's very clever, thank you. I am now wondering which formulation will be most effective for an integer programming solver. May 14 at 21:44
• I wouldn’t expect much difference, but it is worth trying both for comparison. May 14 at 22:23
• @RobPratt, Would you please, is there any reason to don't use the original form of the original expression instead of using contraposition? for example, $\sum_{i} x_{i} = bz$, where $z$ is a binary variable, and adding appropriate corresponding constraints for applying the second part? May 15 at 10:30
• @A.Omidi The choices for $\sum_i x_i$ should be $=b$ and $\not=b$, but your proposal would instead yield $=b$ and $=0$, which is too restrictive. May 15 at 13:18
• So $\sum x_i \in\{0,b,b+1,\dots,n\}$ and $\sum y_i \in\{0,b,b+1,\dots,m\}$? Just based on $\sum x_i$, you could then strengthen $(8)$ by replacing the $-w_1$ in the second part with $-b w_1$. By the way, what do $x_i$ and $y_i$ represent in your problem? May 15 at 17:55

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}

• Thank you. Do you know if there is a proof that 4 is the minimum number of new binary variables you have to introduce? May 14 at 10:14
• In this formulation, you need at least three new binary variables. Note that you can eliminate one variable by substituting (4) into (2).
– joni
May 14 at 10:19

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

• Do you know if this built in method will typically be more/less efficient than the clever formulation from or.stackexchange.com/a/8398/9631 ? May 16 at 9:02
• I don't know CPLEX but it looks like you have defined the $x_i$ to be Booleans but the $y_i$ to be positive integers? Why not have the $y_i$ as Booleans too? May 16 at 9:05
• Hi, I just changed y to boolean too May 16 at 9:22