Solutions can represent not only a complete assignment of decision variables, but also a partial assignment. This allows a solution to represent the change to another solution. When a solution is used to represent the change to another solution, it is called a solution delta.

We can use solution deltas to perform local search for our map coloring problem. Solution deltas make it unnecessary to manipulate the solution directly--instead, the change can be specified in another solution. Predefined Solver goals allow us to examine the application of such a change to a solution.

For instance, consider the following fragment of code which creates four zero-one (0-1) variables and a solution. The variables are added to the solution and each variable is given a stored value of 0 within the solution.

  IloEnv env;
  IloIntVarArray vars(env, 4, 0, 1);
  IloModel model(env);
  model.add(vars);
  IloSolution soln(env);
  soln.add(vars);
  IloInt i;
  for (i = 0; i < vars.getSize(); i++)
    soln.setValue(vars[i], 0);

Suppose we want to make a change to our all-zero solution. We consider as possible changes (or moves), the setting of each variable to 1.

Solver provides a goal, IloScanDeltas, for investigating a set of changes to a solution. However, we first need to define the set of changes. This is done in an array as follows:

  IloSolutionArray deltas(env, vars.getSize());
  for (i = 0; i < vars.getSize(); i++) {
    deltas[i] = IloSolution(env);
    deltas[i].add(vars[i]);
    deltas[i].setValue(vars[i], 1);
  }

The code above creates an array of deltas (one for each original 0-1 variable), and places the desired change (to set the value to 1) to each variable within the delta. We are now in a position to examine the effect each delta will have on the solution. We write:

  IloGoal scan = IloScanDeltas(env, soln, deltas);
  IloSolver solver(model);
  solver.startNewSearch(scan);
  while (solver.next()) {
    for (i = 0; i < vars.getSize(); i++)
      solver.out() << solver.getValue(vars[i]);
    solver.out() << endl;
  }

This code produces the following output:

1000
0100
0010
0001

The IloScanDeltas goal instantiates variables according to the application of each delta to the solution. Note that the solution soln has not been changed by this goal.

IloScanDeltas can be seen as a way of exploring all the moves that can be made from a solution. Often this set of moves is termed the neighborhood of the solution. A single element of the neighborhood is called a neighbor.