Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/facility_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 to declare an environment and a model is provided for you as is the code to declare the standard programming variables i and j for use in loops:

int main(int argc, const char* argv[]){
  IloEnv env;
  try{
    IloModel model(env);
    IloInt i, j;

In this lesson, you will input data from the file <Install_dir>/cpoptimizer/examples/data/facility.dat. The code for opening the data file is provided for you:

    const char* filename = "../../../examples/data/facility.dat";
    if (argc > 1)
      filename = argv[1];
    std::ifstream file(filename);
    if (!file){
      env.out() << "usage: " << argv[0] << " <file>" << std::endl;
      throw FileError();
    }

The data from the file <Install_dir>/cpoptimizer/examples/data/facility.dat is:

[ 3, 1, 2, 4, 1]
[ 480, 200, 320, 340, 300]
[[ 24, 74, 31, 51, 84], 
 [ 57, 54, 86, 61, 68],
 [ 57, 67, 29, 91, 71],
 [ 54, 54, 65, 82, 94],
 [ 98, 81, 16, 61, 27],
 [ 13, 92, 34, 94, 87],
 [ 54, 72, 41, 12, 78],
 [ 54, 64, 65, 89, 89]]

You create standard programming variables to represent the number of stores, nbStores, and the number of supplier warehouses, nbLocations. You model the capacities and fixed costs of the potential warehouses as arrays of integer values.

The constructor of the class IloIntArray takes an environment as its first argument. The second argument is the number of integer values in the array, which is extensible. The elements of the new array take the values that are passed as the remaining arguments. Here is one constructor:

  IloIntArray(const IloEnv env, IloInt n, const IloInt v0, ...);

In this lesson however, you create empty arrays which will be filled directly from the data file. To do this, you pass solely the first argument, the environment, to the constructor.

You model the matrix of relative supply costs as an array of arrays. To create this cost matrix, you use the Concert Technology template IloArray.

To model the supply costs, you create an IloArray in which each of the elements is an IloIntArray.

Step 3: Model the data

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

    IloIntArray capacity(env), fixedCost(env);
    IloArray<IloIntArray> cost(env);
    IloInt nbLocations;
    IloInt nbStores;

Now, you input the data from the data file. The overloaded C++ operator>> directs input from an input stream.

Step 4: Input the data

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

    file >> capacity >> fixedCost >> cost;

The number of stores can be deduced from the size of the cost matrix. The number of supplier warehouses can be deduced from the size of the capacity array. Calculating these values from the data read from the file allows you to easily extend the example by using another data file. The code for determining the values of nbLocations and nbStores is provided for you:

    nbLocations = capacity.getSize();
    nbStores = cost.getSize();

Next, you represent the first set of unknowns in this problem, the warehouse that will serve each store. IBM ILOG Concert Technology gives you the means to represent these unknowns as an array of constrained integer variables. You associate one decision variable in the array with each store.

The constructor of the class IloIntVarArray takes an environment as its first argument. The second argument is the number of decision variables in the array. Arrays are extensible, so you can later increase or reduce the number of variables in the array. The third and fourth arguments are the lower and upper bounds of the domain of possible values for each variable in the array. When you use an array, you can access a variable in that array by its index, and the operator[] is overloaded for this purpose. Here is a constructor:

  IloIntVarArray (const IloEnv env,
                  IloInt n,
                  IloInt lb,
                  IloInt ub);

The first array of decision variables, called supplier, represents which supplier warehouse should supply each store. This array has nbStores elements or, in this example, 10. The domain of possible values for each of these variables represent the supplier warehouses. In this example, a value of 0 represents Bonn, a value of 1 represents Bordeaux, a value of 2 represents London, a value of 3 represents Paris, and a value of 4 represents Rome.

For each store, the associated decision variable in the array supplier can be assigned one value in a solution, so each solution will satisfy the constraint that a store must be served by exactly one warehouse. The array of decision variables supplier will represent the solution to the problem, after it has been solved.

Step 5: Declare the supplier decision variables

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

    IloIntVarArray supplier(env, nbStores, 0, nbLocations - 1);

To represent whether a potential supplier warehouse site should be open or not, you declare another array of decision variables, open. It has nbLocations elements or, in this example, 5. There are two possible values for each variable, 0 and 1. The value of 1 indicates that the warehouse is open and 0 indicates that the warehouse is not open.

Step 6: Declare the warehouse open decision variables

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

    IloIntVarArray open(env, nbLocations, 0, 1);

Now you add the constraints. The first constraint states that the supplier warehouse used by a given store must be open. In other words, the warehouse must be open if a store is to be supplied by it. For example, if store 0 is supplied by the Rome warehouse, the constraint states that the variable of the open array that is associated with the Rome warehouse must be assigned the value 1. The Rome warehouse must be open.

This interdependence of the decision variable arrays supplier and open is modeled through the use of an element expression.

For each store i, the warehouse that supplies that store is represented by supplier[i]. To indicate that supplier[i] must be open, you constrain open[supplier[i]] to be assigned the value 1.

Step 7: Add the constraints on open warehouses

Add the following code after the comment //Add the constraint on open warehouses

    for (i = 0; i < nbStores; i++)
      model.add(open[supplier[i]] == 1);

Next, you need to compute the number of stores being supplied by a particular warehouse and ensure that this value does not exceed the capacity of the warehouse. You can use the IBM ILOG Concert Technology function IloCount to represent the number of times a warehouse is assigned to be a supplier.

The function IloCount takes two arguments, an array of decision variables and an integer value, and returns an instance of IloIntExprArg that represents the number of times the value appears in the array. 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 IloCount that you will use:

  IloIntExprArg IloCount(const IloIntVarArray vars, IloInt value);

For each warehouse, you count the number of times it appears in the array supplier using the function IloCount. You constrain this expression to be no greater than the warehouse capacity using operator<=.

Step 8: Add the constraints on warehouse capacity

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

    for (j = 0; j < nbLocations; j++)
      model.add(IloCount(supplier, j)  <= capacity[j]);

Finally, you consider the objective. The objective in a constraint programming model is an expression that can be maximized or minimized. Expressions in IBM ILOG Concert Technology are generally represented by the classes IloExpr and its subclasses IloIntExpr and IloNumExpr.

Many Concert Technology functions, such as IloCount, return expressions. During search, expressions have domains of possible values like decision variables. Unlike variables, these domains are not stored but instead calculated based on the basic elements of the expression.

To build the objective expression, you need to represent the sum of the fixed costs of all the warehouses that are to be opened. This cost can be modeled as the scalar product of the fixedCost array and the open array. To express the fixed cost expression, you use the Concert Technology function IloScalProd.

The function IloScalProd takes two arguments, both arrays, and returns an instance of IloIntExprArg that represents the scalar product of the two arrays. Although you should not use an IloIntExprArg directly, it can be cast to an IloIntExpr, which you should use instead. Here is the signature of the function IloScalProd that you will use:

  IloIntExprArg IloScalProd(const IloIntVarArray vars, 
                            const IloIntArray values);

You declare the integer expression obj to be the expression returned by the IloScalProd function called with the arguments open and fixedCost. To complete the objective expression, you must also add the supply costs to it. To express the cost of supplying each store from the warehouse selected to supply it, you use an element expression. For each store i, the cost of supplying the store from the assigned warehouse is cost[i][supplier[i]]. You can incrementally add these costs to the expression obj by using the self-assigned addition operator.

Step 9: Create the objective expression

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

    IloIntExpr obj = IloScalProd(open, fixedCost);
    for (i = 0; i < nbStores; i++)
      obj += cost[i][supplier[i]];

To add the objective to the model, you first use the function IloMinimize, which creates an instance of the class IloObjective. The function IloMinimize takes the environment as its first argument and an expression as its second argument. The last argument is an optional name used for debug and trace purposes. Here is signature of the IloMinimize function that you will use:

  IloObjective IloMinimize(const IloEnv env,
                           const IloExpr expr, 
                           const char* name=0);

You then use the member function IloModel::add to add the objective to the model. You must explicitly add an objective to the model or the CP Optimizer engine will not use it in the search for a solution. If an objective has been added to the model, the optimizer will search for an optimal solution which minimizes the value of the objective.

Step 10: Add the objective to the model

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

    model.add(IloMinimize(env, obj));