2
$\begingroup$

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.

$\endgroup$

3 Answers 3

3
$\begingroup$

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}

$\endgroup$
8
  • $\begingroup$ That's very clever, thank you. I am now wondering which formulation will be most effective for an integer programming solver. $\endgroup$
    – graffe
    May 14 at 21:44
  • 1
    $\begingroup$ I wouldn’t expect much difference, but it is worth trying both for comparison. $\endgroup$
    – RobPratt
    May 14 at 22:23
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    May 15 at 10:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – RobPratt
    May 15 at 13:18
  • 1
    $\begingroup$ 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? $\endgroup$
    – RobPratt
    May 15 at 17:55
5
$\begingroup$

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} $$

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

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

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – graffe
    May 16 at 9:02
  • $\begingroup$ 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? $\endgroup$
    – graffe
    May 16 at 9:05
  • 1
    $\begingroup$ Hi, I just changed y to boolean too $\endgroup$ May 16 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.