Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/teambuilding_partial.cpp in your development environment. This file is a program that is only partially completed. You 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 declaring an environment and a model, for calculating the coaching pairs and for printing out the solution found by the CP Optimizer engine is provided for you.

First, you represent the data of the program. The number of people, nbPersons, is set to 60 in this example, but can be easily modified. The number of teams, nbTeams, is 10 in this example. The size of a team, teamSize, is 6 in this example.

const IloInt nbPersons = 60;
const IloInt nbTeams = 10;
const IloInt teamSize = 6;
const IloInt nbServices = 6;

As the teams and the slots in each team are interchangeable, there is a lot of symmetry in this problem. To remove the symmetry, you will use a two-step process to solve this problem along with adding extra constraints. The first step is to determine a set of integer tuples, such that each tuple represents a possible set of new hires and existing employees to be assigned to a single team with six slots. The second step is to select a feasible set of ten of these tuples, one for each team, as the solution.

The first step requires solving a subproblem using CP Optimizer. Since this subproblem is a constraint programming problem itself, you follow the three step process to solve the subproblem.

Step 3: Describe the subproblem

In this subproblem, you will search for all possible combinations for a single team. There are 60 employees from six service units who can to be assigned to a team of six people. The team must have three existing employees and three new hires assigned to it. At most four people from the same service unit can be on the team. If one person from a coach/new hire pair is on the team, the other must be as well.

The sixty people are labeled with unique identifiers in the range 0 to 59. The existing employees are those with odd numbered identifiers, and the new hires are those with even numbered identifiers. The service unit memberships are the same as outlined in the description.

Employees from Services A and B cannot be on a team together, and employees from Services E and F cannot be on a team together.

Discussion

What is the known information in this subproblem?

• There are thirty existing employees and thirty new hires. Each employee belongs to one of six service units, and there are twenty coach/new hire pairs.

• There is one team with slots for six people.

What are the decision variables or unknowns in this problem?

• The unknown is all of the possible combinations of employees that can be assigned to one team. In other words, there are six decision variables, one for each slot. The domain of each of these variables is the set of employees, or [0..59].

What are the constraints on these variables?

• The team must have three existing employees and three new hires.

• The team cannot have just one person from a coach/new hire pair.

• The team cannot have more than four people from a given service unit.

• The team cannot have people from both Services A and B nor from both Services E and F.

This subproblem is modeled and solved in the function MakeTeamTuples, which returns an instance of IloIntTupleSet. The tupleset is the set of all feasible solutions to the subproblem. In this function, the code for creating the environment and model for the subproblem and for filling the data arrays newEmployee and service, both indexed on the person identifiers, is provided for you. Each element of the array service states to which service unit the associated person belongs, where the value 0 indicates the person is an employee of Service A, the value 1 indicates the person is in Service B, etc. The array newEmployee is a Boolean array; an element of newEmployee has the value 1 if and only if that person is a new hire.

Each tuple in the set to be returned has teamSize, or 6, elements. You create the IloIntTupleSet using the global environment that is the input argument to the function MakeTeamTuples.

Step 4: Create the set of tuples

Add the following code after the comment //Add the tupleset

  IloIntTupleSet ts(globalEnv, teamSize);

Each solution to the subproblem is an integer tuple of size teamSize. To represent the subproblem unknowns, you declare an array of decision variables, teamMembers, of length teamSize. The possible values for these variables are the person identifiers, or [0..nbPersons-1].

Step 5: Create the team members variable array

Add the following code after the comment //Add the team members variable array

  IloIntVarArray teamMembers(env, teamSize, 0, nbPersons-1);

Next, you begin to add the subproblem constraints. To model the constraint that there must be an equal number of new and existing employees on a team, you use an expression nbNewEmployees to count the number of new employees assigned to the array teamMembers. You use element expressions to determine if the person assigned to each element of teamMembers is a new employee and use the self-assigned addition operator on the expression to find the total number of new employees assigned to teamMembers. You constrain this expression to be equal to half the number of people on the team.

Step 6: Add the constraint on number of new employees

Add the following code after the comment //Add the constraint on the number of new employees

  IloIntExpr nbNewEmployees(env); 
  for (i = 0; i < teamSize; i++)
    nbNewEmployees += newEmployee[teamMembers[i]]; 
  model.add(nbNewEmployees == teamSize / 2);

To model the constraint that pairs must be together, you constrain that each member of the pair be assigned to teamMembers an equal number of times (in a later step you will add a constraint that ensures each person is assigned to teamMembers at most once in any given solution). You count how many times that person has been assigned to elements of teamMembers by using the IBM ILOG Concert Technology function IloCount. To make sure that either both or neither person in a pair is assigned to variables in teamMembers, you constrain that the number of times each person in the pair is assigned to the array teamMembers is equal. Here you use the array coaching which is initialized in the main program such that the i-th element has the value of -1 if the i-th person does not have a coach or the identifier of the coach if the i-th person has a coach.

Step 7: Add the constraint on coaching pairs

Add the following code after the comment //Add the constraint on coaching pairs

  for (i = 0; i < 60; i += 2) {
    if (coaching[i] >= 0)
      model.add(IloCount(teamMembers, i) == IloCount(teamMembers, coaching[i])); 
  }

To add the constraints on incompatible service units and the maximum number of people from a service unit that may be on the same team, you need to be able to represent the service unit of each employee. To do this, you create an array of auxiliary constrained integer variables serviceVar, which is indexed similarly to teamMembers. (For example, the third element of serviceVar represents to which service unit the person assigned to the third element of teamMembers belongs. These variables are linked using an element expression and the service data array.

Step 8: Add the service variables array

Add the following code after the comment //Add the service unit variables

  IloIntVarArray serviceVar(env, teamSize, 0, nbServices - 1); 
  for (i = 0; i < teamSize; i++)
    model.add(serviceVar[i] == service[teamMembers[i]]); 

You add the constraints that at most four people from a single service unit can be assigned to the same team using the IBM ILOG Concert Technology function IloCount and the array serviceVar.

Step 9: Add the constraint on cardinality of service unit on team

Add the following code after the comment //Add the constraint on cardinality of service unit on team

  for (i = 0; i < nbServices; i++)
    model.add(IloCount(serviceVar, i) <= 4); 

Employees of Services A and B may not be on the same team; likewise, employees of Services E and F may not be on the same team. To model this, you again use the IBM ILOG Concert Technology function IloCount, but instead of constraining the expression returned, you use it to form the subconstraints of logical constraints. These logical constraints state that the count of employees from either Service A or Service B who are assigned to the team must be zero, and likewise for Services E and F.

Step 10: Add the constraint on disjoint service units

Add the following code after the comment //Add the constraint on disjoint service units

  model.add(IloCount(serviceVar, 0) == 0 || IloCount(serviceVar, 1) == 0); 
  model.add(IloCount(serviceVar, 4) == 0 || IloCount(serviceVar, 5) == 0); 

As the elements, or slots, of the array teamMembers are not ordered, the search will likely encounter symmetry. In order to reduce symmetry, you introduce order among the variables in the array as discussed in Using specialized constraints and tuples: scheduling teams. By introducing this order, you also ensure that no employee will be assigned to teamMembers more than once in any solution.

Step 11: Add the symmetry reducing constraint

Add the following code after the comment //Add the symmetry reducing constraint

  for (i = 0; i < teamSize-1; i++)
    model.add(teamMembers[i] < teamMembers[i+1]);

You now search for all possible solutions to the submodel. Each solution is a valid assignment for one team. As each solution is found, the assigned values are stored in an integer tuple which is then added to the set of tuples that will be returned to the main program. You create an integer tuple, or array, to temporarily store each newly found valid team. You use an instance of IloCP to find the solutions to the problem in the model. Since you will need to find all solutions for this subproblem instead of one solution, you will not use IloCP::solve, which terminates after a single solution has been found, in the case that there is a solution.

When solving a problem that does not have an objective, the member functions IloCP::startNewSearch and IloCP::next can be used in a while loop to find all feasible solutions to a problem. The function IloCP::startNewSearch initializes the optimizer, the function IloCP::next searches for a new solution in the search space. The function IloCP::end cleans up the internal memory and data structures used by the optimizer.

Step 12: Begin the search for a solution to the subproblem

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

  IloIntArray tuple(globalEnv, teamSize);
  IloCP cp(model);
  cp.setParameter(IloCP::LogVerbosity, IloCP::Quiet);
  cp.setParameter(IloCP::SearchType, IloCP::DepthFirst);
  cp.startNewSearch();
  while (cp.next()) {

As each solution is found, you copy the values assigned to the decision variables in the array teamMembers and store these values in a tuple. You add this new tuple to the tupleset and search for another solution. This loop is repeated until all solutions have been found.

Step 13: Search for all solutions to the subproblem

Add the following code after the comment //Search for all solutions

    for (IloInt i = 0; i < teamSize; i++)
      tuple[i] = cp.getValue(teamMembers[i]);
    ts.add(tuple);
  }

The search terminates after all possible team tuples have been found. In order to clean up and reclaim the memory, you end the search and end the environment for the subproblem. You return the created tupleset of team configurations to the main program. Since the tupleset was created on the environment of the main program and not for the subproblem, it will not be destroyed in the clean up of the subproblem.

Step 14: Clean up the subproblem

Add the following code after the comment //End the env for the subproblem

  cp.end();
  env.end();
  return ts;

Now that you have completed searching for all possible assignments for one team, you need to select ten of these tuples such that the employees are all assigned to teams and such that the additional preference constraints are satisfied.

You represent the people assigned to the teams with a matrix of constrained integer variables group, which is indexed on the team and slot. The array of constrained variables group[i] is the group of people assigned to the i-th team. Each element of group can be assigned a value in the interval [0..nbPersons-1].

For each group[i], or set of people on a team, the only possible values are those in the tupleset returned by the function MakeTeamTuple. To model this, you use the IBM ILOG Concert Technology function IloAllowedAssignments.

Step 15: Add the group variables and allowed assignments

Add the following code after the comment //Add the group variables and allowed assignments

    IloArray<IloIntVarArray> groups(env, nbTeams); 
    for (i = 0; i < nbTeams; i++) {
      groups[i] = IloIntVarArray(env, teamSize, 0, nbPersons-1);
      model.add(IloAllowedAssignments(env,groups[i], tupleSet));
    }

Since each person can be assigned to only one team, you must ensure that in any solution every variable in the array group takes a unique value. First you flatten the matrix groups into an array of decision variables. These are not new decision variables, but merely an alternate representation of the variables created previously. Then by using this new array as the argument to the constraint IloAllDiff, you can assure that no person will be assigned to two team slots and also that every person will be assigned to a slot.

Step 16: Add the all diff constraint

Add the following code after the comment //Add the all diff constraint

    IloIntVarArray allVars(env, nbPersons);
    IloInt s = 0, w, p;
    for (w = 0; w < nbTeams; ++w) {
      for (p = 0; p < teamSize; ++p) {
        allVars[s] = groups[w][p];
        ++s;
      }
    }
    model.add(IloAllDiff(env, allVars));

To add the four preference constraints, you need to represent the team to which each employee is assigned. You declare an array of decision variables team of length nbPersons. The domain of each of the variables in team is [0..nbTeams-1] and the value assigned to team[i] represents the team to which person i is assigned.

Step 17: Add the team variables

Add the following code after the comment //Add the team variables

    IloIntVarArray team(env, nbPersons, 0, nbTeams);
    for (w = 0; w < nbTeams; ++w) {
      for (p = 0; p < teamSize; ++p) {
        model.add(team[groups[w][p]]==w);
      }
    }

Using these variables, you add logical constraints to model the four preference constraints.

Step 18: Add the preference constraints

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

    model.add(team[5]== team[41] || team[5]==team[51]);
    model.add(team[15]== team[40] || team[15]==team[51]);
    model.add(team[25]== team[40] || team[25]==team[50]);
    model.add(team[20]== team[24] || team[22]==team[50]);

Since the teams are all equivalent, each unique solution could be represented in 10! “different” solutions to this model. To reduce the symmetry in the search, you add constraints to introduce order to the groups. The person assigned to the initial slot in each element array of group should have a larger identifier than the person assigned to the initial slot of the previous element array of group.

Step 19: Add the symmetry constraint

Add the following code after the comment //Add the symmetry constraint

    for (i=0; i<nbTeams-1; i++)
      model.add(groups[i][0] < groups[i+1][0]);