7
$\begingroup$

Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in successive sequence. That is, if the maximum number of consecutive ones is three then a solution with the sequence $x_i = 1, x_{i+1}=1, x_{i+2} = 1, x_{i+3}=1$ is unfeasible (4 consecutive ones in sequence).

One way to model this (I think) is to add constraints for every interval $[i, i+3]$ of length four periods so that it can have the sum of at most 3. E.g.

\begin{align} x_1+x_2+x_3+x_4 &\leq 3 \\ x_2+x_3+x_4+x_5 &\leq 3 \\ &\vdots \\ x_{n-3}+x_{n-2}+x_{n-1}+x_n &\leq 3 \end{align}

But I know you can do smart things with integer programming, so I'm wondering can this constraint be modeled more easily.

$\endgroup$
3
  • $\begingroup$ You could keep track of where the last $0$ was and when finding the next, compare its index to the last, and if the difference is more than $3$, the sequence is unfeasible. However this seems more of a programming problem rather than a mathematics problem and as such you should consider posting it on stackoverflow.com instead. $\endgroup$
    – user304329
    Mar 9, 2017 at 10:28
  • 1
    $\begingroup$ @vrugtehagel That is a good idea, but I don't see how that can be achieved with linear constraints. With additional binary variables maybe, but I don't see it. $\endgroup$
    – ELEC
    Mar 9, 2017 at 10:31
  • 3
    $\begingroup$ Your way of modeling it is correct, and not that expensive in terms of number of constraints. Are you looking for valid inequalities to strengthen your description ? $\endgroup$
    – Vincent
    Mar 10, 2017 at 12:23

2 Answers 2

1
$\begingroup$

There is a way to deduce these constraints. You want

$$x_i=1, x_{i+1}=1, x_{i+2}=1 \implies x_{i+3}=0, ~ \forall i\in I_{n-3}$$

Let $p_i$ be a logical variable meaning ($p_i$ is $x_i$ and $\neg p_i$ is $1-x_i$).

$$p_i \wedge p_{i+1} \wedge p_{i+2} \implies \neg p_{i+3}, ~ \forall i\in I_{n-3}$$

$$ \neg (p_i \wedge p_{i+1} \wedge p_{i+2}) \vee \neg p_{i+3}, ~ \forall i\in I_{n-3}$$

applying De Morgan's law

$$\neg p_i \vee \neg p_{i+1} \vee \neg p_{i+2} \vee \neg p_{i+3}, ~ \forall i\in I_{n-3}$$

$$(1-x_i) + (1-x_{i+1}) + (1-x_{i+2}) + (1-x_{i+3}) \geq 1, ~ \forall i\in I_{n-3}$$

$$x_i + x_{i+1} + x_{i+2} + x_{i+3} \leq 3, ~ \forall i\in I_{n-3}$$

I think this is the best way.

$\endgroup$
0
$\begingroup$

The answer to this question depends on what kinds of descriptions are taken into consideration (with or without auxiliary variables) and how the complexity of a description is measured. Here is an answer in the case of descriptions in the original space (that is, no auxiliary variables are introduced) whose complexity is measured in terms of the number of inequalities. In this setting, one can show that the set in question will not have a significantly more concise description than the natural one.

Consider integer values $n$ and $k$ with $0 < k < n$. Within the ambient set $\{0,1\}^n$ of binary vectors, the set $X$ of all $x \in \{0,1\}^n$ that have at most $k$ consecutive ones can be described by a system of $n-k$ linear inequalities but cannot be described by a system of fewer than $\lfloor (n + 1 - k) / 2 \rfloor$ linear inequalities.

The system of $n-k$ linear inequalities $$ \sum_{j=i}^{i+k} x_j \le k \qquad (i=1,\ldots,n-k) $$ describes $X$ within $\{0,1\}^n$ since the $i$-th inequality of this system rules out $k+1$ consecutive ones in the components from $i$ to $i+k$.

Consider an arbitrary linear system $Ax \le b$ of $m$ inequalities, with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, that describes $X$ as $X = \{ x \in \{0,1\}^n \,:\, A x \le b\}$. A lower bound on $m$ can be derived using the set $$ Y = \{ (\underbrace{0,\ldots, 0}_{2(i-1)}, \underbrace{1,\ldots,1}_{k+1},\underbrace{0,\ldots,0}_{n-2i+1}) \,: \, i = 1,\ldots, \lfloor (n+1 - k) /2 \rfloor \}. $$ Vectors in $Y$ have exactly $k+1$ consecutive ones preceded by an even number of zeros. Clearly, $X$ and $Y$ are disjoint subsets of $\{0,1\}^n$. It suffices to show that no inequality in the system $Ax \le b$ separates more than one point of $Y$. To see this, pick two arbitrary distinct points $p$ and $q$ in $Y$ and generate out of $p$ and $q$ points $p'$ and $q'$ by an exchange of the components between $p$ and $q$ at two positions: the first and the last position at which the components of $p$ and $q$ differ. For example, if $n=6$, $k=3$, $p= ( \color{red} 1,\color{red} 1, \color{red} 1,\color{red} 1, \color{red} 0, \color{red} 0)$ and $q=( \color{blue} 0, \color{blue} 0, \color{blue} 1, \color{blue} 1, \color{blue} 1, \color{blue} 1)$, then $p' = (\color{blue} 0, \color{red} 1, \color{red} 1, \color{red} 1,\color{red} 0,\color{blue} 1)$ and $q' = (\color{red} 1, \color{blue} 0, \color{blue} 1, \color{blue} 1, \color{blue} 1, \color{red} 0).$ It is clear that $p+ q = p' + q'$ and that $p',q' \in X$. For an arbitrary inequality $a_i x \le b_i$ of the system $Ax \le b$ one has $a_i p' \le b_i$ and $a_i q' \le b$ since the system is valid on $X$. This implies $a_i \cdot ( (p'+q')/2) \le b_i$. In view of $p+q = p'+q'$, one has $a_i \cdot ( (p+ q)/2) \le b_i$. Hence, one has $a_i p \le b_i$ or $a_i q \le b_i$, which means that the inequality $a_i x \le b_i$ cannot separate both $p \in Y$ and $q \in Y$ from $X$. It follows that $Ax \le b$ has at least $|Y| = \lfloor (n+1 - k) /2 \rfloor$ inequalities.

$\endgroup$

You must log in to answer this question.

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