The previous section mentioned the use of the decreasing best fit method of bin packing. In this section, you will implement this method in an Solver goal. First of all, you will use the algorithm below:

As you can see, this algorithm is extremely simple. Items are considered, heaviest first, and packed in the first possible bin. New bins are added when they are needed.

To take advantage of constraint programming, the Solver version of this method (a goal) will be slightly more complicated. The difference will be that decisions can be backtracked. So, for example, if item i were packed into bin b, then on backtracking, the same item is forbidden from being packed in bin b. This means that the goal is much more robust as it can recover from errors and has the potential to perform a complete search over the packing problem.

A backtracking goal is required in this example, as here, advantage is taken of constraint programming to constrain the genetic algorithm to produce ``good'' solutions. This means constraining the number of available bins when generating a new solution. In this case an error, as described above, is the production of a packing that uses more bins than desired. In such a case, a backtrack occurs to change a previous decision in the search of a solution respecting the desired number of bins.

You will now write the packing goal. Add the following code after the comment
// A simple goal to pack bins

ILCGOAL3(Pack, IlcIntVarArray, load,
               IlcIntVarArray, where,
               IlcIntArray, weight) {
  IlcGoal g;
  IlcInt i = IlcChooseFirstUnboundInt(where); 
  if (i >= 0) {
    IlcInt b = where[i].getMin();
    IlcConstraint ct = where[i] == b; 
    IlcGoal pack = load[b].getMin() == 0 ? ct: IlcOr(ct, !ct);
    g = IlcAnd(pack, this);
  }
  return g;
}

It is assumed here that the items are sorted in non-increasing order of weight. This example does this by ordering the weights in this way in the input file.

The goal follows the algorithm straightforwardly, except in the creation of choice points to allow backtracking. The test of the load of the bin against zero is used to ensure that only one empty bin--the first one--is considered for packing. That is, the goal does not backtrack on the choice to put an item in an empty bin as all choices of placing the item into a non-empty bin by this point have been exhausted, and all empty bins are equivalent.