Dealing with non-overlapping constraints

Question

Let us consider the following problem:

Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$ and a target start time $s_t$. No two tasks can be executed in parallel. The objective is to minimize the sum of the absolute deviation between the start time of a task and the target start time.

A possible way to model this problem would be the following:

$\forall t \in T$ let $e_t$ be a linear variable representing the absolute deviation between a task start time and its target start time.

$\forall t \in T$ let $a_t$ be a linear variable representing the actual start time of a task.

$\forall (t_1, t_2) \in T^2$ let $x_{t_1,t_2}$ be a binary variable representing if $t_1$ starts before $t_2$.

Let $M$ be a sufficiently large coefficient.

A possible model is then the following

\begin{align}\min\qquad &\sum_{t \in T}e_t\\\text{s.t.}\qquad&e_t \geq s_t - a_t, \forall t \in T\\&e_t \geq a_t - s_t, \forall t \in T\\&x_{t_1,t_2} + x_{t_2,t_1} = 1, \forall (t_1, t_2) \in T^2\\&a_{t_2} + d_{t_2} \leq a_{t_1} + M \cdot x_{t_1,t_2}, \forall (t_1, t_2)\in T^2\end{align}

Is there a way to deal with the non-overlapping constraints without adding a binary variable for each pair of task?

Answer 1

I do not know of any way of handling this without some sort of variable that sorts out whether $i$ begins before $j$ or vice versa. Given the NP-completeness of the underlying problem, you will need some sort of binary variable in formulating, but there may be other ways than the method you give.

Answer 2

One easy way to convince yourself that this is a non-convex problem - and hence can't be represented without integer constraints, or some other non-convex constraint - is to ask: "If X1 and X2 are both valid solutions, is their average always a valid solution?"

If the problem is convex, the answer must be yes, since that's the definition of convexity. In this case, it's clearly no: there might be valid solutions where task A begins before B, and others where B begins before A, but averaging the starting times results in overlap.

You can squeeze this into a MIP framework by adding some binary variables, but it may be worth considering a constraint solver e.g. Gecode, which specifically supports non-overlap constraints and is programmed to deal with them.

Answer 3

If you have a finite set $I$ of start times, you can introduce a binary variable $y_{t,i}$ that indicates whether task $t \in T$ starts at time $i \in I$. Each task must be assigned exactly one start time: $$\sum_{i \in I} y_{t,i} = 1 \text{ for all } t \in T.$$ Conflicts are then prohibited by clique constraints: $$\sum_{t, i:\ i \le j < i+d_t} y_{t,i} \le 1 \text{ for all } j \in I.$$

Answer 4

Perhaps its possible to solve as is then check the solution for "violations" of the one at a time constraint.

You could then push its start time by adding a constraint that enforces it to start after. Using the third constraint you defined. Plus another to set either $x_{t_1,t_2} = 1$ or $x_{t_2,t_1} = 1$.

This will be highly dependent on data and the solution will be of debatable quality.

Answer 5

There is a nice in-depth review of different MIP formulations for machine scheduling problems by Queyranne and Schulz: https://pdfs.semanticscholar.org/a00d/f7ab46627debbfde11bfe2b019d4d3a5c72d.pdf It is dated, but still relevant today I think.