16
$\begingroup$

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to model some precedence constraints for certain jobs.
Due to the rest of the model I have to use binary variables $s_{jt}$ that are 1 if job $j\in J$ starts in time bucket $t\in T$. Suppose I furthermore have a set $P$ of tuples of jobs $(j_1, j_2)\in P\subset J\times J$ for which the second has to start after the first is finished. Each job $j$ has duration $d_j$, i.e the number of time buckets that are needed to finish the job.

My question is how to model the precedence constraint using the above variables (plus maybe some additional ones) in the most efficient and/or effective way. Meaning I'm interested in the smallest formulation but also in the formulation that gives the tightest bound, respectively the fastest solving times when solved with a MIP solver.

$\endgroup$
14
$\begingroup$

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation.

Let $s'_{jt}$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or before). In that case, your precedence constraint can be formulated as $$s'_{j_2,t} \leq s'_{j_1,t-d_1}$$

Notice that you can do a change of variables ($s_{j,1}=s'_{j,1}$ and $s_{j,t} =s'_{j,t}-s'_{j,t-1}$) to write the remaining constraints with these new variables. You also need to add constraints $s'_{j,t}\leq s'_{j,t+1}$.

This usually provide a very tight bound, specially if the number of precedence constraints is very large and the additional constraints are just a few (see [1]).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Hi @Borelian, unfortunately this will not work due to the other constraints that I have. But nice to know nonetheless... Might be helpful for other similar problems. $\endgroup$ – JakobS Aug 17 '19 at 21:29
  • 1
    $\begingroup$ Yes @jakobs, but note that you can do a change of variables $s_{j,t} =s'_{j,t}-s'_{j,t-1}$ and use the same original constraints but with more terms.. $\endgroup$ – Borelian Aug 17 '19 at 21:32
  • $\begingroup$ Ah nice! Did not see that. Can you add this to your answer? It would make it more self-contained... $\endgroup$ – JakobS Aug 17 '19 at 21:36
11
$\begingroup$

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_{j_1,t_1}+s_{j_2,t_2}\le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$\sum_{t\ge t_1}s_{j_1,t}+\sum_{t\le t_2}s_{j_2,t}\le 1.$$

| improve this answer | |
$\endgroup$
5
$\begingroup$

May I suggest CP-SAT modeling. See this incomplete section. And a few examples:

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Hi @Laurent, I've also got a CP model for the problem and, of course, there the precedence constraints are somewhat easier to handle. But then other constraints are more difficult to apply. So I try to check out different ways to model the problem and use the one that works best (or even use several and exchange information (solutions, bounds, etc.)). $\endgroup$ – JakobS Aug 20 '19 at 8:23
  • $\begingroup$ Which kind of constraints ? Except floating points computation, CP-SAT offers the same API as a MIP solver, and internally, it reuses a lot of MIP techniques. $\endgroup$ – Laurent Perron Aug 20 '19 at 14:23
  • $\begingroup$ @LaurentPerron, would you have some examples using Python for precedence constraints when the time is not taken into account? $\endgroup$ – campioni Oct 22 '19 at 7:57
  • $\begingroup$ What do you mean ? I have a trouble with the juxtaposition of 'precedence' and 'time not taken into account'. $\endgroup$ – Laurent Perron Oct 22 '19 at 9:26
3
$\begingroup$

The smallest formulation will be with these constraints:

$$\sum_{t}t\cdot s_{j_1,t} + p_{j_1}\leq \sum_{t}t\cdot s_{j_2,t},\quad \forall (j_1,j_2)\in P$$

However, much stronger LP relaxation will be with constraints

$$\sum_{t'\leq t}s_{j_1,t'}\geq \sum_{t'\leq t+p_{j_1}}s_{j_2,t'},\quad \forall (j_1,j_2)\in P, \forall t$$

(or its equivalent form suggested by @Borelian, which produces a much sparser matrix).

Having to handle precedence constraints usually makes a scheduling problem much more complicated when solved by MIP approaches. So a CP approach can be more efficient, as suggested by @Laurent.

| improve this answer | |
$\endgroup$

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.