Once you have written a description of your problem, you can use Concert Technology classes to model it.

Open the example file YourSolverHome/examples/src/tutorial/graph_partial.cpp in your development environment.

You want to be able to run this program and test graphs of different sizes, so you create a function testGraph to run the test. It has one parameter, nTest, which is the size of the maximal cliques of the graph.

Add the following code after the comment //Declare the testGraph function

void testGraph(IloInt nTest)

Next, you create the environment and the model. The parameter nTest is the size of the maximal clique, which is n-1 in this problem. Since n must be an even number for this problem, you check if nTest is an even number. If it is not, you increment nTest by 1 to get the size n of the graph. This code is provided for you:

{
  IloEnv env;
  try {
    IloModel model(env);
    IloInt n = (nTest%2)?nTest+1:nTest;

Then you set the number of nodes, nbNodes, equal to n*(n-1)/2 and the number of colors, nbColors, equal to n-1. You declare i and j for use in loops. This code is provided for you:

    IloInt nbNodes = n*(n-1)/2;
    IloInt nbColors = n-1;
    IloInt i, j;

Now you declare the variables, using an instance of IloIntVarArray. The array contains nbNodes variables. The variables in the array represent the unknown information--the color of each node. Each variable takes a value in the domain of integers from 0 to nbColors-1. These values represent the possible colors.

Add the following code after the comment //Declare the decision variables

    IloIntVarArray vars(env,nbNodes,0,nbColors-1);
    for(i = 0; i < n-2; i++){
      model.add(vars[i] < vars[i+1]);
    }

Now that you have created the variables, you create the maximal cliques using the function createClique. The function createClique is declared before the function testGraph. It is used to build the cliques. The following code is provided for you:

IloInt createClique(IloInt i, IloInt j, IloInt n){
  if (j >= i) return (i*n-i*(i+1)/2+j-i);
  else return createClique(j,i-1,n);
}

For each clique, you add the predefined constraint IloAllDiff. This constraint states that every node in that maximal clique must be a different color.

Add the following code after the comment
//Create the cliques and add the IloAllDiff constraint

    for(i = 0; i < n; i++){
      IloIntVarArray clique(env,n-1);
      for(j = 0; j < n-1; j++){
            clique[j] = vars[createClique(i,j, n)];
      }
      model.add(IloAllDiff(env,clique));
    }

To demonstrate how the createClique function works, consider a graph with n = 4. There are 6 or 4 * (4 - 1)/2 nodes. Every node belongs to exactly two maximal cliques of size 3 or 4 - 1.

The "for" loops and the function createClique create these maximal cliques. The createClique function takes three parameters: i, j, and n. For i=0 and j=0 and n=4, the createClique function returns (i*n - i*(i+1)/2 + j - i) or
(0*4 - 0*(0 + 1)/2 + 0 - 0) = 0. This corresponds to element [0] in the array vars, or node 0. In the second loop using j, i=0 and j=1 and n=4 and the createClique function returns 1. This corresponds to element [1] in the array vars, or node 1. In the third loop using j, i=0 and j=2 and n=4 and the createClique function returns 2. This corresponds to element [2] in the array vars, or node 2. After the loop using j has run three times, the code has created an array of variables clique. This array contains three elements: the variables representing nodes 0, 1, and 2. You use IloAllDiff to add the constraint to the model that these three variables must all be different from each other. This procedure is then followed for i=1, and so on. The following table shows the results of the "for" loops for a n = 4 graph:

In other words, there are four maximal cliques:

For each clique, you use the predefined constraint IloAllDiff to state that every node in that clique must be a different color.