Modeling Local Politicians with Global Constraints; or Making it for 2014 Cup and 2016 Olympics: Scheduling Tasks with CP, part II

As Jerome Valcke predicted, 2011 has only started in Brazil about a couple of weeks ago when carnival was over. For those who do not believe, it is just a matter of checking that in the past weeks people started talking again about the arrangements for the forthcoming international games. Thus, it is not possible to apply any OR technique to speed-up things and reduce costs if we do not consider local conditions more closely.

Minding that, this post will complement that OPL example presented previously with a couple of refinements. An explanation about what is a global constraint will be given at the end.

Dealing with the political calendar

Since part of our activities involve politicians and they don’t work as frequently as other people do, that must be included in our model. In fact, that is not only the case of politicians since other people take vacations too (albeit not that long). For instance, one interval might represent a work whose size is 5 days but whose length might be of 7 days if there is a weekend between its start and end, in which its intensity is null.

In OPL, an interval can be declared accompanied by a step-wise function that represent the intensity along time in percentage units. To give a simple example, suppose that our activities are measured in months. For 2010, in which carnival was in February but there as a World Cup between half of June and of July, debates and elections from August to October, and Christmas in the last half-month, we have the following:

stepFunction politicalEffort2010 =
      stepwise {1->0; 3->100; 6->50; 8->0; 11->100; 12->50; 100};
dvar interval politicalActivity[1..n]
      intensity politicalEffort2010;

In the example above, the step-wise functions starts with 0 in month 1, changes to 100 in month 3, 50 in month 6, 0 in month 8, 100 in month 11, 50 in month 12, and it is supposed to be 100 afterwards.

Dealing with bureaucracy restrictions

Yet another impairment that happens with projects of public interest is that they must be approved by commissions. Sometimes, such commissions are overloaded with lots of different projects. Let´s try to model their operational limit. Suppose that we have a set of activities environmentalComActs which must be executed by an environmental committee, for example. Also, consider that there is a variable environmentalComMaxLim stating how many activities can be done concurrently:

{int} environmentalComActs = {1, 4, 8, 9, 12, 20, 45};
int environmentalComMaxLim = 3;

We can create a cumulative function to represent concurrency in the committee, using a unitary pulse in time for each activity:

cumulFunction environmentalComUse =
      sum (i in environmentalComActs) pulse(politicalActivity[i], 1);

And we can state that such function is limited in the “subject to” block:

subject to {
      environmentalComUse <= environmentalComMaxUse;

Global constraints… what’s that?

I’ve pointed out before that the strength of Constraint Programming (CP) for solving problems is due to the specialization of its mechanisms. Such specialization is based on the structure of the problem, which is pictured by its constraints. In the case of a scheduling problem, we are dealing with a bunch of activities upon which constraints are imposed. For the sake of a good solving performance, it is important to capture such constraints at the highest semantic level that is possible. For instance, if we have to impose that the activities of a group should not concur in time, it would be better to state that upon the entire group of activities then defining such constraint among each pair of activities in the group. Thus, instead of considering local relations among variables, it would be preferable to use the so called global constraints, which strive to represent much more meaningful information about problem structure. By doing this, it is possible to prevent a lot of useless search effort with less processing requirements.

The cumulative function used above is an example of global constraint for which much research has been published in the past 5 years.

** This post is my second contribution to the INFORMS Blog Challenge of March: OR and Sports. However, I think that it would be a best fit for the January topic: OR and Politics. **

This entry was posted in Uncategorized and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s