1
$\begingroup$

Suppose we have $S=\{1,2,\ldots,n\}$, a binary variable $x$ and an integer $p$. I would like to model the following constraint using integer linear programming:

If $x = 1$, then there must exists a unique $i\in S$ such that: $x_j=1$ for all $j\in\{i,i+1,\ldots,i+p-1\}$.

How can I do this?

$\endgroup$
2
  • $\begingroup$ Is $x$ a scalar or a vector? $\endgroup$ Commented Apr 11, 2017 at 9:07
  • $\begingroup$ $x$ is a scalar $\endgroup$
    – Zir
    Commented Apr 12, 2017 at 1:24

1 Answer 1

3
$\begingroup$

Assuming $x_j$ are binary.

The additional binary variable $y_i$ equals one if and only if when all $j$ are 1.

$$ \sum\limits_{j=i}^{i+p-1}x_j - p+1 \leq y_i \leq \frac{1}{p}\sum\limits_{j=i}^{i+p-1}x_j $$

Then to have a unique $y_i$ equals one you add $$ x \leq \sum_{i=1}^n y_i \leq (n-1)(1-x)+1 $$

$\endgroup$
1
  • $\begingroup$ Can be done hopefully better (tighter) if the objective is known. $\endgroup$
    – Eugene
    Commented Apr 10, 2017 at 2:38

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.