1
$\begingroup$

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

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Would that still work if $y_t$ is continuously zero? I like the approach $\endgroup$
    – PeterD
    Commented Apr 10 at 15:51
  • 1
    $\begingroup$ 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| $ $\endgroup$
    – PeterD
    Commented Apr 10 at 16:03
  • $\begingroup$ @PeterD oh, thanks! I missed the $y_t$ would be continuously zero. I have modified my answer and add your suggesstion. $\endgroup$
    – ytsao
    Commented Apr 10 at 17:46
  • 2
    $\begingroup$ 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? $\endgroup$
    – prubin
    Commented Apr 10 at 18:15
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Demitri
    Commented Apr 11 at 9:35

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