Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/sched_state_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 constants representing the number of houses (NbHouses), the number of workers (NbWorkers) and the two cleanliness states (Clean and Dirty) 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 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 information about worker usage. 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 cost expression involves the date at which moving is completed for each house; the integer expression array ends is used to store this information. An array of task interval variables, allTasks, stores all the interval variables that are created. In addition, the expression used to represent worker usage is 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 cumulative function expression representing usage of the pool of workers can be modified by the interval variables that require a worker.

Step 3: Declare the objects needed for MakeHouse

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

    IloInt i;
    IloModel model(env);
    IloIntExprArray ends(env);
    IloIntervalVarArray allTasks(env);
    IloCumulFunctionExpr workers(env);

The transition time from a dirty state to a clean state is the same value for all houses. Thus you can create one IloTransitionDistance object that can be shared by all houses. Here there are two transition types.

Step 4: Create the transition times

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

    IloTransitionDistance ttime(env, 2);
    ttime.setValue(Dirty, Clean, 1);

You need to pass the model, the house identifier, the array of expressions representing the completion dates of the houses, the array of all tasks, the cumulative function expression for the worker usage and the transition object 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,
         IloIntExprArray ends,
         IloIntervalVarArray allTasks,
         IloCumulFunctionExpr& workers,
         IloTransitionDistance ttime) {

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 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, using the function IloPulse.

You also add each interval variable to the array allTasks that will be used to display the solution once the schedule has been determined.

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]);
    tasks[i] = IloIntervalVar(env, TaskDurations[i], name);
    workers += IloPulse(tasks[i], 1);
    allTasks.add(tasks[i]);
  }

The tasks in the model have precedence constraints that are added to the model.

Step 7: Add the temporal constraints

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

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

Certain tasks require the house to be clean, and other tasks cause the house to be dirty. To model the possible states of the house, Concert Technology provides the class IloStateFunction to represent the disjoint states through time.

You create one state function object in each execution of MakeHouse, one for each house.

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

  IloStateFunction(const IloEnv env,  
                   const IloTransitionDistance tdist,
                   const char* name =0);

To model the state required or imposed by a task, you create a constraint that specifies the state of the house throughout the interval variable representing that task.

The first argument passed to the function IloAlwaysEqual is the environment. The second argument is the state function. The third argument is the interval variable on which you want to place the constraint. The fourth argument is the state value that the state function must take during the interval.

Here is a function signature:

  IloConstraint IloAlwaysEqual(const IloEnv env,
                               const IloStateFunction f,
                               const IloIntervalVar a,
                               IloInt v);

You create a state function and constrain the state function to take the appropriate values during the tasks that require the house to be in a specific state.

Step 8: Add the state constraints

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

  IloStateFunction houseState(env, ttime);
  model.add(IloAlwaysEqual(env, houseState, tasks[masonry],   Dirty));
  model.add(IloAlwaysEqual(env, houseState, tasks[carpentry], Dirty));
  model.add(IloAlwaysEqual(env, houseState, tasks[plumbing],  Clean));
  model.add(IloAlwaysEqual(env, houseState, tasks[ceiling],   Clean));
  model.add(IloAlwaysEqual(env, houseState, tasks[roofing],   Dirty));
  model.add(IloAlwaysEqual(env, houseState, tasks[painting],  Clean));
  model.add(IloAlwaysEqual(env, houseState, tasks[windows],   Dirty));

To model the cost of building the houses, you will need to determine the maximum completion date among the individual house projects. To access 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 9: Add the cost expression

Add the following code after the comment //Add the cost 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, the cumulative expression, workers, is updated and additional elements are appended to the arrays ends and allTasks. The model, house identifier and transition object are also passed to the MakeHouse function.

Step 10: Create the houses

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

    for (i=0; i<NbHouses; ++i) {
      MakeHouse(model, i, ends, allTasks, workers, ttime);
    }

To add the constraint that there can be only two 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 cumulative constraints

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

    model.add(workers <= 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)));