Blog Post: Mailbag: Contiguity constraints for project scheduling models

Reader BobD asked me the following question over email:

Actually, I'm having some trouble understanding the original paper "Event-based MILP models for resource-constrained project scheduling problems". Particularly the "On/Off Event-based formulation" constraint's (39) & (40). Would you be willing to answer some of my questions?

Sure! Let’s look at equation 39 as written in the paper:

I have adjusted the equation slightly: as noted in a previous post, the >= should actually be a <=. The rightmost part of (39) says that the condition must hold for each event e, except the first one. The left hand side adds up the decision z_ie’ for all events e’ before e. Remember that z_ie is a boolean (actually 0-1) decision that is true if task i is active during event e. So in plain English: the left hand side is simply the number of periods before event e for which task i is active. For example if task i hasn’t started yet, this will be 0. The right hand side is more complicated – but the important thing to notice is that we are subtracting z_ie and z_i(e-1): the current event and the one before it. The easiest way to understand what’s going on here is to think about the four possible cases. There are four cases because z_ie and z_i(e-1) can take on the values 0 or 1.

• Task i is active during both periods e-1 and e. Then z_ie = z_i(e-1) = 1. That means the right hand side is equal to e. Now look at the left hand side – since it is the number of periods before event e where i is active, there is no way that this value can ever be bigger than e. So in this case, the inequality will always hold.
• Task i is inactive during both periods. This can happen if the task has already finished before event e, or if it has yet to start. In this case,  z_ie = z_i(e-1) = 0 and the right hand side is again equal to e. So again the constraint must hold in this case.
• Task i starts on event e. This means that z_i(e-1) = 0 (since the task has not started yet so it cannot be active) and z_ie = 1. This means that the right hand side is 0. This forces z_ie’ to be 0 for all the periods e’.
• Task i ends on event e. This means that z_i(e-1) = 1 and z_ie = 0. Now the right hand side is 2e, and again this constraint will always hold.

In short, this constraint is a fancy way of making sure that once task is active, it does not become inactive until it is completely finished. Notice that this constraint only considered events before event e (because of the summation in the left hand side). So we need another constraint that considers events after e – this is constraint 40, which has almost the same form. The reason why these constraints are relatively complex is that we need to express everything in terms of linear expressions in the decision variables. Multiplying the right hand side by “e” is a way of writing a conditional (“if-statement”). This is another in a range of “modeling tricks” used for mixed integer programming models. Others were covered on the team blog, and they are readily available elsewhere. I don’t actually remember most of these – I just know they exist. When I want to model something like “max”, “min”, or “if” that is not directly expressible using a linear constraint, I go find a similar model where I have seen it done before and apply the trick to my case.

Samaire Armstrong Selita Ebanks Michael Michele Marisa Tomei Shannyn Sossamon