5
$\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 that 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$
  • $\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$ – vrugtehagel Mar 9 '17 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 '17 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 '17 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.