How to find the index of the item, the first time appears?

Question

How to formulate this problem as MIP:

For example, we have the following vector of binary variables: $$ x= [0, 0, 0, 1, 0, 1, 1] $$ How to find out when the first "1" is recorded? For example, the index of the first "1" is 4. How to let the solver return for example, $y =[0, 0, 0, 1, 0, 0, 0].$

Answer 1

Here's a formulation if at least one $x_i$ must be $1$: \begin{align} \sum_i y_i &= 1 \tag1\label1\\ y_i &\le x_i &&\text{for all $i$} \tag2\label2\\ y_i &\le 1-x_j &&\text{for $j<i$} \tag3\label3 \end{align} Constraint \eqref{1} selects exactly one $y_i$ to be $1$. Constraint \eqref{2} enforces the implication $y_i \implies x_i$. Constraint \eqref{3} enforces the implication $y_i \implies \lnot x_j$.

If instead it is possible that $x_i=0$ for all $i$, relax \eqref{1} to $\le 1$ and impose \begin{align} y_i &\ge x_i - \sum_{j<i} x_j &&\text{for all $i$} \tag4 \end{align}

In either case, you can use \eqref{1} to strengthen \eqref{3} as follows: \begin{align} \sum_{i>j} y_i &\le 1-x_j &&\text{for all $j$} \tag5 \end{align}

See How can I strengthen a family of constraints in the presence of a clique constraint?

---

For the general case where $x \equiv 0$ is feasible, PORTA yields the following formulation: \begin{align} \sum_i y_i &\le 1 \\ y_i &\le x_i &&\text{for all $i$} \\ x_i &\le \sum_{j \le i} y_j &&\text{for all $i$} \end{align}

Answer 2

Suppose the index is 1-based and set constant $u_0 = 0$. With binary variables $u_i, y_i, i=1,\dots,n$ and constraints $$ \begin{align} u_i &\geq x_i\\ u_i &\geq u_{i-1}\\ u_i &\leq x_i + u_{i-1}\\ y_i &\leq u_i\\ y_i &\leq 1 - u_{i-1}\\ y_i &\geq u_i - u_{i-1} \end{align} $$ $y_i$ indicate the first $x$.

In logic expressions: $$ u_i = x_i \vee u_{i-1}\\ y_i = u_i \wedge \neg u_{i-1} $$

It is just my first thought and I have no idea if it is efficient.

---

Second formulation: $$ y_i \leq x_i\\ y_i \geq x_i - \sum_{i' < i} x_{i'}\\ y_i \leq 1 - \sum_{i' < i} y_{i'} $$

Answer 3

If number is non-binary, say non negative continuous number $c$, introduce a vector of binary $y_i$ initialized to 0.
Have two binary variables $z_1 \ and z_2$

$c - x_i \le My_{i}$
$x_i - c \le M(1-y_{i})$
$\sum_{j \lt i} y_j \le i \quad \forall i \in\ N$
$y_{i+1}\le y_i \ \forall i \in\ N$: this ensures y turns 0 once c=x and remains 0 for rest of the array.

First index will be $\sum_{j \lt i} y_j$