Solve

Once the map coloring problem has been described and modeled, you use CP Optimizer classes and functions to solve the constraint programming problem.

Solving a problem consists of finding a value for each decision variable so that all constraints are satisfied. You may not always know beforehand whether there is a solution that satisfies all the constraints of the problem. In some cases, there may be no solution. In other cases, there may be many solutions to a problem.

You use an instance of the class IloCP to solve a problem expressed in a model.

Note:

Optimizer

The class IloCP in the C++ API and the Java™ API and the class CP in the C# API can be used to employ different algorithms for solving problems modeled with Concert Technology modeling classes.

An object of this class is sometimes referred to as the optimizer.

The constructor for IloCP takes an IloModel as its argument.

Step 7: Create an instance of IloCP

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


    IloCP cp(model);

You now use the member function IloCP::solve, which solves the problem contained in the model by using constructive search and constraint propagation. It is possible to modify the search using tuning objects and search parameters (more on this in Using search parameters: team building).

Step 8: Search for a solution

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


    if (cp.solve())

The member function IloCP::solve returns a Boolean value of type IloBool. If a solution is found, a value of IloTrue is returned.

After a solution has been found, you can use member functions of IloAlgorithm, the base class for algorithms in IBM® ILOG® Concert Technology, to examine that solution. The member function IloAlgorithm::getValue takes a decision variable as an argument and returns the value the CP Optimizer engine has assigned to that variable. When you print the solution, you associate each value with the name of a color using the array Names[]. The value 0 is associated with Names[0], which is the first array element “blue”; the value 1 is associated with Names[1], which is the second array element “white”; and so on. The array Names[] is already created for you in the lesson code.

The member function IloAlgorithm::getStatus returns a status code which provides information about the solution that the optimizer has found. The stream IloAlgorithm::out is the communication stream for general output.

The code for displaying the solution has been provided for you:


      cp.out() << std::endl << cp.getStatus() << " Solution" << std::endl;
      cp.out() << "Belgium:     " << Names[cp.getValue(Belgium)] << std::endl;
      cp.out() << "Denmark:     " << Names[cp.getValue(Denmark)] << std::endl;
      cp.out() << "France:      " << Names[cp.getValue(France)] << std::endl;
      cp.out() << "Germany:     " << Names[cp.getValue(Germany)] << std::endl;
      cp.out() << "Luxembourg:  " << Names[cp.getValue(Luxembourg)]  << std::endl;
      cp.out() << "Netherlands: " << Names[cp.getValue(Netherlands)] << std::endl;

Note:

If there is more than one set of values for the variables that satisfy the constraints of the problem, there is more than one solution. Within your problem, there may be certain criteria that make one such set of values more appropriate than another as a solution. This appropriateness is usually measured in terms of a cost function that can be optimized. You can read more on cost functions, also called objectives, in Using arrays and objectives: warehouse location

Step 9: Compile and run the program

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


Feasible Solution
Belgium:     yellow
Denmark:     blue
France:      blue
Germany:     white
Luxembourg:  green
Netherlands: blue

As you can see, all four colors are used.

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