5
$\begingroup$

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?

$\endgroup$

4 Answers 4

13
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ your intuition from the RHS of your first implication is very interesting. Thanks for sharing that. Also, I am not sure how the presolver can perform again the huge number of binary variables that imply to the solver from your first transformation. I think the same is for my transformation. $\endgroup$
    – A.Omidi
    May 14, 2023 at 11:54
  • $\begingroup$ Your second (big-M) approach is not sufficient because it enforces $y_{i,j}^a=0$ only for the same $i,j$. But you can obtain a more compact (although weaker) formulation by aggregating your conflict constraint by summing both sides over $b,i,j$. $\endgroup$
    – RobPratt
    May 14, 2023 at 12:41
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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)
$\endgroup$
6
  • $\begingroup$ You want instead the converse of (1), and then you can replace $w$ with $z$ in (2) and omit (3). $\endgroup$
    – RobPratt
    May 14, 2023 at 12:09
  • $\begingroup$ @RobPratt, I actually need to change the $\implies$ into $\iff$. $\endgroup$
    – A.Omidi
    May 14, 2023 at 12:16
  • $\begingroup$ If you want to use $\iff$ in (2), then you might as well replace $w_{i,j,a}$ with $w_a$ because the value will not depend on $i,j$. $\endgroup$
    – RobPratt
    May 14, 2023 at 13:34
  • $\begingroup$ @RobPratt, thanks for pointing this out. I think many of the redundant variables and constraints can be removed through the pre-solving process. Could you please, which one of the three transformations, the first and BigM by Kuifje and the indicator transformation I mentioned, can perform better from the solver side? The first one and the indicator really inject a huge number of boolean variables into the solver. $\endgroup$
    – A.Omidi
    May 15, 2023 at 5:25
  • $\begingroup$ As often happens in MILP, it might be best to try them all and see what happens. My suspicion is that the final (disaggregated) indicator approach in my answer would be best. It introduces only one binary variable per $a$ and fewer constraints than the conflict formulation but is at least as strong (adding the two constraints yields the conflicts). $\endgroup$
    – RobPratt
    May 15, 2023 at 12:49
1
$\begingroup$

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$

$\endgroup$
1
  • 2
    $\begingroup$ This is an alternative aggregation of the conflict constraints, but you need to distinguish between $i,j$ and $u,v$. $\endgroup$
    – RobPratt
    May 14, 2023 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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