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$
6
  • 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 '20 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 '20 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$ Mar 29 '20 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 '20 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 '20 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\}$.

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