5
$\begingroup$

My target is to formulate a binary sequence with fixed size $N$ = 10, such as $[1, 0, 0, 0 ,1, 1, 0, 1, 0, 0]$. However, I want to constrain this sequence so that when 1 appears, it has to appear at least three times; This is partial problem when I formulate my traffic signal optimization problem, in which 1/0 indicates green/red. I need to add such constraint to emulate minimum green time in the real world.

$\endgroup$
6
$\begingroup$

Define a two sets of binary variables : variables $x_i$ take value $1$ if and only if the $i^{th}$ term of the sequence equals $1$, and variable $y$ that takes value $1$ if and only if one of the terms equals $1$.

You want to enforce

$$ y=1 \quad \Longrightarrow \quad \sum_i{x_i} \ge 3 \\ x_i = 1 \quad \Longrightarrow \quad y=1 $$

You can do this with \begin{align*} 3 y &\le \sum_i{x_i} \\ x_i &\le y \quad \forall i \end{align*}


It is not clear in your question if the ones have to be consecutive or not. If they do, then you need to forbid all the patterns that do not satisfy this. @ErwinKalvelagen shows us how to achieve this here:

One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:

$$ -x_t + x_{t+1} - x_{t+2} \le 0 $$

and

$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} \le 1 $$

A little bit of thought is needed to decide what to do at the borders, especially the first time period.

A different approach is detailed here.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you very much for your prompt response. Sorry for the unclear question. The ones must be consecutive in my problem. From my understanding, probably defining variable set of x~i is not necessary since xi would be identical to the original sequence. $\endgroup$ Dec 8 '21 at 15:21
  • 1
    $\begingroup$ yes correct, variables $x_i$ are certainly already defined. $\endgroup$
    – Kuifje
    Dec 8 '21 at 15:26
  • 1
    $\begingroup$ But thank you for sharing the link. The problem the link leads to is just like my problem. $\endgroup$ Dec 8 '21 at 15:31

Your Answer

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

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