IBM ILOG Solver User's Manual > More on Modeling > Using Table Constraints: Scheduling Teams > Complete program

The complete table constraint program follows. You can also view it online in the file YourSolverHome/examples/src/sports_basic.cpp.

#include <ilsolver/ilosolver.h>
ILOSTLBEGIN
 
IloInt nbTeams;
IloInt nbWeeks;
IloInt nbPeriods;
IloInt nbSlots;
 
int main(int argc, char** argv){
  IloInt i;
  IloInt j;
  IloInt m;
  IloInt p;
  IloInt w;
 
  nbTeams = (argc>1? atol(argv[1] ) : 8 );
  if ( nbTeams % 2 ) ++nbTeams;
  nbWeeks = nbTeams-1;
  nbPeriods = nbTeams /2;
  nbSlots = nbWeeks * nbPeriods;
  IloEnv env;
    try {
      IloModel model(env);
 
      IloArray<IloIntVarArray> slotVars(env, nbPeriods);
 
      for(i = 0; i < nbPeriods; i++)
        slotVars[i] = IloIntVarArray(env, nbWeeks, 0, nbSlots-1);
// ie : NumVarMatrix slotVars = IloArray<IloNumVarArray>(env, nbPeriods);
// build copy vector of match variables matrix
      IloIntVarArray matchVars(env, nbSlots);
      IloInt s = 0;
      for (p = 0; p < nbPeriods; ++p) {
        for (w = 0; w < nbWeeks; ++w) {
          matchVars[s] = slotVars[p][w];
          ++s;
        }
      }
      IloArray<IloIntVarArray> homeTeamVars(env, nbPeriods);
      IloArray<IloIntVarArray> awayTeamVars(env, nbPeriods);
 
      for (p = 0; p < nbPeriods; ++p) {
        homeTeamVars[p]  = IloIntVarArray(env, nbWeeks, 0, nbTeams-1);
        awayTeamVars[p] = IloIntVarArray(env, nbWeeks, 0, nbTeams-1);
      }
// ---------------------------------
// Constraint 1 : each team plays each other exactly once,
// i.e. a match (T1, T2) occurs exactly once.
// ---------------------------------
      model.add( IloAllDiff(env, matchVars));
// ---------------------------------
// Constraint 2 : each week, all teams do play.
// remember 2*nbPeriods == nbTeams.
// ---------------------------------
      for (w = 0; w < nbWeeks; ++w) {
        IloIntVarArray weekTeams(env, nbTeams);
        for (p = 0; p < nbPeriods; ++p) {
          weekTeams[2*p]   = homeTeamVars [p][w];
          weekTeams[2*p+1] = awayTeamVars[p][w];
        }
        model.add( IloAllDiff(env, weekTeams) );
      }
// ---------------------------------
// constraint 3 : in each period, each team plays no more than twice.
// one can demonstrate that the number of occurences of each team in
// one period is at least 1, so we constrain it to be in [1..2]
// ---------------------------------
      IloIntArray teams(env, nbTeams);
        for (m = 0; m < nbTeams; ++m)
          teams[m] = m;
          for (p = 0; p < nbPeriods; ++p) {
            IloIntVarArray periodTeams(env, 2*nbWeeks);
            for ( w = 0; w < nbWeeks; ++w) {
              periodTeams[ 2*w ]   = homeTeamVars [p][w];
              periodTeams[ 2*w+1 ] = awayTeamVars[p][w];
            };
            IloIntVarArray cardVars(env, nbTeams, 1, 2);
            model.add( IloDistribute(env, cardVars, teams, periodTeams) );
          }
// ---------------------------------
// Constraint 4: link team and match vars with table constraint
// ---------------------------------
      IloIntTupleSet tuple(env, 3);
      IloInt m = 0;
        for (i=0; i < nbTeams; ++i) {
          for ( j=i+1; j < nbTeams; ++j) {
            tuple.add(IloIntArray(env, 3, i, j, m));
            ++m;
          }
        }
      assert( m == nbSlots );
      for (p = 0; p < nbPeriods; ++p) {
        for (w = 0; w < nbWeeks; ++w) {
          IloIntVarArray slotConsistencyTest(env, 3);
          slotConsistencyTest[0] = homeTeamVars[p][w];
          slotConsistencyTest[1] = awayTeamVars[p][w];
          slotConsistencyTest[2] = slotVars[p][w];
          model.add(IloTableConstraint(env,
                                       slotConsistencyTest,
                                       tuple,
                                       IloTrue));
        }
      }
      IloSolver solver(model);
      if (solver.solve()) {
        cout << endl << "SOLUTION" << endl;
        for (p=0; p < nbPeriods; ++p) {
             cout << "period " << p << " : ";
               for (w=0; w < nbWeeks; ++w) {
               cout << solver.getValue(homeTeamVars[p][w]) << " vs "
                   << solver.getValue(awayTeamVars[p][w]) << " - " ;
             }
         cout << endl;
        }
        solver.printInformation();
          }
      else
        cout << "**** NO SOLUTION ****" << endl;
      }
    catch (IloException& ex) {
       cerr << "Error: " << ex << endl;
    }
  env.end();
  return 0;
}
 
 
 

Results

The information displayed by IloSolver::printInformation will vary depending on platform, machine, configuration, and so on.

%
* sports scheduling teams: 8 weeks: 7 periods: 4
 
SOLUTION
period 0 : 0 vs 1 - 0 vs 2 - 1 vs 2 - 3 vs 4 - 3 vs 5 - 4 vs 5 - 6 vs 7 -
period 1 : 2 vs 3 - 3 vs 6 - 4 vs 6 - 0 vs 7 - 0 vs 4 - 2 vs 7 - 1 vs 5 -
period 2 : 4 vs 7 - 5 vs 7 - 0 vs 5 - 1 vs 6 - 2 vs 6 - 1 vs 3 - 0 vs 3 -
period 3 : 5 vs 6 - 1 vs 4 - 3 vs 7 - 2 vs 5 - 1 vs 7 - 0 vs 6 - 2 vs 4 -
%