Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/sched_optional_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) and the data related to the workers, such as the workers (Workers), number of workers (NbWorkers) and the names of workers (WorkerNames), are provided. The matrix of skill levels (SkillsMatrix), one level for each worker/task pair and functions to return the skill level based on worker and task identifiers are 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 objective 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, for each worker, the array of interval variables associated with the worker, in order to create the constraint regarding non overlapping intervals. 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 that will be updated in the MakeHouse function. The objective expression is represented by the integer expression skill. An array of task interval variables, allTasks, stores all the interval variables that are created. To maintain the interval variables related to each worker, you use an array of arrays of interval variables called workerTasks, that will be filled by the calls to MakeHouse.

Step 3: Declare the objects needed for MakeHouse

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

    IloInt nbHouses = 5;
    IloInt deadline = 318;
    IloModel model(env);
    IloIntExpr skill(env);
    IloIntervalVarArray allTasks(env);
    IloIntervalVarArray2 workerTasks(env, NbWorkers);
    IloInt h, w;
    for (w=0; w<NbWorkers; ++w)
      workerTasks[w] = IloIntervalVarArray(env);

You need to pass the model, the objective expression, the array of all tasks, the matrix of worker interval variables, the house identifier and the overall deadline 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,
         IloIntExpr skill,
         IloIntervalVarArray allTasks,
         IloIntervalVarArray2 workerTasks,
         IloInt id,
         IloInt deadline) {

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.

Each task also requires one of the three workers from the start to the end of the interval. The worker assigned must have a non-negative level of skill on the task. To model this worker choice, you create an array of interval variables, one interval variable for each possible worker. You set these interval variables to be optional, so that each one may or may not be present in the solution. You also add each interval variable to the array allTasks that will be used to display the solution once the schedule has been determined. You also store these interval variables in a matrix called TaskMatrix, which is indexed on task and worker. This matrix will be used within the MakeHouse function in a later step.

If one of these interval variables is present in the solution, then its presence must be counted in the objective. Thus for each of these possible tasks, you increment the objective by the product of the skill level and the expression representing the presence of the time interval in the solution. The function IloPresenceOf takes the environment and an interval variable and returns a constraint that is true if the interval variable is present and false if it is absent.

To constrain the solution so that exactly one of this array of interval variables is to be present in the solution, you use the specialized constraint IloAlternative.

The first argument passed to the constructor of the class IloAlternative is the environment. The second argument is the interval variable. The third argument is the array of interval variables that are the “alternatives". The final argument is an optional name used for debug and trace purposes. Here is a constructor:

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

Step 5: Create the interval variables

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

  char name[128];
  IloIntervalVarArray  tasks(env, NbTasks);
  IloIntervalVarArray2 taskMatrix(env, NbTasks);

  for (IloInt i=0; i<NbTasks; ++i) {
    sprintf(name, "H%ld-%s ", id, TaskNames[i]);
    tasks[i] = IloIntervalVar(env, TaskDurations[i], name);
    taskMatrix[i] = IloIntervalVarArray(env, NbWorkers);

    /* ALLOCATING TASKS TO WORKERS. */
    IloIntervalVarArray alttasks(env);
    for (IloInt w=0; w<NbWorkers; ++w) {
      if (HasSkill(w, i)) {
        sprintf(name, "H%ld-%s-%s ", id, TaskNames[i], WorkerNames[w]);
        IloIntervalVar wtask(env, TaskDurations[i], name);
        wtask.setOptional();
        alttasks.add(wtask);
        taskMatrix[i][w]=wtask;
        workerTasks[w].add(wtask);
        allTasks.add(wtask);
        /* DEFINING MAXIMIZATION OBJECTIVE. */
        skill += SkillLevel(w, i)*IloPresenceOf(env, wtask);
      }
    }
    model.add(IloAlternative(env, tasks[i], alttasks));
  }

The tasks in the model have precedence constraints that are added to the model. Moreover, the “moving” task must be complete by the deadline.

Step 6: Add the temporal constraints

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

  tasks[moving].setEndMax(deadline);
  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]));

For each house and each given pair of tasks and worker that must have continuity, you constrain that if the interval variable for one of the two tasks for the worker is present, then the interval variable associated with that worker and the other task must also be present. To represent if a task is performed by a worker, you again use the constraint IloPresenceOf.

Step 7: Add the same worker constraints

Add the following code after the comment //Add same worker constraints

  model.add(IloPresenceOf(env, taskMatrix[masonry][joe]) ==
            IloPresenceOf(env, taskMatrix[carpentry][joe]));
  model.add(IloPresenceOf(env, taskMatrix[roofing][jack]) ==
            IloPresenceOf(env, taskMatrix[facade][jack]));
  model.add(IloPresenceOf(env, taskMatrix[carpentry][joe]) ==
            IloPresenceOf(env, taskMatrix[roofing][joe]));
  model.add(IloPresenceOf(env, taskMatrix[garden][jim]) ==
            IloPresenceOf(env, taskMatrix[moving][jim]));

This completes the MakeHouse function. In the main function, you now call the MakeHouse function, once for each house. At each call, the objective expression, skill, is updated and additional elements are appended to the arrays allTasks and the arrays in the matrix workerTasks. The deadline and house identifier are also passed to the MakeHouse function.

Step 8: Create the houses

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

    for (h=0; h<nbHouses; ++h)
      MakeHouse(model, skill, allTasks, workerTasks, h, deadline);

To add the constraints that a given worker can be assigned only one task at a time, you use the classes IloIntervalSequenceVar and IloNoOverlap as in Using no overlap constraints on interval variables: house building with workers.

Step 9: Add the no overlap constraints

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

    for (w=0; w<NbWorkers; ++w) {
      IloIntervalSequenceVar seq(env, workerTasks[w], WorkerNames[w]);
      model.add(IloNoOverlap(env, seq));
    }

The objective of this problem is to maximize the skill levels used for all the tasks, so you maximize the expression in the array skill.

Step 10: Add the objective

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

    model.add(IloMaximize(env, skill));