Solve

Step 20: Create an instance of IloCP

Add the following code after the comment //Create an instance of IloCP

    IloCP cp(model);

In this problem, using the built-in search leads to a long search time. To modify the search to make it more efficient, you use a search tuning parameter to change the inference level of the IloAllDiff constraint.

Each constraint is associated with a domain reduction algorithm. This algorithm performs domain reductions based on the associated constraint; the algorithm will remove values from the current domains of variables that do not belong to a solution. Constraint propagation is the mechanism used to communicate the effects of these domain reductions.

For some types of constraints, you can set an inference level that specifies the type of domain reduction algorithm. For specialized constraints such as IloAllDiff, the reduction algorithm varies depending on the inference level. This inference level can be changed by setting a parameter on IloCP.

To understand the difference between the inference levels, consider the IloAllDiff constraint. You can view this constraint in two ways. It can be seen as a set of inequality constraints or as one specialized constraint. For example, consider a graph coloring problem with three nodes: x, y and z. All the nodes must be colored a different color. Node x can be colored red or blue; node y can be colored red or blue; and node z can be colored red, blue, or yellow. If you set the inference level of IloAllDiff to the basic level using the tuning parameter, the domain reduction algorithm treats this specialized constraint as a set of inequality constraints. Looking at each set of binary constraints individually, the domain reduction algorithm is not able to reduce the domains.

If you set the inference level of IloAllDiff to the extended level, the domain reduction algorithm treats this constraint as a truly specialized constraint. The reduction algorithm is not able to reduce the domains of x and y. However, the reduction algorithm can “realize” that between them, variables x and y must use both of the values red and blue. This leaves only the value of yellow available for variable z.

Given that the extended level is the most thorough inference level, why would you use any other inference level? There is a trade-off in using the extended level. In general, the extended level takes longer. The basic inference level is less thorough, but faster. The medium level is a compromise between the two levels--faster than the extended level and more thorough than the basic. However, these are general rules and are not true for every situation. Depending on your application, different inference levels may be appropriate.

You use the member function IloCP::setParameter to set the inference levels for specialized constraints. This function takes two arguments: the first specifies the type of specialized constraint, the second specifies the inference level.

Step 21: Modify the search

Add the following code after the comment //Modify the search

    cp.setParameter(IloCP::AllDiffInferenceLevel, IloCP::Extended);

You now use the member function IloCP::solve, which searches for a single solution to the problem using constructive search and constraint propagation.

Step 22: Search for a solution

Add the following code after the comment //Search for a solution

    if (cp.solve()) {
      cp.out() << std::endl << "SOLUTION" << std::endl;
      for (p=0; p < nbTeams; ++p) {
        cp.out() << "team " << p << " : ";
        for (w=0; w < teamSize; ++w) {
          cp.out() << cp.getValue(groups[p][w]) << " ";
        }
        cp.out() << std::endl;
      }
    }
    else
      cp.out() << "**** NO SOLUTION ****" << std::endl;

Step 23: Compile and run the program

Compile and run the program. You should get the following results:

SOLUTION
team 0 : 0 1 2 3 55 56
team 1 : 4 5 15 18 50 51
team 2 : 6 7 16 19 45 46
team 3 : 8 9 12 14 49 59
team 4 : 10 11 13 17 44 54
team 5 : 20 21 24 25 40 41
team 6 : 22 23 32 33 57 58
team 7 : 26 27 38 39 52 53
team 8 : 28 29 34 35 42 43
team 9 : 30 31 36 37 47 48

The complete program can be viewed in the <Install_dir>/cpoptimizer/examples/src/cpp/teambuilding.cpp file.