I want help in formulating a mixed integer linear problem formulation.

Question

I want the following help in linear fashion:

• I have a vector: $P(n) = [1, 2, 3, 4, 5,...,n]$
• I have binary variables with length of $P:y(1),y(2).....y(n)$. These variables, y(i) can only take $0$ or $1$.

A new vector $Q(n)$ is needed, such that, if $y(i)$ is $1$, then the $i^{th}$ element in $Q(n)$ should be $0$. And in rest of the places, the $P(n)$ should get repeated.

• Example : if $n = 6 $ , and $y(1)$ and $y(4)$ are $1$ ,then $Q(1)$ and $Q(4)$, should be $0$. The vector, $Q$ will be as follows :

$Q =$[0 1 2 0 1 2].

• Another example : if $y(3)$ is $1$, then $Q$ should be as follows:

$Q =$[1 2 0 1 2 3].

Basically, beside the zeros on $i^{th}$ position, the vector $P$ should repeat itself in non-zero positions of $Q$

Can you please help me formulating this problem?

Answer 1

In other words, you want to enforce: $$Q_i = \begin{cases} 0 &\text{if $y_i=1$} \\ 1 &\text{if $y_i=0$ and $i=1$} \\ Q_{i-1} + 1 &\text{if $y_i=0$ and $i>1$} \\ \end{cases}$$ You can do this via linear constraints: \begin{align} 1-y_i \le Q_i &\le i (1-y_i) &&\text{for $i\in\{1,\dots,n\}$} \tag1\\ -iy_i \le Q_i - Q_{i-1} - 1 &\le -y_i &&\text{for $i\in\{2,\dots,n\}$} \tag2\\ \end{align}

• If $y_i=1$ then constraint $(1)$ enforces $Q_i=0$ and constraint $(2)$ enforces $-i \le 0-Q_{i-1}-1 \le -1$, which is redundant because $0 \le Q_j \le j$ for all $j$.
• If $y_i=0$ and $i=1$ then constraint $(1)$ enforces $Q_1=1$.
• If $y_i=0$ and $i>1$ then constraint $(2)$ enforces $Q_i=Q_{i-1}+1$ and constraint $(1)$ enforces $1 \le Q_i \le i$, which is redundant.