For the car-sequencing problem, the order in which variables are chosen and values are tried proves to be quite important. As you try to decide the order in which to choose variables, you will notice that variables at the extremities (the beginning or the end of a sequence) are less constrained than variables in the middle of the sequence. For that reason, you begin ordering the variables by choosing the one closest to the middle of the sequence.

If you do not order the values carefully, you cannot solve a car-sequencing problem within a reasonable amount of time, so you must pay attention to this part of the problem, too.

First, the most difficult constraints are tied to options. However, in a conventional backtracking problem, the basic decision is to assign a value to a variable; that is, to assign a configuration to a car. This practice is not tied directly to the difficult constraints. For example, suppose that option 1 is required by configurations 1, 2, and 3, and furthermore that you assign configuration 1 to a given car. There is no solution with this assignment because of the capacity of option 1. Consequently, the algorithm backtracks to try another value, say, configuration 2 this time. But again, for the same reason--the limited capacity of the option--this trial also leads to failure. In other words, you will see thrashing, as values are tried and discarded for the same reason.

It is better to try another kind of value ordering: you first try to assign those options for which the demand is close to their capacity. To distinguish those options, the slack of an option with capacity pj/qj required to be scheduled kj times is defined like this:

n - qj(kj/pj)

In this context, slack is a good measure of how much an option is used. If the slack of an option is negative, the capacity constraint on the option cannot be satisfied. If the slack is large, however, the capacity constraint on the option is easy to satisfy.

The enumeration algorithm is a combination of these two ways of ordering variables and values; both depart from the conventional backtracking algorithm. Instead of choosing a variable and then trying a value for it, as you might conventionally do, you progressively reduce the domains of the variables. How do you do that? As the first option, you select the one with the least slack; then you try to assign it to the appropriate variables. To assign an option o to a variable x, you remove the configurations that do not use o from the domain of x. In other words, you generally reduce the domain.

More precisely, you select the option oj with the least slack. If this option is required kj times, you try to assign this option to k variables. To do so requires a tree search, where the variables that are closest to the middle of the sequence are tried first. If you succeed in assigning option o k times, you recursively call the algorithm with a new option. If not, you backtrack to the previous level of the algorithm.

As the algorithm backtracks, it propagates constraints at each node. However, these nodes are defined differently from those in a conventional backtracking algorithm, where branches correspond to the assignment of a value to a variable. In this case, a branch corresponds instead to the assignment of an option to a variable; that is, a reduction of the domain of the variable.

Moreover, a given variable may appear at different levels in the search tree, since its domain may be reduced more than once. To get a clearer idea of this, consider for example a configuration, say, c1 that requires option o1, along with the option o2 which is assigned to x in a given solution. In this example, x appears two times among the branches leading to that solution: once when o2 is assigned to x and again when o1 is assigned to it.

In that context, this algorithm tries first to consider the most constrained choices.

These ideas can be implemented straightforwardly by Boolean variables to represent whether a configuration assigned to a car does or does not require a given option. More formally, you use nbOptions*nbCars Boolean variables. The Boolean variable o[i*nbCars+j] is IloTrue if the car at the position i is assigned the configuration that requires the option j; otherwise, the Boolean variable is IloFalse. Here is how you define those variables:

    IloBoolVarArray bvars(env,nbOptions*nbCars);
    for(i=0;i < nbOptions;i++){
      opt=(IloInt)order[i];
      IloBoolVarArray bv(env,nbCars);
      for (j = 0; j < nbCars; j++)
        bv[j] = IloBoolVar(env);
      model.add(IloBoolAbstraction(env, bv, cars, optConf[opt]));
      for(j=0;j<nbCars;j++){
        bvars[i*nbCars + j] = bv[j];
      }
    }
    cout << "Pass 4 " << endl;

In order to instantiate the variable at the middle of the sequence first, you simply reorder the array of Boolean variables. Here is the code to do that:

    IloBoolVarArray tbvars(env,nbOptions*nbCars);
    for(j=0;j<nbOptions*nbCars;j+=nbCars){
      IlcInt mid=nbCars/2 - 1;
      for(i=0;i<mid+1;i++){
        tbvars[2*i+j]=bvars[mid-i+j];
        tbvars[2*i+1+j]=bvars[mid+i+1+j];
      }
    }

The order in which the options are chosen is given explicitly for this example. Here is the code:

    IloIntArray order(env, nbOptions);
    switch(example){
    case 1:{
      order[OL]=0;
      order[1]=1;
      order[2]=4;
      order[3]=2;
      order[4]=3;
    } break;
    case 2:{
      order[OL]=0;
      order[1]=4;
      order[2]=1;
      order[3]=2;
      order[4]=3;
    }break;
    }

That order, of course, respects the definition of slack.