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

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 - a| = 0.00061 > 0.0005 and |a - a| = 0.00055 > 0.0005

It's possible a < a. If MIP can be formulated such that output = -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.

• It might be useful to explain briefly why you must use an LP/MIP solver for this. There are efficient sort+DP solutions, of course. – Richard Mar 29 '20 at 21:58
• This is a part of a bigger problem which is MIP. I want to see if it's possible to write a constraint so that I can use it with rest of the MIP. Also, I am not familiar with DP – Vinay Mar 29 '20 at 22:06
• so in your example list a, split form of the list should be: a1= [1.1341, 1.13421, 1.13433, 1.13412, 1.13435, 1.13447, 1.13459, 1.13452, 1.13471], a2= [ 1.1348, 1.13496,1.13474,1.13483,1.1349,1.13502,1.13515,1.13526,1.13512] and a3=[1.13512] Is it the solution that you are looking for? – Oguz Toragay Mar 29 '20 at 22:16
• You can say so. I am expecting a variable list like [1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,-1,0] once it is solved given a < a – Vinay Mar 29 '20 at 22:38
• If I understand your question as well, you would need to determine the sequence of the situations, in which the minimum absolute difference is at least 0.0005 between two numbers. Would you see this result that, it's what you are looking for? – A.Omidi Mar 30 '20 at 0:10

## 1 Answer

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, 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 = 1
c = a
for i = 1 to n
if |c - a[i]| > 0.0005
x[i] = 1
c = a
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, 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\}$$.

• You are spot on – Vinay Mar 30 '20 at 1:23
• OK, now is $a_i$ given or a decision variable? – RobPratt Mar 30 '20 at 1:34
• a[i] is given. It's not a decision variable. – Vinay Mar 30 '20 at 1:37
• Is there a way to write it as a constraint. My actual problem is identify delta(0.0005) to minimize the longest streak of 1 in x. That's why I want this problem solution as a constraint instead of a loop assignment. – Vinay Mar 30 '20 at 2:50
• I tried to implment this solution in CPLEX and ORTOOLS but I could not get the desired result. Is there any constraint I am writing wrong? – Vinay Mar 30 '20 at 12:50