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 1


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$


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.