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?


Your Answer

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

Browse other questions tagged or ask your own question.