Model

Once the house building with workers 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_sequence_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.

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 a house. The information about individual houses that must be shared with the main function includes the cost expression and the set of tasks associated with each worker. This set of tasks is needed in order to create the constraints for each worker that involve tasks of different houses. 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 global 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 overall cost is represented by a numerical expression called cost. For the worker Joe, you create two arrays to be filled by the MakeHouse function: joeTasks, an array of interval variables, and joeLocations, an array of integers. These two corresponding arrays are indexed the same, so that for each index i, joeTasks[i] is performed at joeLocation[i]. A similar pair of arrays are created for the worker Jim. These four arrays are passed to the MakeHouse function which adds elements to these arrays as the interval variables and constraints are created

Step 3: Declare the objects needed for MakeHouse

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


    IloNumExpr cost(env);
    IloIntervalVarArray allTasks(env);
    IloIntervalVarArray joeTasks(env);
    IloIntervalVarArray jimTasks(env);
    IloIntArray joeLocations(env);
    IloIntArray jimLocations(env);

You pass the model, the cost expression, the array of all tasks, the arrays joeTasks, jimTasks, joeLocations and jimLocations, the identifier of the current house, the earliest date the house can be started, the preferred due date of the house and the cost per day of completing the house late as arguments to the MakeHouse function.

Step 4: Create the MakeHouse function

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


void MakeHouse(IloModel model,
      IloNumExpr cost,
      IloIntervalVarArray allTasks,
      IloIntervalVarArray joeTasks,
      IloIntervalVarArray jimTasks,
      IloIntArray joeLocations,
      IloIntArray jimLocations,
      IloInt loc,
      IloInt rd,
      IloInt dd,
      IloNum weight) {

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 determined.

Step 5: 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", loc, TaskNames[i]);
    tasks[i] = IloIntervalVar(env, TaskDurations[i], name);
    allTasks.add(tasks[i]);
  }

To model the cost associated with the length of time it takes to build a single house, you create an interval variable that starts at the start of the first task of the house and ends at the end of the last task. This interval variable must span the tasks.

Note:

Span constraint

With the specialized constraint IloSpan, you can create a constraint that specifies that one interval variable must exactly cover a set of interval variables.

In other words, the spanning interval a is present in the solution if and only if at least one of the spanned interval variables is present and, in this case, the spanning interval variable starts at the start of the interval variable scheduled earliest in the set and ends at the end of the interval variable scheduled latest in the set.

The first argument passed to the constructor of the class IloSpan is the environment. The second argument is the interval variable that will be constrained to cover the set of interval variables. The third argument is the array of interval variables that are to be covered. The final argument is an optional name used for debug and trace purposes. Here is a constructor:


  IloSpan (const IloEnv env, 
           const IloIntervalVar a, 
           const IloIntervalVarArray bs, 
           const char *name =0);

You create an interval variable called house and constrain the variable to cover the array of tasks, tasks.

Step 6: Add the house interval variable and span constraint

Add the following code after the comment //Add the house interval variable and span constraint


  sprintf(name, "H%ld", loc);
  IloIntervalVar house(env, name);
  model.add(IloSpan(env, house, tasks));

The tasks of the house building project have precedence constraints that are added to the model. Moreover, each house has an earliest starting date which can be modeled with a time bound modifier.

Note:

Interval variable modifier

Properties of interval variables can be modified.

Time bound modifiers are used to limit the possible values that may be assigned to the start, length, size, or end of an interval variable. These modifiers include setStartMin, setStartMax, setEndMin, setEndMax, setLengthMin, setLengthMax., setSizeMin and setSizeMax. For example, if a denotes an interval variable and val is a number, then:

a.setStartMin(val) constrains that a must not start before val or a is not present in the solution. It imposes the inequality startTime(a) >= val.

Other modifiers of interval variables include setPresent, setAbsent and setOptional which indicate whether or not an interval variable must be present.

Step 7: Add the precedence and time bound constraints

Add the following code after the comment //Add the precendence and time bound constraints


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

Each of the tasks requires a particular worker. As a worker can perform only one task at a time, it is necessary to know all of the tasks that a worker must perform and then constrain that these intervals not overlap. Also, as there are transition times between houses that must be taken into account, it is necessary to know where each task is to be performed. To create the no overlap and transition time constraints in the main function, you add the appropriate tasks to the arrays joeTasks and jimTasks. To indicate at which house the task is performed, whenever a task is added to a worker’s task array, a location is added to that worker’s location array. Thus the two corresponding arrays are indexed the same, so that for each index i, joeTasks[i] is performed at joeLocation[i].

Step 8: Add the tasks to workers

Add the following code after the comment //Add the tasks to workers


  joeTasks.add(tasks[masonry]);
  joeLocations.add(loc);
  joeTasks.add(tasks[carpentry]);
  joeLocations.add(loc);
  jimTasks.add(tasks[plumbing]);
  jimLocations.add(loc);
  jimTasks.add(tasks[ceiling]);
  jimLocations.add(loc);
  joeTasks.add(tasks[roofing]);
  joeLocations.add(loc);
  jimTasks.add(tasks[painting]);
  jimLocations.add(loc);
  jimTasks.add(tasks[windows]);
  jimLocations.add(loc);
  joeTasks.add(tasks[facade]);
  joeLocations.add(loc);
  joeTasks.add(tasks[garden]);
  joeLocations.add(loc);
  jimTasks.add(tasks[moving]);
  jimLocations.add(loc);

To model the cost of building the house, you create a function that uses the function IloEndOf to model the cost associated with a task being completed later than its preferred latest end date.

Step 9: Add the tardiness cost function

Add the following code after the comment //Add the tardiness cost function


IloNumExpr TardinessCost(IloIntervalVar task, IloInt dd, IloNum weight) {
  IloEnv env = task.getEnv();
  return weight * IloMax(0, IloEndOf(task)-dd);
}

This cost function returns an expression that models the tardiness cost for the end date of the house interval variable. The cost for building a house is the sum of the tardiness cost and the number of days it takes from start to finish building the house. To model the cost of the length of time it takes to build the house, you use the function IloLengthOf, which returns an expression representing the length of an interval variable.

Step 10: Add the cost expression

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


  cost += TardinessCost(house, dd, weight);
  cost += IloLengthOf(house);

This completes the MakeHouse function. In the main function, you now call the MakeHouse function, once for each house. At each call, the cost expression is incremented by the cost associated with that house and additional elements are appended to the arrays allTasks, joeTasks, jimTasks, joeLocations and jimLocations.

Step 11: Create the houses

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


    MakeHouse(model, cost, allTasks, joeTasks, jimTasks, joeLocations, 
      jimLocations, 0, 0,   120, 100.0);
    MakeHouse(model, cost, allTasks, joeTasks, jimTasks, joeLocations, 
      jimLocations, 1, 0,   212, 100.0);
    MakeHouse(model, cost, allTasks, joeTasks, jimTasks, joeLocations, 
      jimLocations, 2, 151, 304, 100.0);
    MakeHouse(model, cost, allTasks, joeTasks, jimTasks, joeLocations, 
      jimLocations, 3, 59,  181, 200.0);
    MakeHouse(model, cost, allTasks, joeTasks, jimTasks, joeLocations, 
      jimLocations, 4, 243, 425, 100.0);

You now model the transition times associated with the workers transferring between houses.

Note:

Transition time object

The class IloTransitionDistance in IBM ILOG Concert Technology lets you build a table of transition times to apply to a sequence of non-overlapping interval variables. An instance of this class is a table of non-negative numbers, indexed by an integer interval variable type associated with each interval variable.

Given an interval variable a1 that precedes (not necessarily directly) an interval variable a2 in a sequence of non-overlapping interval variables, the transition time between a1 and a2 is an amount of time that must elapse between the end of a1 and the beginning of a2.

The first argument passed to the constructor of the class IloTransitionDistance is the environment. The second argument is the number of transition types. The final argument is an optional name used for debug and trace purposes. Here is a constructor:


   IloTransitionDistance(const IloEnv env, 
                         IloInt size, 
                         const char* name = 0);

In this problem, there are five houses, thus the number of types of interval variables is also five. The transition time from one house to another is the absolute difference of the associated house identifiers.

Step 12: Create the transition times

Add the following code after the comment //Create the transition times


    IloTransitionDistance tt(env, 5);
    for (i=0; i<5; ++i) 
      for (j=0; j<5; ++j)
        tt.setValue(i, j, IloAbs(i-j));

To add the constraints that Jim and Joe can only perform one task at a time and must respect transition times, you create a sequence variable that represents the order in which the workers perform the tasks. Note that the sequence variable does not force the tasks to not overlap or the order of tasks; in a future step you create a constraint that enforces these relations on the sequence of interval variables.

Note:

Interval sequence decision variable

Using the class IloIntervalSequenceVar in Concert Technology, you can create a variable that represents a sequence of interval variables. The sequence can contain a subset of the variables or be empty. In a solution, the sequence will represent a total order over all the intervals in the set that are present in the solution.

The assigned order of interval variables in the sequence does not necessarily determine their relative positions in time in the schedule.

The first argument passed to the constructor of the class IloIntervalSequenceVar is always the environment. The second argument is the array of interval variables to be sequenced. The third argument is the array of integer types of the interval variables in the second argument. The final argument is an optional name used for debug and trace purposes. Here is a constructor:


  IloIntervalSequenceVar(const IloEnv env, 
                         const IloIntervalVarArray a, 
                         const IloIntArray types, 
                         const char* name=0);

You create interval sequence variables for Jim and Joe, using the arrays of their tasks and task locations as the arguments.

Step 13: Create the sequence variables

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


    IloIntervalSequenceVar joe(env, joeTasks, joeLocations, "Joe");
    IloIntervalSequenceVar jim(env, jimTasks, jimLocations, "Jim");

Now that you have created the sequence variables, you must constrain each sequence such that the interval variables do not overlap in the solution, that the transition times are respected and that the sequence represents the relations of the interval variables in time. To do this, you use the specialized constraint IloNoOverlap.

Note:

No overlap constraint

Using the class IloNoOverlap in Concert Technology, you can constrain that an interval sequence variable defines a chain of non-overlapping intervals that are present in the solution. If a transition matrix is specified, it defines the minimal time that must elapse between two intervals in the chain.

Note that intervals which are not present in the solution are automatically removed from the sequence.

In this case, the first argument passed to the constructor of the class IloNoOverlap is the environment. The second argument is the sequence of interval variables. The third argument is the transition object. The final argument is an optional name used for debug and trace purposes. Here is a constructor:


  IloNoOverlap(const IloEnv env,
               const IloIntervalSequenceVar seq,
               const IloTransitionDistance ttime =0,
               const char* name=0);

You add one no overlap constraint for the sequence interval variable for each worker.

Step 14: Add the no overlap constraints

Add the following code after the comment //Add the no overlap constraints


    model.add(IloNoOverlap(env, joe, tt));
    model.add(IloNoOverlap(env, jim, tt));

The objective of this problem is to minimize the cost as represented by the cost expression.

Step 15: Add the objective

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


    model.add(IloMinimize(env, cost));