Model

Step 2: Open the example file

Open the example file <Install_dir>/cpoptimizer/examples/tutorial/cpp/steelmill_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.

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

Step 3: Create the environment and model

The following code which creates the environment and model has been provided for you

int main(int argc, const char * argv[]) {
  IloEnv env;
  try {
    IloModel model(env);
    IloInt m, o, c, q;

You create standard variables to represent the number of orders, nbOrders, the maximum number of slabs needed, nbSlabs, and the number of colors, nbColors. You model the order sizes and colors as arrays of integer values. The possible sizes, or capacities, of the slabs are also modeled as an array.

Step 4: Create the data

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

    IloInt         nbOrders   = 12; 
    IloInt         nbSlabs    = 12; 
    IloInt         nbColors   = 8;
    IloIntArray    capacities(env, 20, 0, 11, 13, 16, 17, 19, 20, 
                                       23, 24, 25, 26, 27, 28, 29, 
                                       30, 33, 34, 40, 43, 45); 
    IloIntArray    sizes(env, nbOrders, 22, 9, 9, 8, 8, 6, 5, 3, 3, 3, 2, 2);
    IloIntArray    colors(env, nbOrders,  5, 3, 4, 5, 7, 3, 6, 0, 2, 3, 1, 5);

The first array of decision variables represents which slab should be used to process each order. To represent this information, you declare an array of decision variables where. This array has nbOrders elements or, in this example, 12. The possible values for these variables represent the ordered slabs. In this example, a value of 0 represents the first slab, a value of 1 represents the second slab, and so on. The array of decision variables where will represent the solution to the problem, after the CP Optimizer engine has found a solution.

The second array of decision variables represents the load assigned to each slab. To represent this information, you declare an array of decision variables load. This array has nbSlabs elements, or, in this example, 12. The possible values for these variables represent the cumulative sum of the sizes of the orders assigned to each slab. The minimum load is 0 and the maximum load is the cumulative sum of the sizes of the entire batch of orders.

Step 5: Declare the decision variables

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

    IloIntVarArray where(env, nbOrders, 0, nbSlabs-1);
    IloIntVarArray load(env, nbSlabs, 0, IloSum(sizes));

You now begin to add the constraints. First you create the constraint that links the where and load variables. For each slab, its load must be equal to the sum of sizes of orders that are assigned to it. To model this, you use the predefined constraint IloPack.

The class IloPack is a subclass of the class IloConstraint. The first argument of the constructor of IloPack is the environment. The second argument is the array of load variables. The third argument is the array for assignments, in this case the slab to which each order is assigned. The fourth argument is the array of order sizes or weights. The fifth argument is an optional name used for debug and trace purposes. Here is the constructor you will use:

  IloPack(const IloEnv env, 
          const IloIntVarArray load, 
          const IloIntVarArray where, 
          const IloIntArray weight, 
          const char * name=0);

The arrays where and sizes are indexed by the orders. For each slab i, the packing constraint requires that the value of load[i] is equal to the sum of the sizes[j] such that the value of where[j] is i.

Step 6: Add the pack constraint

Add the following code after the comment //Add the pack constraint

    model.add(IloPack(env, load, where, sizes));

Next, you create the constraints to constrain the number of colors represented by the orders assigned to a slab. For a given slab, you create an array of expressions colorExpArray which is indexed on the set of colors. Each element has a domain of[0..1] and indicates whether or not at least one order of the corresponding color is assigned to the slab. For each color, you need to determine if an order of that color has been assigned to the given slab. Using the array colorExpArray and the predefined IBM ILOG Concert Technology constraint IloOr, you can link the order assignments to the colorExpArray to represent whether an order of a particular color has been assigned to the slab.

For a given slab m and a given color, you iterate through the orders. If the order, o, is of the given color, then you add the constraint (where[o] == m) to the IloOr logical constraint. If any one of the orders of the given color is assigned to the given slab, then the value of the expression will be 1.

Finally, you constrain the sum of the elements of the colorExpArray to be no greater than two.

Step 7: Add the color constraints

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

    for(m = 0; m < nbSlabs; m++) {
      IloExprArray colorExpArray(env); 
      for(c = 0; c < nbColors; c++) {
        IloOr orExp(env);
        for(o = 0; o < nbOrders; o++){
          if (colors[o] == c){
            orExp.add(where[o] == m);
          }
        } 
        colorExpArray.add(orExp);
      }
      model.add(IloSum(colorExpArray) <= 2); 
    }

To create the objective expression, you calculate an expression to represent the loss for each slab. First you determine, for each possible value of load, the minimum sized slab needed and thus the loss that would be incurred. If a slab has a given load, the loss is the difference between the load assigned to the slab and the minimal size slab needed to process the load.

Step 8: Add the objective

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

    IloIntArray lossValues(env);
    lossValues.add(0);
    for(q = 1; q < capacities.getSize(); q++){ 
      for(IloInt p = capacities[q-1] + 1; p <= capacities[q]; p++){
        lossValues.add(capacities[q] - p);
      }
    }
    IloExpr obj(env);
    for(m = 0; m < nbSlabs; m++){
      obj += lossValues[load[m]];  
    }
    model.add(IloMinimize(env, obj));

Since the slabs are ordered with no distinguishing characteristics, reordering the slabs would produce a number of equivalent solutions. One way to reduce symmetry is to introduce order among variables, as was done in previous lessons. You add constraints that state that the ordered slabs must have decreasing loads. This constraint eliminates some, though not all, symmetric solutions.

Step 9: Add the constraints to reduce symmetry

Add the following code after the comment //Add the constraints to reduce symmetry

    for(m = 1; m < nbSlabs; m++){
      model.add(load[m-1] >= load[m]); 
    }