# (M)ILP overlap of two intervals

I got an ILP Model where $$c_i$$ represents the starting time for a visit$$_i$$. $$c_i$$ is already constraint by a number of constraints, one is $$c_i > 0$$.

I have now outside of my model 0 or multiple desired intervals for the visit$$_i$$, lets call them $$dStart_{ik}$$ and $$dEnd_{ik}$$ where k represents the k-th desired interval. i started by adding two variables per k: $$desiredStart_{ik}$$ and $$desiredEnd_{ik}$$.

I added the constraints

$$desiredStart_{ik} >= dStart_{ik}$$

$$desiredStart_{ik} >= c_{i}$$

$$desiredEnd_{ik} <= dEnd_{ik}$$

$$desiredEnd_{ik} <= c_{i+1}$$

$$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik}$$

with the last constraint, i get the problem if the intervals do not overlap, the $$desiredDuration_{ik}$$ gets negative. So I added a "helper" Variable $$desiredHelper_{ik}$$ to it so it looks like this:

$$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik} + desiredHelper_{ik}$$

The general problem of my model is a minimsationProblem, so I added these two terms to the target function:

$$+100000 \sum_{i=0}^N \sum_{k=0}^N desiredHelper_{ik} -\sum_{i=0}^N \sum_{k=0}^N desiredDuration_{ik}$$

With this formulation I see a problem, it favours solutions where the desired interval is closer by the actual solution. Is there a better formulation? how could I avoid the $$desiredHelper_{ik}$$ variable?

## 1 Answer

In case someone else needs this in the future

I ended up using indicator constraints

$$desiredOverlap_{ik} = 1 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \geq 0$$ $$desiredOverlap_{ik} = 1 \rightarrow desiredDuration_{ik} = desiredEnd_{ik} - desiredStart_{ik}$$ $$desiredOverlap_{ik} = 0 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \leq 0$$ $$desiredOverlap_{ik} = 0 \rightarrow desiredDuration_{ik} = 0$$