Problem representation: Cost variable

IBM ILOG Solver User's Manual > Evolutionary Algorithms > Car Sequencing Using EA > Problem representation: Cost variable

Problem representation: Cost variable

INDEX

PREVIOUS NEXT

The example contains a lot of code related to the reading of car sequencing problem instances and the construction of the model. As the focus of this lesson is on the use of genetic algorithms, and not on modeling, it is therefore suggested that you take some time to examine the CarSeqProblem structure which holds information about the car sequencing problem, and the BuildModel function which builds the car sequencing model. When you feel you are familiar with these, you can move on with the rest of the lesson.

The example code includes a function called SolveWithGA which will be used as the main entry point for the lesson. Its signature is below:

void SolveWithGA(IloSolver solver,
                 IloModel model,
                 CarSeqProblem problem,
                 IloIntVarArray sequence,
                 IloIntVar cost) {

The function takes the following parameters:

solver: an instance of IloSolver, to use as an engine;
model: the IBM® ILOG® Concert Technology model of the car sequencing problem;
problem: an instance of CarSeqProblem containing problem data;
sequence: the direct representation. An array of constrained variables holding the sequence of car configurations to be built;
cost: the cost variable to be minimized. If cost is reduced to 0, a solution to the original car sequencing problem has been found.

The code to create all of the above objects is in the partially completed example with the exception of the cost variable. You will therefore write the code which will create it now, but first let us describe the idea. Assume that the original car sequencing problem required the scheduling of n cars in n slots. As explained, this problem is modified to allow up to n + s slots, where s is the amount of slack, that is the number of empty configurations available. The cost is the number of empty configurations that appear before the last car in the schedule. However, such a calculation can be difficult to model; a simpler, equivalent alternative is to look at the last s slots of the sequence. Let k be the number of empty configurations occurring after the last car in this part; the cost is then s - k.

The problem is now to model the cost via such a calculation of k.


Step 1 -	Build the cost variable

Add the following code after the comment

// Build the cost variable

IloIntVar BuildCostVar(IloModel model, IloIntVarArray seq, IloInt slack) {
  IloEnv env(model.getEnv());
  IloIntVar cost(env, 0, slack);
  IloConstraintArray carAfter(env, slack);
  for (IloInt i = slack - 1; i >= 0; i--) {
    IlcInt j = seq.getSize() - slack + i;
    carAfter[i] = seq[j] != 0;
    if (i < slack - 1)
      carAfter[i] = carAfter[i] || carAfter[i + 1];
    model.add(carAfter[i] == cost > i);
  }
  return cost;
}

This code can seem complex, but can be broken down quite easily. carAfter[i] is true if and only if a car appears at or after position i in the slack area (last s elements of the sequence). Using carAfter, constraints then state that for each position i, the cost is strictly greater than i if and only if there is a car at i or after. Thus, if all elements of carAfter up to and including i are false, and are then true afterwards, then carAfter[i] being true ensures that cost > i, while carAfter[i+1] being true ensures that cost <= i+1, thus assigning the cost to the value i+1.

PREVIOUS NEXT