Model

Once the map coloring problem has been described using natural language, you then use Concert Technology classes to model the constraint programming problem.

After you have written a description of your problem, you can use IBM® ILOG® Concert Technology classes to model it. After you create a model of your problem, you can use CP Optimizer classes and functions to search for a solution.

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/color_partial.cpp in your development environment. This file is a program that is only partially completed. You will 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 creating the array of names for the color values and for printing out the solution found by the CP Optimizer engine is provided.

The first step in converting your natural language description of the problem into code using Concert Technology classes is to create an environment and a model.

Note:

Environment

An instance of the class IloEnv manages the internal modeling issues, which include handling output, memory management for modeling objects and termination of search algorithms.

This instance is typically referred to as the environment. Normally an application needs only one environment, but you can create as many environments as you want.

In the C# and Java™ APIs, the environment object is not public. To free memory used by a model in C# API, you use the method CP.End. To free memory used by a model in the Java API, you use the method IloCP.end.

Step 3: Create the environment

Add the following code after the comment //Create the environment 


  IloEnv env;

The initialization of the environment creates internal data structures to be used in the rest of the code. After this initialization is performed, you can create a model.

Note:

Model

A model is a container for modeling objects such as decision variables, objectives and constraints.

The first argument passed to the constructor of the class IloModel is the environment. The second argument is an optional name used for debug and trace purposes. Here is a constructor: 


  IloModel(const IloEnv env, const char * name=0);

Step 4: Create the model

Add the following code after the comment //Create the model 


    IloModel model(env);

After solving your problem, you can reclaim memory for all modeling objects and clean up internal data structures by calling IloEnv::end for every environment you have created. This clean-up should always be done before you exit your application. The call to end the environment is already included in the lesson code.

In the Microsoft .NET Framework languages and Java APIs, all memory associated with the solving of the problem is reclaimed automatically when the optimizer object is garbaged.

IBM ILOG Concert Technology gives you the means to represent the unknowns in this problem, the color of each country on the map, as constrained integer, or decision, variables.

Note:

Decision Variable

Integer decision variables are represented by IloIntVar in the C++ and Java APIs and by IIntVar in the C# API of Concert Technology.

A constrained integer variable is a decision variable that has integers as possible values. Typically, the possible values are represented as a domain of integers with an upper bound and a lower bound. These variables are said to be constrained because constraints can be placed on them.

The first argument passed to the constructor of the class IloIntVar is always the environment. The second argument is the lower bound of the domain of possible values, which defaults to 0. The third argument is the upper bound of the domain of possible values. The upper bound defaults to IloIntMax, which represents the largest possible positive integer on a given platform. The fourth argument is an optional name used for debug and trace purposes. Here is a constructor: 


  IloIntVar(const IloEnv env, 
            IloInt lb = 0, 
            IloInt ub = IloIntMax
            const char* name = 0);

After you create an environment and a model, you declare the decision variables, one for each country. Each variable represents the unknown information, the color of the country. The domain of each decision variable is [0..3] or 0 to 3 inclusive.

These values represent the possible colors:

  • the value 0 represents the color blue;

  • the value 1 represents the color white;

  • the value 2 represents the color yellow;

  • the value 3 represents the color green.

After the problem is solved, the values assigned to these decision variables will represent the solution to the problem.

Step 5: Declare the decision variables

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


    IloIntVar Belgium(env, 0, 3), Denmark(env, 0, 3), 
      France(env, 0, 3), Germany(env, 0, 3), 
      Luxembourg(env, 0, 3), Netherlands(env, 0, 3);

IBM ILOG Concert Technology allows you to express constraints involving decision variables using the following operators:

  • equality (==),

  • less than or equal to (<=),

  • less than (<),

  • greater than or equal to (>=),

  • greater than (>) and

  • not equal to (!=).

In this example, you use a constraint to require that if two countries are neighbors, they cannot be the same color. For example, the statement Belgium != France indicates that the neighbors France and Belgium should not share the same color. Explicitly, it means that the value the CP Optimizer engine assigns to the decision variable Belgium cannot equal the value the optimizer assigns to the variable France.

Note:

Constraint

Constraints specify the restrictions on the values that may be assigned to decision variables. To create a constraint for a model, you can:

  • use an arithmetic operator between decision variables and expressions to return a constraint,

  • use a function that returns a constraint,

  • use a specialized constraint or

  • use a logical operator between constraints which returns a constraint.

Expressions, logical constraints and specialized constraints will all be introduced in later lessons.

After you create a constraint, you must explicitly add it to the model in order for it to be taken into account by the CP Optimizer engine.

You use the member function IloModel::add to add constraints to the model. You must explicitly add a constraint to the model object or the CP Optimizer engine will not use it in the search for a solution.

Step 6: Add the constraints

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


    model.add(Belgium != France); 
    model.add(Belgium != Germany); 
    model.add(Belgium != Netherlands);
    model.add(Belgium != Luxembourg);
    model.add(Denmark != Germany ); 
    model.add(France != Germany); 
    model.add(France != Luxembourg); 
    model.add(Germany != Luxembourg);
    model.add(Germany != Netherlands);