Next, the solution prototype is created, which will be used as a basis for all solutions created for use in the genetic algorithm. This solution contains the variables of both the indirect and direct representations.

Add the following code after the comment // Create the solution prototype

  IloSolution prototype(env);
  prototype.add(prio);
  prototype.add(sequence);
  prototype.add(IloMinimize(env, cost));

Here, both the indirect representation (prio) and the direct representation (sequence) are present in the prototype. The objective is also added to the solution which allows different solutions to be compared for quality.

Now, you will create the decoding goal which transforms an assignment in the indirect representation to one in direct representation.

Add the following code after the comment // Create the decoding goal

  IloGoal decode = Decode(env, problem, prio, sequence);

Aside from the environment, the decoding goal takes three parameters: a description of the problem data (problem), the variables of the indirect representation (prio), and those of the direct representation (sequence). You will now move on to implementing this decoding goal which is at the heart of the solving method.

The decoding algorithm must instantiate all variables in sequence by using the values of the variables of prio. Each variable of sequence corresponds not to a car, but to a configuration, whereas each car has a priority in the indirect representation. The decoding algorithm is described below.

Roughly speaking, at each step in the decoding process, the above algorithm places the highest priority unscheduled car compatible with the problem constraints (option capacities and number of each configuration to be built). Note that empty configurations are never considered as candidate vehicles by the above algorithm; they will be inserted automatically when all real configurations are impossible for a particular slot.

The priority theme is quite a general form of indirect representation which can be adapted for numerous other problems.

The decoding algorithm is written as an IlcGoal with a helper class which manages the priorities. This helper class stores a list of ordered priorities for each configuration as opposed to a priority for each car, which makes finding the best configuration faster, without changing the operation of the algorithm.

Add the following code of the helper class after the comment
// Class to produce configs in priority order

class ConfigurationPriorities {
private:
  IlcIntArray2   _priorities;
  IlcRevIntArray _index;

  static void Sort(IlcIntArray a);
public:
  ConfigurationPriorities(CarSeqProblem problem, IlcIntVarArray prio);
  IlcInt getHighestPriority(IlcInt conf) const {
    return _priorities[conf][_index[conf]->getValue()];
  }
  void markScheduled(IlcInt conf) {
    IloSolver solver(_priorities.getSolver());
    _index[conf]->setValue(solver, _index[conf]->getValue() + 1);
  }
};

This class has two fields: _priorities is a two-dimensional array of integers (IlcIntArray2) specifying the priorities. The two indices which access the priorities are the configuration and the index of the car with that configuration. Each column of this priority table is sorted in decreasing order. To give an example, imagine that you have 7 cars to build and two configurations. Assume the first four cars are of configuration one and the remainder have configuration two. Further assume that in a particular solution, the priorities of these cars (as instantiated in prio, passed to the constructor) are {342, 14, 875, 442, 129, 509, 812}. The constructor of ConfigurationPriorities will construct _priorities as follows:

Note that index 0 of _priorities is not used as configuration 0 is the empty configuration; cars of this configuration have no priorities assigned, but are inserted only where necessary. The member function getHighestPriority delivers the priority of the highest priority unscheduled car of the given configuration.

The second field, _index, holds an array of indices in the _priorities array. There is one index for each configuration, and all indices are initialized to zero. For any configuration, all priorities below the index correspond to cars already scheduled, while the remainder correspond to cars waiting to be scheduled. As cars will be scheduled in a backtracking search, the indices are reversible.

The two inline member functions of the ConfigurationPriorities class are now easily explained. getHighestPriority(conf) delivers the priority of the highest priority unscheduled car of configuration conf. This will be used later in deciding between configurations to place in a slot. The member function markScheduled(conf) is called to say that the highest priority unscheduled car of configuration conf has been scheduled, and so the index marker for that configuration should be moved on.

The codes of the constructor and sorting member function are already provided for you.

Now that the helper class has been defined, you will move on to writing the decoding method. This method is implemented as a goal and closely follows the algorithm already given.

Add the following code after the comment // Decode priorities to a sequence

ILCGOAL3(DecodeSlave, ConfigurationPriorities *, priorities,
                      IlcIntVarArray, seq,
                      IlcInt, idx) {
  IlcInt i;
  for (i = idx; i < seq.getSize() && seq[i].isBound(); i++)
    if (seq[i].getValue() != 0)
      priorities->markScheduled(seq[i].getValue());

  // No unbound slots, found a solution
  if (i == seq.getSize())
    return 0;

Here, you have implemented steps 2 and 3 of the decoding algorithm previously given. The decoding goal is passed the helper class, the sequence (direct representation) to decode to, and the current index in the sequence. Any scheduled slots are marked off by the helper class so long as they do not contain the empty configuration. At the end of the for loop, the index i points either to an unbound slot or past the end of the sequence. In the latter case, all slots have been decided, and a solution has been found.

In the next stage of decoding, given a slot to be decided, you will choose for it the highest priority available configuration.

Add the following code after the comment // Decide on a configuration

  IloInt bestPrio = -1;
  IloInt bestConf = 0;
  for (IlcIntExpIterator it(seq[i]); it.ok(); ++it) {
    IlcInt conf = *it;
    if (conf != 0) {
      IlcInt p = priorities->getHighestPriority(conf);
      if (p > bestPrio) {
        bestPrio = p;
        bestConf = conf;
      }
    }
  }

This code is relatively simple, and its function is to exit with bestConf holding the configuration of the highest priority car which can be scheduled in the current slot. Empty configurations are not considered as candidates.

The chosen configuration is placed (with the configuration being removed on backtracking), and the goal recalled.

Add the following code after the comment // Instantiate remainder of sequence

  IlcGoal loop = DecodeSlave(getSolver(), priorities, seq, i);
  return IlcAnd(IlcOr(seq[i] == bestConf, seq[i] != bestConf), loop);
}

The decoding goal needs only a small driving goal (which calls DecodeSlave with an initial zero index) and a wrapper to create an IloGoal from an IlcGoal. These codes are provided for you and are both named Decode.