I want to express the following locigal expression in an IP:

$$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in D, i,j \in T, i<j$$

where $x_{dt}$ is a binary decision variable ($x_{dt} \in \{0,1\}$) and $a_{k}$ is a binary parameter.

The meaning should be as follows: $T$ represents a set of timeslots. Whenever something happens at timeslots $i$ and $j$ (i.e. $x_{di} = 1$ for some $d$, $x_{d'j} = 1$ for some $d'$, $i<j$), then there should also something be happening at all timeslots inbetween $i$ and $j$, but only if at timeslot $t$ something can actually happen ($a_t = 1$, otherwise $a_t$ is $0$).

Can anyone tell me how to do this? Thanks in advance!

  • $\begingroup$ What have you tried? Where did you get stuck? Do you know how to represent an arbitrary logical expression in IP? $\endgroup$ – Yuval Filmus Aug 4 '17 at 8:31

Base yourself on the fact that $x_{d,i} \land x_{d',j} $ happens iff $ x_{d,i} + x_{d',j} =2 $.

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \leq \sum\limits_{i<j<k} a_k + (j-i)(2-x_{d,i} - x_{d',j}) $

$\forall (d,d') \in D^2, \forall (i,j) \in T^2, i<j, \sum\limits_{d'' \in D \\ i<j<k} x_{d'',k} \geq \sum\limits_{i<j<k} a_k + (j-i)(x_{d,i} + x_{d',j} - 2) $

Check these equations in two cases : $ x_{d,i} + x_{d',j} =2 $ and $ x_{d,i} + x_{d',j} < 2 $

Depending on your $a_k$ and problem, you may get a better multiplicative constant than $(j-i)$. If you can, do it, otherwise the continuous relaxation is going to suck.


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.