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

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].$$

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 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

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}

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}

• Thank you so much. Constraints 1-3 solve the problem. Yes, it is possible that $xi=0$ for all $i$. In that case, I believe you mean replacing constraint 1 with constraint 4 and constraint 3 with constraint 5. I mean, solve the problem with constraints 2, 4, and 5. That also solves the problem in less computation time since it reduces the number of constraints! I am wondering what you mean by " strengthen." Do you mean reducing the number of constraints? Dec 1, 2022 at 21:05
• If you impose $(2)$, $(4)$, and $(5)$, you can omit $(1)$, which is dominated by $(5)$, and you end up with the second formulation by @xdy. By strengthen, I mean that the LP feasible region is smaller, cutting off more fractional solutions. Dec 1, 2022 at 21:18
• Thank you! @ RobPartt. The PORTA formulation you suggested might be the best as it requires fewer constraints than all other formulations. Dec 4, 2022 at 0:12
• More importantly, the PORTA formulation yields the integer hull, so there are no fractional extreme points. Dec 4, 2022 at 0:19

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'}$$

• +1. We had similar ideas for your second formulation. I suspect that your first formulation will scale better, with only $O(n)$ constraints, each of which is sparse. Dec 1, 2022 at 15:05
• Thanks! Both formulations work. As @ RobPratt mentioned, the second formulation is expected to be better as it has less number of constraints and binary variables. Dec 2, 2022 at 3:04
• Yes but I just found the last constraint in the second formulation is stupid and could be replaced by $\sum y_i \leq 1$...
– xd y
Dec 2, 2022 at 3:13
• Thanks, @ xd y. It could be replaced, but both solve the problem. Thank you so much for your help! Dec 3, 2022 at 23:00

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$$

• Thanks! Sutanu. I believe that your first two constraints contradict each other. Dec 1, 2022 at 22:27
• if $c-x_i > 0$ then $y_i$ has to be 1, then $x_i-c <0, y_i$ is free to be 1. Vice-versa, in other words if $c \neq x_i$ y is 1. When $c=x_i$ then possible $y_i = 0$, that will be forced by last constraint. Dec 1, 2022 at 22:32
• Let me get back to you. Dec 2, 2022 at 1:48
• Obj should be =gp.quicksum(B[i] for i in range (len(x))) or simple B.sum(). Also you are trying to determine first index for C=1 in the array, x. I don't think 1 is there in the array. I have added one more constraint B[i+1]<=B[i] for i in range(len(x))-1 Dec 2, 2022 at 3:47
• Ok my bad, I thought you are comparing with cost. Dec 3, 2022 at 1:29