# how to express an intertemporal implication constraint in integer linear programming (ILP)?

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!

• What have you tried? Where did you get stuck? Do you know how to represent an arbitrary logical expression in IP? – 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.