Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/sports_partial.cpp in your development environment.

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, calculating the unique game identifiers 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 teams, n, is set to a default of 10 in this example, but can be changed with an input argument. (For this problem, the number of teams must always be even. If the number of teams is not even, it is increased by 1.) The code for processing the input argument is provided for you:

    IloInt n = 10;
    if (argc > 1)
      n = atoi(argv[1]);
    if ((n % 2) == 1)
      n++;
    env.out() << "Finding schedule for " << n << " teams" << std::endl;

The number of weeks, nbWeeks, is 2*(n-1), or 18 in this example. The number of game slots per week, nbGamesPerWeek, is nbTeams/2, or 5 in this example. The number of game slots, nbGames, is equal to the number of weeks times the number of game slots per week, or 90 in this example. The number of games to be scheduled is equal to the number of game slots available.

Step 3: Calculate the data

Add the following code after the comment //Calculate the data

    IloInt nbWeeks = 2 * (n - 1);
    IloInt nbGamesPerWeek = n / 2;
    IloInt nbGames = n * (n - 1);

Each week has five slots; each slot must have a game assigned to it. The unknowns in this problem are which game is assigned to which slot. To represent these unknowns, you declare a matrix of decision variables, games, which is indexed on week and slot. To create the matrix of variables, you create an array in which each element is an array of constrained integer variables. The domain of values for each variable in games is the set of unique game identifiers; in this example the domain of each variable is [0..89]. The matrix of variables games will represent the solution to the problem after a solution has been found by the CP Optimizer engine.

To help you model the constraints that involve the home and away teams, it will be useful to be able to easily determine which team is the home team and which team is the away team for each slot. You declare auxiliary variables that are not directly a part of the solution, but make it easier to model the breaks and other constraints. You declare matrices of decision variables which represent the teams that will play at home and away in each slot, called home and away, respectively. These matrices are indexed on week and slot in the same manner as the matrix games. The domain of the variables in each of these matrices are the teams, represented by integers in the range [0..9].

Step 4: Declare the game, home team and away team variables

Add the following code after the comment //Declare the game, home team and away team variables

    IloIntVarArray2 games(env, nbWeeks);
    IloIntVarArray2 home(env, nbWeeks);
    IloIntVarArray2 away(env, nbWeeks);
    for (IloInt i = 0; i < nbWeeks; i++) {
      home[i]  = IloIntVarArray(env, nbGamesPerWeek, 0, n - 1);
      away[i]  = IloIntVarArray(env, nbGamesPerWeek, 0, n - 1);
      games[i] = IloIntVarArray(env, nbGamesPerWeek, 0, nbGames - 1);
    }

For each slot, you need to link the variables in the arrays game, home and away. In other words, you constrain that only certain configurations of home team, away team and game identifiers are allowed. These allowed configurations can be modeled as a set of integer tuples.

The constructor of IloIntTupleSet takes the environment as its first argument, and the arity as its second argument. Here is a constructor for IloIntTupleSet:

  IloIntTupleSet(IloEnv env, const int arity);

You use the member function IloIntTupleSet::add to add tuples to the set.

In this example, the game identifier indicates a particular pairing of home team and away team. Using the Game function, you see that the game in which Team 1 plays at home against Team 2 is Game 10. This combination is a tuple. You would write it as (1, 2, 10). The number of values in a tuple is known as the arity of the tuple. The tuple (1, 2, 10) has an arity of 3. You calculate all allowed combinations of home team, away team and game identifier using the Game function.

Step 5: Calculate the allowed tuples

Add the following code after the comment //Calculate the allowed tuples

    IloIntTupleSet gha(env, 3);
    IloIntArray tuple(env, 3);
    for (IloInt i = 0; i < n; i++) {
      tuple[0] = i;
      for (IloInt j = 0; j < n; j++) {
        if (i != j) {
          tuple[1] = j;
          tuple[2] = Game(i, j, n);
          gha.add(tuple);
        }
      }
    }

The complete set of possible combinations of home team, away team and game identifier are enumerated in the set of tuples, gha. To constrain the values assigned to a given slot of the matrices of home, away and games variables to be allowed combinations, you use the IBM ILOG Concert Technology constraint IloAllowedAssignments.

The function IloAllowedAssignments returns an instance of an IloConstraint. The first argument passed to this function is the environment. The second argument is the array of decision variables. The third argument is the tupleset which enumerates the allowed combinations of values for the array of variables. The arity of the tuples must be the same as the length of the array of the decision variables. Here is the function signature you will use:

  IloConstraint IloAllowedAssignments(const IloEnv env,
                                      const IloIntVarArray vars,
                                      const IloIntTupleSet set);

For each slot, you build a small temporary array of decision variables from variables you have already created. This new array has the home, away and games variables associated with the given slot. Note that you are not creating new decision variables but creating an alternate manner of referencing the previously created variables. Adding the compatibility constraint that the allowed assignments for these variables must be in the set of tuples, gha, ensures that these three matrices of variables are properly linked.

Step 6: Add the constraint on allowed combinations

Add the following code after the comment //Add the constraint on allowed combinations

    for (IloInt i = 0; i < nbWeeks; i++) {
      for (IloInt j = 0; j < nbGamesPerWeek; j++) {
        IloIntVarArray vars(env);
        vars.add(home[i][j]);
        vars.add(away[i][j]);
        vars.add(games[i][j]);
        model.add(IloAllowedAssignments(env, vars, gha));
      }
    }

Now that the auxiliary variables are properly linked to the games variables, you begin to model the constraints as outlined in the description of the problem. The first set of constraints state that each team can play in exactly one slot a week. For each week, no team can appear twice in the set of variables representing the teams playing at home and away for that week. In other words, the home and away variables associated with a given week must all be assigned different values in any solution. For each week, you create an array with all of the home and away variables for that week. To state that the value assigned to each decision variable in an array must be different from that of every other variable in that array, you use the IBM ILOG Concert Technology predefined constraint IloAllDiff.

The class IloAllDiff is a subclass of the class IloConstraint. The constructor of IloAllDiff takes the environment as its first argument. The second argument is the array of variables. The third argument is an optional name used for debug and trace purposes. Here is the function signature you will use:

  IloAllDiff(const IloEnv env, 
             const IloIntVarArray vars = 0, 
             const char* name = 0);
 

To simplify creating the single array containing the home and away variables for a given week, you use the add method of IloIntVarArray whose single argument is an IloIntVarArray. This method appends the argument array to the invoking array.

Step 7: Add the alldiff constraint

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

    for (IloInt i = 0; i < nbWeeks; i++) {
      IloIntVarArray teamsThisWeek(env);
      teamsThisWeek.add(home[i]);
      teamsThisWeek.add(away[i]);
      model.add(IloAllDiff(env, teamsThisWeek));
    }

Next, you add the constraints that the two games between a pair of teams must be in different halves of the season and also must be at least six weeks apart (if there are fewer than 6 teams, this minimum distance is reduced). To simplify modeling this constraint, you create auxiliary variables to represent the week of the season in which each game will be played.

You create the array weekOfGame which is indexed on game identifiers. Each element of this array is a decision variable with a domain of the possible weeks, [0..17]. The value of each variable in this array represents the week in which that game will be played.

To ensure that the weekOfGame variables are assigned the appropriate values, you need to be able to determine the week of each game. Assuming that each game is played exactly once, the week that game g is played is w, where there is an i such that game[w][i] is assigned the value g. To model this relationship, you use two steps. First, you determine which slot a game has been assigned to, then you determine the week of that slot.

To determine to which slot a game has been assigned, you create two arrays of decision variables, each of length nbGames. One is a “flattened” version of the matrix games, called allGames. The variables in allGames are not new variables, but provide an alternate view on the original variables in games. The other array, allSlots, is indexed by the games. The domain of each variable in allSlots is the set of values of the indices of allGames, [0..89]. Since allSlots[i] == j if and only if allGames[j] == i, the arrays have an inverse relationship. This relationship can be modeled using the IBM ILOG Concert Technology constraint IloInverse.

The class IloInverse is a subclass of IloConstraint. The constructor of IloInverse takes the environment as its first argument. The second argument is one array of decision variables. The third argument is the other array of variables. Here is the function signature you will use:

  IloInverse(const IloEnv env, 
             const IloIntVarArray f, 
             const IloIntVarArray invf);

As the arrays are of the same length, this constraint also has the virtue of ensuring that in any solution, the values assigned to all the variables within each array will be unique.

Step 8: Add the inverse constraint

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

    IloIntVarArray weekOfGame(env, nbGames, 0, nbWeeks - 1);
    IloIntVarArray allGames(env);
    IloIntVarArray allSlots(env, nbGames, 0, nbGames - 1);
    for (IloInt i = 0; i < nbWeeks; i++)
      allGames.add(games[i]);
    model.add(IloInverse(env, allGames, allSlots));

After you have established the connection between the arrays allSlots and allGames, you write a constraint to represent to which week a game will be assigned. Using the array allSlots, you can represent to which slot a game will be assigned. To determine to which week a slot belongs, you can use integer division. For instance, slot i is in the week i div nGamesPerWeek where div represents the integer division operator. IBM ILOG Concert Technology provides a function IloDiv for use in integer expressions.

The function IloDiv takes two arguments, an integer expression (or variable) and an integer value, and returns an instance of IloIntExprArg. The class IloIntExprArg is used internally by IBM ILOG Concert Technology to build expressions. You should not use IloIntExprArg directly. Here is the version of IloDiv that you will use:

  IloIntExprArg IloDiv(const IloIntExprArg x, IloInt y);

Step 9: Add the week of game

Add the following code after the comment //Add the week of game constraint

    for (IloInt i = 0; i < nbGames; i++)
      model.add(weekOfGame[i] == IloDiv(allSlots[i], nbGamesPerWeek));

Now that you have a representation of the week in which each game will be played, you can complete the second step in writing constraints to model the limitations on season half and minimum length of time between the games. You determine the identifiers of the two games played between each pair of teams and then constrain that if one game is scheduled in the last half of the season, then the other game must be scheduled in the first half of the season and that if one game is not scheduled in the last half of the season, then the other game must not be scheduled in the first half of the season. This type of conditional constraint is called a logical constraint.

Step 10: Create the different halves constraint

Add the following code after the comment //Create the different halves constraint

    IloInt mid = nbWeeks / 2;
    IloInt overlap = 0;
    if (n >= 6)
      overlap = IloMin(n / 2, 6);
    for (IloInt i = 0; i < n; i++) {
      for (IloInt j = i + 1; j < n; j++) {
        IloInt g1 = Game(i, j, n);
        IloInt g2 = Game(j, i, n); 
        model.add((weekOfGame[g1] >= mid) == (weekOfGame[g2] < mid));

To constrain that six weeks is the minimum length of time between the two games played between a given pair of teams, you could write a logical constraint using a disjunction. However, IBM ILOG Concert Technology provides a function IloAbs, which not only eases modeling but may also improve performance in the search, since it provides more information.

Step 11: Create the distance constraint

Add the following code after the comment //Create the distance constraint

        if (overlap != 0)
          model.add(IloAbs(weekOfGame[g1] - weekOfGame[g2]) >= overlap);
      }
    }

You next write the constraint on the maximum size of breaks. No team can have a break of length three or greater. In other words, in any sequence of three weeks, a team must play at least one game at home and no more than two games at home. In order to count the number of games at home in a sequence of three weeks, you create a matrix of auxiliary variables indexed on team and week called playHome. The domain of each variable in this matrix is [0..1]. A value of 0 indicates the team plays away that week and a value of 1 indicates that the team plays at home that week.

To constrain each variable in playHome to be assigned the appropriate value, you use the function IloCount. You constrain the value of the element of playHome for that week and team by counting the number of times that a particular team plays at home during a particular week (it must be 0 or 1).

For each team, you represent each sequence of three games with a subarray of the array playHome. Using this subarray and the predefined IBM ILOG Concert Technology function IloSum, you can represent the number of time the team plays at home during the three weeks.

For each team, you constrain the sum of each sequence of three playHome variables for each team to take the value 1 or 2. To do this, you use a range constraint.

Step 12: Add the max break length constraint

Add the following code after the comment //Add max break length constraints

    IloIntVarArray2 playHome(env, n);
    for (IloInt i = 0; i < n; i++) {
      playHome[i] = IloIntVarArray(env, nbWeeks, 0, 1);
      for (IloInt j = 0; j < nbWeeks; j++)
        model.add(playHome[i][j] == IloCount(home[j], i));
      for (IloInt j = 0; j < nbWeeks -3; j++) {
        IloIntVarArray window(env);
        for (IloInt k = j; k < j + 3; k++)
          window.add(playHome[i][k]);
        model.add(1 <= IloSum(window) <= 2);
      }
    }

The final modeling constraint you add states that the team must play either its first game or last game at home, but not both. For each team, you state that the value of its playHome decision variable for the first week must not equal the value of its playHome variable for the last week.

Step 13: Add the constraint on first and last weeks

Add the following code after the comment //Add the constraint on first and last weeks

    for (IloInt i = 0; i < n; i++)
      model.add(playHome[i][0] != playHome[i][nbWeeks-1]);

To complete the model, you add the objective. The objective is constructed similarly to the constraint on break length. Since each break has a length of at most two, you know that there are at most nbWeeks/2 breaks for each team. For each team, you count the number of breaks, which is now easily represented as two consecutive weeks for which the playHome variables are assigned the same value, using an expression comprised of constraints using a self-assigned addition operator. The variable breaks is set to be the total sum of all of the breaks for all the teams. The objective is to minimize the value of breaks.

Step 14: Add the objective

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

    IloIntVarArray teamBreaks(env, n, 0, nbWeeks / 2);
    for (IloInt i = 0; i < n; i++) {
      IloIntExpr nbreaks(env);
      for (IloInt j = 1; j < nbWeeks; j++)
        nbreaks += (playHome[i][j-1] == playHome[i][j]);
      model.add(teamBreaks[i] == nbreaks);
    }
    IloIntVar breaks(env, n - 2, n * (nbWeeks / 2));
    model.add(breaks == IloSum(teamBreaks));
    model.add(IloMinimize(env, breaks));

While the model has now been fully expressed, there are additional constraints that can be introduced to help improve the search. The first set of additional constraints are called surrogate constraints. The second type of additional constraints are constraints used to reduce symmetry.

It is known that a team must play half of its games at home. This is already implicitly expressed in the model within the set of tuples, so you are certain every solution will satisfy this. However, adding an additional constraint on the playHome variables will improve the constraint propagation.

Step 15: Add the surrogate constraints

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

    for (IloInt i = 0; i < n; i++)
      model.add(IloSum(playHome[i]) == nbWeeks / 2);

Since only breaks of size two are allowed, each team must have an even number of breaks. This can be constrained using the IBM ILOG Concert Technology modulus operator, operator%.

Step 16: Add more surrogate constraints

Add the following code after the comment //Add more surrogate constraints

    for (IloInt i = 0; i < n; i++)
      model.add((teamBreaks[i] % 2) == 0);

To help the search perform efficiently, it is also important to reduce symmetry.

Since the teams are interchangeable, you can fix the games scheduled for the first week. This constraint removes only symmetric solutions; it does not eliminate any “real” solutions.

Step 17: Add constraints to reduce symmetry

Add the following code after the comment //Add constraints to fix first week

    for (IloInt i = 0; i < nbGamesPerWeek; i++) {
      model.add(home[0][i] == i * 2);
      model.add(away[0][i] == i * 2 + 1);
    }

Since the slots for a given week are identical with no distinguishing characteristics, you reduce symmetry by forcing an order on which games are assigned to which slots within a week.

Step 18: Add more constraints to reduce symmetry

Add the following code after the comment //Add the slot order constraint

    for (IloInt i = 0; i < nbWeeks; i++)
      for (IloInt j = 1; j < nbGamesPerWeek; j++)
        model.add(games[i][j] > games[i][j-1]);