How to write a LP/MIP to mark the items in a time-series list after a fixed delta?

Question

I have a time series list like this.

a = [1.1341, 1.13421, 1.13433, 1.13412, 1.13435, 1.13447, 1.13459, 1.13452, 1.13471, 1.1348, 1.13496,1.13474,1.13483,1.1349,1.13502,1.13515,1.13526,1.13512]

How to write constraints to mark after every 0.0005 change in this list using a LP/MIP (series is not sorted and order matters)

For example, |a[0] - a[8]| = 0.00061 > 0.0005 and |a[16] - a[8]| = 0.00055 > 0.0005

It's possible a[16] < a[8]. If MIP can be formulated such that output[16] = -1, it is most appreciated but just binary is also fine.

I am expecting something like the following. Output is the control variable in LP/MIP.

Is it possible to solve this just with constraints and without an objective function?

I want to solve this in CPLEX. Ideally I would like to formulate in regular LP/MIP but constraint programming is also fine.

Answer 1

For each $i$, let binary decision variable $x_i$ be your desired output[i]. If I understand correctly, you want $x_0=1$, and for each $i<j$, you want $$(x_i,x_{i+1},\dots,x_{j-1},x_j)=(1,0,\dots,0,1)\iff \left(\bigwedge_{k=i+1}^{j-1} (|a_i-a_k|\le 0.0005) \land |a_i-a_j|> 0.0005\right).$$ Because $a_i$ is given, there is no decision to be made. You can fix all $x_i$ up front, before calling any solver:

x[0] = 1
c = a[0]
for i = 1 to n
   if |c - a[i]| > 0.0005
      x[i] = 1
      c = a[0]
   else 
      x[i] = 0
   endif
endfor

---

Update now that $0.0005$ is replaced with decision variable $\delta\in [0,U]$

Let $\epsilon>0$ be a small constant. For each $i<j$, let binary decision variable $z_{i,j}$ indicate whether $|a_i-a_j| \le \delta$. The following constraints enforce the desired relationship between $z$ and $\delta$: \begin{align} |a_i-a_j|z_{i,j} &\le \delta &&\text{for $i < j$}\\ -|a_i - a_j| + \delta + \epsilon &\le (-|a_i - a_j| + U + \epsilon)z_{i,j} &&\text{for $i < j$} \end{align}

To enforce the logical proposition $$\left(x_i \land \bigwedge_{k=i+1}^{j-1} z_{i,k} \land \neg z_{i,j}\right) \implies x_j,$$ impose the following additional constraint: $$x_i + \sum_{k=i+1}^{j-1} z_{i,k} + (1 - z_{i,j}) - (j - i) \le x_j$$

Now the problem is to minimize the longest streak length $s$ subject to the above constraints and the following min-max constraints: $$s \ge k \left(\sum_{j=i}^{i+k-1} x_j - k + 1\right)$$ for all $i\in\{0,\dots,n\}$ and $k\in\{1,\dots,n-i+1\}$.