# Precedence constraints using binary variables - DOCPLEX

I would like to establish a precedence constraint to ensure the precedence relation of tasks. I have a set of tasks available, but required tasks are not always the same. It means, the tasks executed will depend of the demand.

When I searched for examples of precedence constraints in CPLEX/DOCPLEX and also OR-TOOLS, all examples I found use interval variables for establishing precedence constraints. In my case, I don't have interval variables, just binary ones.

I tried to implement the following precedence constraint:

  for t1 in required_tasks:
for w in range(1, len(task_cost) + 1):
for j1 in range(1, number_tasks + 1):
for j2 in range(1, number_tasks + 1):
if j1 < j2:
X[t1, w, j1] *
precedence[t1, t2]
>= X[t2, w, j2]
)


Some definitions:

• X is a binary variable

• w is the worker index

• t1 and t2 are task indexes

• j1 and j2 are the positions of the tasks in the sequence

• preced_task is a dictionary containing the precedence relation.

preced_task = {1: [], 2: [1], 3: [2], 4: [], 5: [], 6: [], 7: []}


When I consider j1 and j2 in range(1, number_tasks + 1) it does not return a solution. However, if I consider j1 and j2 in range(2, number_tasks + 1) it returns a solution respecting precedence for one task (2, for example), but not for task 3.

Could someone help me with that? Thanks in advance!

• Would you see the resources-constraint project schedule or other related scheduling problem such as flowshop? They contain task precedence constraints (using binary variables) which you could benchmark. – A.Omidi Nov 28 '19 at 14:48
• Your preced_task keys are (1, 2, ..) and I assume X index starts from 0. Are you sure then you're correctly indexing X? Also, this is just a suggestion about implementing your constraint. You have 5 loops and you only have a handful of values in preced_task. So, I suggest changing the order of your loops. Loop over your preced_task which gives you only those keys and values that you need and then for the desired j1 and j2 indices coming from preced_task, you can create your constraint. – EhsanK Nov 28 '19 at 15:56
• @A.Omidi, thanks for replying. I took a look at the references you suggested me in another post (or.stackexchange.com/questions/3055/…), but I was looking for some code examples. In the tutorial of Philippe Laborie he used interval variables to establish precedence constraints... – campioni Dec 1 '19 at 13:41
• @EhsanK I'm not sure I understood your answer. X is a decision variable and its index is based on t, w and j. All of them start from 1. – campioni Dec 1 '19 at 13:42
• @campioni I didn't know how you defined x. That was just a check to make sure the index problem is not coming from x being defined on a different range. Anyway, it seems you figured out a solution. – EhsanK Dec 1 '19 at 14:56

After a while, I finally found a way to establish a precedence constraint using binary variables. It was hard to find examples of precedence constraints that do not use time as a parameter in both theoretical models and also code implementation tutorials.

Anyway, I am sharing here the code I used in DOCPLEX to establish the precedence constraint with binary variable without using time, but just process plan position as a parameter. I hope it will help other people dealing with similar problems.

for t1 in required_tasks:
for j2 in range(1, number_tasks + 1):
opt_model.sum(
X_var[t1, w1, j1]
for w1 in range(1, len(workers) + 1)
for j1 in range(1, j2)
)
>= opt_model.sum(
X_var[t2, w2, j2] * precedence[t1,t2]
for w2 in range(1, len(workers) + 1)

)
)


PS: precedence is a dictionary showing the precedence relation between t1 and t2. If t1 must be done before t2, precedence[t1, t2] = 1, and 0 otherwise.