# How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $$y_t$$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single timestamp. It can; however, be continuously zero. What I would like to do is to track the very first time that y becomes 1 and the very last time that y becomes 1. An example is shown in the table below. What am I struggling to do is to track the first timestamp at which y becomes 1. My current attempt is to create two more binary variables $$v^1_t$$ and $$v^2_t$$ which should be 1 at the first and last occurrence of $$y_t = 1$$, respectively. I can set $$v^2_t$$ correctly using the following constraint: $$t \cdot v^2_t \geq t \cdot y_t - \sum^{T}_{t'=t+1}{t' \cdot u_t'} \quad \forall t \in T$$

This table shows what the correct behaviour should be.

t 1 2 3 4 5 6 7 8 9 10
y 0 1 0 0 0 0 1 0 1 0
v1 0 1 0 0 0 0 0 0 0 0
v2 0 0 0 0 0 0 0 0 1 0

Is anyone able to provide some guidance on how to formulate constraints to set the $$v^1_t$$ correctly? I have also tried setting $$v^1$$ and $$v^2$$ as continuous variables but I have come up against the same issue in that I can set $$v^2$$ correctly but not $$v^1$$.

My idea was to restrict both two variables in different constraints.

First two constraint is to ensure AT MOST 1 variable can turn on to 1.

Next, if $$y_t$$ is zero, then corresponding variable $$v^1_t$$ and $$v^2_t$$ should be zero.

Last constraint is forward and backward to turn on variable.

Finally, since I thought the third constraints cannot enforce the value perfectly, I use objective function to guide the search the optimal solution.

To indicate the first binary variable as 1:

$$\sum_{t}v^1_t \le 1$$

$$\sum_ty_t \le \sum_t v^1_t \cdot |T|$$

$$y_t \ge v^1_t, \forall t \in T$$

$$\sum^{t'=t}_{t'=1} y_{t'} \ge \sum^{t'=t}_{t'=1}v^1_{t'} \forall t \in T$$

To indicate the last binary variable as 1:

$$\sum_{t}v^2_t \le 1$$

$$\sum_ty_t \le \sum_t v^2_t \cdot |T|$$

$$y_t \ge v^2_t, \forall t \in T$$

$$\sum^{t'=|T|}_{t'=t} y_{t'} \ge \sum^{t'=|T|}_{t'=t}v^2_{t'} \forall t \in T$$

Combine with the objective function as following to enforce the index should be minimum and maximum in $$v^1_t$$ and $$v^2_t$$:

$$\min \sum_t (tv^1_t - tv^2_t)$$

• Would that still work if $y_t$ is continuously zero? I like the approach Commented Apr 10 at 15:51
• Concerning $v_t^1$, I think you would then need to reformulate the first constraint with a $\leq$ and you can add a constraint that assures that $v^1_t$ must be 1 in case there is at least on $y_t$ that is greater zero, e.g. with $\sum^{T}_{t=1}y_t \leq \sum^{T}_{t=1}v^1_{t} \cdot |T|$ Commented Apr 10 at 16:03
• @PeterD oh, thanks! I missed the $y_t$ would be continuously zero. I have modified my answer and add your suggesstion. Commented Apr 10 at 17:46
• Won't the constraint $y_t \ge \sum^{t'=t}_{t'=1}v^1_{t'} \forall t \in T$ force $y_t$ to stay at value 1 in all time periods after the first time it takes value 1?
– prubin
Commented Apr 10 at 18:15
• Thank you for your answer ytsao. I have tested it and it seems to work well for me; however, I have decided to implement the first formulation by xy d in this question or.stackexchange.com/questions/9440/… Commented Apr 11 at 9:35