Assigning Activities to Subproblems

IBM ILOG Scheduler User's Manual > Advanced Concepts > Scheduling with Discrete Resources: the Ship-loading Problem, Second Version > Decomposing the Problem > Assigning Activities to Subproblems

Assigning Activities to Subproblems

INDEX

PREVIOUS NEXT

The function DecomposeProblem first creates an extraction of the model, and then propagates on this extraction with an empty goal to solve. The purpose of this is to assign activities to the various subproblems. During this propagation, a precedence graph is used to determine which activities are the critical activities. The critical activities are then marked as belonging to the appropriate submodels.

The precedence enforcement is set to IloMediumHigh. This enforcement level aims at maintaining a precedence graph whose nodes are the schedule activities and whose directed edges represent precedence relations between activities. The startsAfterEnd constraints are automatically inserted as new edges when a precedence graph exists. The transitive closure of the graph is maintained by the constraint during the search.

The decomposition function scans the precedence graph and initializes the criticality status and the sections of the instances of class Activity. More precisely, the critical activities are the ones that are ranked on the precedence graph and the section of an activity corresponds to the number of ranked activities that precedes it.

As the precedence graph will not be used later in the program, once the problem has been decomposed, we set the enforcement level back to the default of IloBasic.

void
DecomposeProblem(IloModel            model,
                 IloActivityArray    activities, 
                 IloNumVar           makespan,
                 IloModelArray&      subModels)
{
  // 1. CREATE DECOMPOSITION ALGORITHM AND SET SUBPROBLEMS
  IloEnv env = model.getEnv();
  IloSchedulerEnv schedEnv(env);
 
  schedEnv.setPrecedenceEnforcement(IloMediumHigh);
 
  IloSolver solver(model);
  solver.solve(IloGoalTrue(env));
 
  IloInt numberOfActivities = activities.getSize();
  IloInt nbSubProblems = 0;
  IloInt i;
  IlcScheduler schedr(solver);
  for (i = 0; i < numberOfActivities; i++) {
    Activity* act = ((Activity*) activities[i].getObject());
    if (schedr.getActivity(activities[i]).isRanked())
      act->setCritical(IloTrue);
    IloInt subProblem = 0;
    for (IloInt j = 0; j < numberOfActivities; j++)
      if ((i != j) &&
          schedr.getActivity(activities[j]).isRanked() && 
          schedr.getActivity(activities[j]).isSucceededBy
                            (schedr.getActivity(activities[i])))
        subProblem++;
    act->setSubProblem(subProblem);
    if (subProblem >= nbSubProblems)
      nbSubProblems = subProblem + 1;
  }
 
  schedEnv.setPrecedenceEnforcement(IloBasic);
 
 /* ... */
 }

PREVIOUS NEXT