3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Richard Mar 29 at 21:58
  • $\begingroup$ 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 $\endgroup$ – Vinay Mar 29 at 22:06
  • $\begingroup$ 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? $\endgroup$ – Oguz Toragay Mar 29 at 22:16
  • $\begingroup$ 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[16] < a[8] $\endgroup$ – Vinay Mar 29 at 22:38
  • $\begingroup$ 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? $\endgroup$ – A.Omidi Mar 30 at 0:10
7
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are spot on $\endgroup$ – Vinay Mar 30 at 1:23
  • $\begingroup$ OK, now is $a_i$ given or a decision variable? $\endgroup$ – RobPratt Mar 30 at 1:34
  • $\begingroup$ a[i] is given. It's not a decision variable. $\endgroup$ – Vinay Mar 30 at 1:37
  • $\begingroup$ 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. $\endgroup$ – Vinay Mar 30 at 2:50
  • $\begingroup$ 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? $\endgroup$ – Vinay Mar 30 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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