3
$\begingroup$

How to model the following "If, then" type constraint?

If $\sum\limits_{i \in I}x_i = 0$ then $\sum\limits_{j \in J}x_{j} = n$

where $x$ are binary variables, $n$ is a known parameter and $I \cap J = \emptyset$?

$\endgroup$
8
$\begingroup$

You want to enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies \sum_{j \in J} x_j = n.$$ Introduce a new binary variable $y$ and enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies y$$ and $$y \implies \sum_{j \in J} x_j = n.$$ For the first implication, conjunctive normal form yields \begin{align} \left(\bigwedge_{i \in I} \lnot x_i\right) &\implies y \\ \neg \left(\bigwedge_{i \in I} \lnot x_i\right) &\lor y \\ \left(\bigvee_{i \in I} x_i\right) &\lor y \\ \sum_{i \in I} x_i + y &\ge 1 \tag1 \end{align} For the second implication, use big-M: $$(0-n)(1-y) \le \sum_{j \in J} x_j - n \le (|J|-n)(1-y) \tag2$$

Note that this formulation works even if $I \cap J \not= \emptyset$.

$\endgroup$
0
5
$\begingroup$

in OPL CPLEX you could directly use logical constraints and write

int m=7;
range r=1..m;

int n=2;

{int} I={i | i in r : i mod 2==1};
{int} J={i | i in r : i mod 2==0};

assert card(I inter J)==0;

dvar boolean x[r];

subject to
{
  (sum(i in I) x[i]==0) => (sum(j in J) x[j]==n);
}
$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .