Model

Once the house building with budget and resource pools problem has been described using natural language, you then use Concert Technology classes to model the constraint programming problem.

After you have written a description of your problem, you can use IBM® ILOG® Concert Technology classes to model it.

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/sched_cumul_partial.cpp in your development environment. This file is a program that is only partially completed. You will enter the missing code in each step in this lesson. At the end, you will have completed the program code, and you can compile and run the program.

In this lesson, you include the header file <ilcp/cp.h>. To catch exceptions that may be thrown, you use a try/catch block. The code for creating the environment and model and for printing out the solution found by the CP Optimizer engine is provided.

In addition, the data related to the tasks, such as the tasks (Tasks), the number of tasks (NbTasks), the names of the tasks (TaskNames) and sizes of the tasks (TaskDurations), are provided. The number of workers (NbWorkers) is also provided.

After you create an environment and a model, you need to define the decision variables and add the constraints and objective to the model. Since the requirements for each of the five houses are similar, you use a function, MakeHouse, to create the decision variables, constraints and costs associated with each house. Information about individual houses that must be shared with the main function includes the expressions needed to create the objective function and information about worker usage and the cash balance. In order to display the results of the optimization, it is also useful to maintain an array of all the interval variables.

To access this information, you create objects to be updated in the MakeHouse function. An array of task interval variables, allTasks, stores all the interval variables that are created. The cost expression involves the date at which moving is completed for each house, and the integer expression array ends is used to store this information. In addition, the expressions used to represent worker usage and the cash balance are included in the global information that is updated in each call to the MakeHouse function.

Since the workers are equivalent in this problem, it is better to represent them as one pool of workers instead of as individual workers with no overlap constraints as was done in the earlier examples. This representation removes symmetry. The expression representing usage of the pool of workers can be modified by the interval variables that require a worker.

To model both the limited number of workers and the limited budget, you need to represent the sum of individual contributions of interval variables. In the case of the cash budget, some tasks consume some of the budget at the start. In the case of the workers, a task requires a worker only for the duration of the task. Concert Technology provides the class IloCumulFunctionExpr to represent the sum of individual contributions of interval variables.

Note:

Cumulative function expression

A cumulative function, represented in IBM ILOG Concert Technology by IloCumulFunctionExpr, can be used to model a resource usage function over time. This function can be computed as a sum of interval variable demands on a resource over time.

An interval usually increases the cumulated resource usage function at its start time and decreases it when it releases the resource at its end time (pulse function).

For resources that can be produced and consumed by activities (for instance the contents of an inventory or a tank), the resource level can also be described as a function of time. A production activity will increase the resource level at the start or end time of the activity whereas a consuming activity will decrease it. The cumulated contribution of activities on the resource can be represented by a function of time, and constraints can be posted on this function (for instance, a maximal or a safety level).

A cumulative function expression can be computed as a sum of the following types of elementary demands:

IloStep, which increases or decreases the level of the function by a given amount at a given time;
IloPulse, which increases or decreases the level of the function by a given amount for the length of a given interval variable or fixed interval;
IloStepAtStart, which increases or decreases the level of the function by a given amount at the start of a given interval variable;
IloStepAtEnd, which increases or decreases the level of the function by a given amount at the end of a given interval variable.

A cumulative function expression can be constrained to model limited resource capacity by constraining that the function be <= the capacity.

To illustrate, consider a cumulative resource usage function that measures how much of a resource is being used. There are two intervals, A and B, bound in time, and each interval increases the cumulative function expression by one unit over its duration. For each interval, this modification to the cumulative resource usage function can be made by incrementing the cumulative function with the elementary function IloPulse, created with the interval and the given amount. Given this, the function would take the profile as in the figure “Pulse on Cumulative Function Expression.”

Graph of a pulse function — Figure 1. Pulse on Cumulative Function Expression

As another example, consider a function measuring a consumable resource, similar to the budget resource. Consider that the level of the resource is zero, until time 2 when the value is increased to 4; modeled by modifying the cumulative function with the elementary cumul function IloStep at time 2. There are two intervals, A and B, fixed in time. Interval A decreases the level of the resource by 3 at the start of the interval, modeled by applying IloStepAtStart, created with Interval A and the value (3), to the cumulative function. Interval B increases the level of the resource by 2 at the end of the interval, modeled by applying IloStepAtEnd, created with Interval B and the value (2), to the cumulative function for the interval. Given this, the function would take the profile as in the figure “Step on Cumulative Function Expression.”

Graph of a consumable resource over time — Figure 2. Step on Cumulative Function Expression

For the house building problem, you create two cumulative function expression objects, one to represent the usage of the workers and the other to represent the cash balance. The constructor of the class IloCumulFunctionExpr takes one argument, the environment.

Step 3: Declare the objects needed for MakeHouse

Add the following code after the comment //Declare the objects needed for MakeHouse


    IloCumulFunctionExpr workersUsage(env);
    IloCumulFunctionExpr cash(env);
    IloIntExprArray ends(env);
    IloIntervalVarArray allTasks(env);

To set the increases to the cash balance, you use the function IloStep, which can be used to increment or decrement the cumulative function expression by a fixed amount on a given date. The first argument passed to this function is the environment. The second argument is the date at which the function should be modified. The third argument is the amount by which the function should be changed; this must be a non-negative value.


  IloCumulFunctionExpr IloStep(const IloEnv env, IloInt t, IloInt v);

For setting the increases to the cash balance, the cumulative function expression for the cash balance should be incremented by the appropriate amount, 30,000 dollars, every 60 days, starting at day 0.

Step 4: Add the cash payment expression

Add the following code after the comment //Add the cash payment expression


    for (IloInt p=0; p<5; ++p)
      cash += IloStep(env, 60*p, 30000);

You need to pass the model, the house identifier, the earliest start date of the house, the cumulative function expressions for the worker usage and cash balance, the array of expressions representing the completion dates of the houses and the array of all the tasks as arguments to the MakeHouse function.

Step 5: Create the MakeHouse function

Add the following code after the comment //Create the MakeHouse function


void MakeHouse(IloModel model,
                IloInt id,
                IloInt rd,
                IloCumulFunctionExpr& workersUsage,
                IloCumulFunctionExpr& cash,
                IloIntExprArray ends,
                IloIntervalVarArray allTasks) {

Each house has a list of NbTasks that must be scheduled. Task i, where i is in 0..NbTasks-1, has a size of TaskDurations[i] and the name TaskNames[i]. Using these, you build an array tasks of interval variables. As you create each interval variable, you also add it to the array allTasks that will be used to display the solution once the schedule has been computed.

Each task also requires one worker from the start to the end of the task interval. To represent the fact that a worker is required for the task, you modify the cumulative function expression, workerUsage. Since it is not known when a task will begin or end, you use the function IloPulse. The first argument passed to this function is the interval during which the function should be modified. The second argument is the amount by which the function should be changed; this must be a non-negative value.


  IloCumulFunctionExpr IloPulse(const IloIntervalVar a, IloInt v);

Moreover, each task requires a payment equal to 200 dollars a day for the length of the task, payable at the start of the task. For each task, you use the function IloStepAtStart to adjust the cash balance cumulative function expression.

Step 6: Create the interval variables

Add the following code after the comment //Create the interval variables


  char name[128];
  IloIntervalVarArray tasks(env, NbTasks);
  for (IloInt i=0; i<NbTasks; ++i) {
    sprintf(name, "H%ld-%s", id, TaskNames[i]);
    IloIntervalVar task(env, TaskDurations[i], name);
    tasks[i] = task;
    allTasks.add(task);
    workersUsage += IloPulse(task, 1);
    cash -= IloStepAtStart(task, 200 * TaskDurations[i]);
  }

The tasks have precedence constraints that are added to the model. Moreover, each house has an earliest starting date.

Step 7: Add the temporal constraints

Add the following code after the comment //Add the temporal constraints


  tasks[masonry].setStartMin(rd);
  model.add(IloEndBeforeStart(env, tasks[masonry], tasks[carpentry]));
  model.add(IloEndBeforeStart(env, tasks[masonry], tasks[plumbing]));
  model.add(IloEndBeforeStart(env, tasks[masonry], tasks[ceiling]));
  model.add(IloEndBeforeStart(env, tasks[carpentry], tasks[roofing]));
  model.add(IloEndBeforeStart(env, tasks[ceiling], tasks[painting]));
  model.add(IloEndBeforeStart(env, tasks[roofing], tasks[windows]));
  model.add(IloEndBeforeStart(env, tasks[roofing], tasks[facade]));
  model.add(IloEndBeforeStart(env, tasks[plumbing], tasks[facade]));
  model.add(IloEndBeforeStart(env, tasks[roofing], tasks[garden]));
  model.add(IloEndBeforeStart(env, tasks[plumbing], tasks[garden]));
  model.add(IloEndBeforeStart(env, tasks[windows], tasks[moving]));
  model.add(IloEndBeforeStart(env, tasks[facade], tasks[moving]));
  model.add(IloEndBeforeStart(env, tasks[garden], tasks[moving]));
  model.add(IloEndBeforeStart(env, tasks[painting], tasks[moving]));

To model the cost of building the houses, you will need to determine the maximum completion date among the individual house projects. To determine the expression representing the completion date of the house currently in consideration, you use the function IloEndOf on the last task in building a house (here, it is the moving task) and store this expression in the array ends.

Step 8: Add the objective expression

Add the following code after the comment //Add the objective expression


  ends.add(IloEndOf(tasks[moving]));

This completes the MakeHouse function. In the main function, you now call the MakeHouse function, once for each house. At each call, additional elements are appended to the arrays ends and allTasks, and the expressions for worker usage and the cash balance are modified.

Step 9: Create the houses

Add the following code after the comment //Create the houses


    MakeHouse(model, 0,  31, workersUsage, cash, ends, allTasks);
    MakeHouse(model, 1,   0, workersUsage, cash, ends, allTasks);
    MakeHouse(model, 2,  90, workersUsage, cash, ends, allTasks);
    MakeHouse(model, 3, 120, workersUsage, cash, ends, allTasks);
    MakeHouse(model, 4,  90, workersUsage, cash, ends, allTasks);

To add the constraint that the cash balance must remain positive, you constrain the cumulative function expression representing the cash to be non-negative. (Note that by default the function is constrained to be non-negative, but the cumulative expression function must be added to the model in order for the optimizer to take it into account during the search.)

Step 10: Add the cash balance constraint

Add the following code after the comment //Add the cash balance constraint


    model.add(0 <= cash);

To add the constraint that there can be only three workers working at a given time, you constrain the cumulative function expression representing worker usage to be no greater than the value NbWorkers.

Step 11: Add the worker usage constraint

Add the following code after the comment //Add the worker usage constraint


    model.add(workersUsage <= NbWorkers);

The objective of this problem is to minimize the overall completion date (the completion date of the house that is completed last). To do this, you minimize the maximal expression in the array ends.

Step 12: Add the objective

Add the following code after the comment //Add the objective


    model.add(IloMinimize(env, IloMax(ends)));