1
$\begingroup$

I am working on an optimization problem which has the following constraint:

Let $x_{j}, y_{j}$, $j=1, \ldots, J$ be a set of binary variables, it holds that, for $j', j'' \in J$ fixed, if $$\sum_{j' < j < j''}x_{j} = 0$$ then either $y_{j'} = 0$ or $y_{j''} = 0$.

I know that the implication can be modelled introducing a binary variable $z_{j',j''}$ such that $y_{j} - z_{j',j''} \leq 0$ and $y_{j} + z_{j', j''} \leq 1$, but I do not know how to model the entire constraint formally with the introduction of big-M.

Any help will be appreaciated.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

You want to enforce the following proposition: $$\sum_{j' < j < j''}x_{j} = 0 \implies (y_{j'} = 0 \lor y_{j''} = 0).$$ Equivalently, $$\left(\bigwedge_{j' < j < j''} \lnot x_{j}\right) \implies (\lnot y_{j'} \lor \lnot y_{j''}).$$ Now rewrite in conjunctive normal form: $$\lnot\left(\bigwedge_{j' < j < j''} \lnot x_{j}\right) \lor (\lnot y_{j'} \lor \lnot y_{j''}) \\ \bigvee_{j' < j < j''} x_{j} \lor \lnot y_{j'} \lor \lnot y_{j''}, $$ which immediately yields linear constraints $$ \sum_{j' < j < j''} x_{j} + (1-y_{j'}) +(1-y_{j''}) \ge 1. $$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.