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$

4 Answers 4

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]).

$\endgroup$
3
  • 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, 2019 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, 2019 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, 2019 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.$$

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
  • 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, 2019 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$ Aug 20, 2019 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, 2019 at 7:57
  • $\begingroup$ What do you mean ? I have a trouble with the juxtaposition of 'precedence' and 'time not taken into account'. $\endgroup$ Oct 22, 2019 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.