Rewriting if-then constraints of binary summations

Question

Suppose both $x_{i,j}^{ab}$ and $y_{i,j}^a$ are binaries. Then how can I rewrite the following if-then in linear form?

$\sum_b x_{i,j}^{ab} \ge 1 \implies \sum_{i,j} y_{i,j}^a = 0$

I was thinking of considering an indicator. But is there a better way to not have any additional variables (indicators) and still linearize?

My thought was to have, $\alpha^a$, a binary indicator. Then $\sum_b x_{i,j}^{ab} \ge 1 \implies \alpha^a \quad \&\& \quad \alpha^a \implies\sum_{i,j} y_{i,j}^a \le 0$

Then the first one becomes $1- \alpha^a \le \sum_b x_{i,j}^{ab} $

And the next one becomes $\alpha^a \le \sum_{i,j} y_{i,j}^{a} $

Is this a correct way to rewrite it?

Answer 1

In conjunctive normal form, you want to enforce: \begin{align} &\quad \quad \quad\bigvee_b x_{i,j}^{a,b} \implies \bigwedge_{u,v}\neg y_{u,v}^{a} \quad&\forall a,i,j\\ &\equiv \quad\neg \left( \bigvee_b x_{i,j}^{a,b} \right) \vee \left(\bigwedge_{u,v}\neg y_{u,v}^{a} \right) \quad&\forall a,i,j\\ &\equiv \quad \left( \bigwedge_b \neg x_{i,j}^{a,b} \right) \vee \left(\bigwedge_{u,v}\neg y_{u,v}^{a} \right) \quad&\forall a,i,j\\ &\equiv \quad 1- x_{i,j}^{a,b} + 1-y_{u,v}^{a} \ge 1\quad&\forall a,b,i,j,u,v\\ &\equiv \quad x_{i,j}^{a,b} + y_{u,v}^{a}\le 1 \quad&\forall a,b,i,j,u,v\\ \end{align}

You can verify that this is correct: if any $x$ variable takes value $1$, then all other $y$ variables must equal $0$, which will force the sum to also be $0$.

---

As noted by @RobPratt in the comments below, a more compact (although weaker) formulation can be obtained by aggregating the conflict constraint by summing both sides over $b,i,j$: $$ \sum_{b,i,j}(x_{i,j}^{a,b} + y_{u,v}^{a})\le \sum_{b,i,j} 1 $$

Answer 2

@Kuifje gave a correct formulation without introducing additional variables. To answer your question about the indicator variable approach, what you proposed is not correct.

To enforce $$\sum_b x_{i,j}^{ab} \ge 1 \implies \alpha^a,$$ equivalently consider its contrapositive $$\lnot \alpha^a \implies \sum_b x_{i,j}^{ab} \le 0,$$ which you can enforce via big-M constraint $$\sum_b x_{i,j}^{ab} \le M_1\alpha^a.$$ To enforce $$\alpha^a \implies\sum_{i,j} y_{i,j}^a \le 0,$$ impose big-M constraint $$\sum_{i,j} y_{i,j}^a \le M_2(1-\alpha^a).$$

You can view both of these big-M constraints as aggregations of the following stronger constraints: \begin{align} x_{i,j}^{ab} &\le \alpha^a &&\text{for all $a,b,i,j$}\\ y_{u,v}^a &\le 1-\alpha^a &&\text{for all $a,u,v$} \end{align}

Answer 3

Another way would be by introducing the new binary auxiliary variables $z_{i, j, a}$ and $w_a$ and imply the following constraints:

$$ z_{i,j,a} = 1 \iff\left(\sum_{b} x_{i,j,a,b} \geq 1\right) \quad \forall i,j,a \tag1$$ $$ w_a = 1 \iff\left(\sum_{u,v} y_{u,v,a} = 0\right) \quad \forall a \tag2$$ $$ z_{i,j,a} = 1 \implies w_a = 1 \quad \forall i,j,a \tag3$$

As far as I know, Pyomo has an internal facility to do these kinds of transformations somewhat automatically under a hood. The following snippet code can do this transformation:

model = pyo.ConcreteModel()
model.I = pyo.Set(initialize= range(2))
model.J = pyo.Set(initialize= range(2))
model.A = pyo.Set(initialize= range(2))
model.B = pyo.Set(initialize= range(2))
model.U = pyo.Set(initialize= range(2))
model.V = pyo.Set(initialize= range(2))
model.x = pyo.Var(model.I, model.J, model.A, model.B, domain= Binary, name= "x", bounds=(0, 1))
model.y = pyo.Var(model.I, model.J, model.A, domain= Binary, name= "y", bounds=(0, 1))
@model.Disjunction(model.I, model.J, model.A)
def rule(model, i, j ,a):
    disjunct_A = [
        sum(model.x[i,j,a,b] for b in model.B) == 1, 
        sum(model.y[u,v,a] for u in model.U for v in model.V) == 0
    ]
    disjunct_B = [sum(model.x[i,j,a,b] for b in model.B) == 0,
                  sum(model.y[u,v,a] for u in model.U for v in model.V) >= 1
    ]
    return [disjunct_A, disjunct_B]
@model.Objective(sense=pyo.maximize)
def obj(model):
    return 0
pyo.TransformationFactory('gdp.bigm').apply_to(model)

Answer 4

Try if you want to avoid additional indicator binaries
$ \sum_{ij} y_{ij}^a \le M(1-x_{ij}^{ab}) \quad \forall b,i,j,a$
where $M = \vert i\times j \vert$