As outlined in the introduction, there are two essential components to LNS. The first is the choice of "fragment"; the part of the solution which can change its value. The second is the completion method, which instantiates the fragment to some new value. Solver IIM uses goals for the latter task (instances of IloGoal), and for the former uses neighborhoods (instances of IloNHood), although the neighborhoods are quite particular in nature.

Normally, this neighborhood has only one neighbor which might be termed a "meta-neighbor" as it defines the fragment and thus the search space for the completion goal. There is a special subclass of IloNHoodI, IloLargeNHoodI which is used to define large neighborhoods; full details can be found in the IBM ILOG Solver Reference Manual. However, for now you will not need to understand any details, or even how to subclass IloLargeNHoodI. A simple interface is provided via the macro ILODEFINELNSFRAGMENT1 (and its variants) which you will use here to define an LNS fragment for the talent scheduling problem.

You will now create the instance of IloNHood which defines a fragment.

Insert the following code after the comment
// Define an LNS fragment which is a random segment

ILODEFINELNSFRAGMENT1(SegmentLNSNHood, solver, IloIntVarArray, x) {
  IlcRandom r = solver.getRandom(); 
  IloInt a = r.getInt(x.getSize());
  IloInt b = r.getInt(x.getSize());
  if (a > b) { IloInt tmp = a; a = b; b = tmp; }
  for (IlcInt i = a; i <= b; i++)
    addToFragment(solver, x[i]);
}

This code chooses as a fragment a random segment in the schedule. That is, you will authorize changes to variables from indices a to b where a and b are randomly chosen. It is essential that the fragment is chosen with some random element. If not, the same fragment will be chosen time and time again, and the search will stagnate very quickly with no improvements possible. In the macro ILODEFINELNSFRAGMENT, you must call the service function addToFragment for every variable that you wish to include in the part of the solution that can change its value. The macro takes only two mandatory parameters: the name of the neighborhood function to create, and the name of an instance of IloSolver which will be received. Depending on the particular instance of the macro chosen, optional parameters may then be added in the usual way by pairs of type and variable name. The macro also has other services available like retrieving the current solution: see the documentation of IloLargeNHoodI in the IBM ILOG Solver Reference Manual.

In this fragment, two indices are chosen randomly using the solver's random number generator. These indices are interchanged to make sure that a is no greater than b. Finally, all variables from a to b are added to the fragment.

Now that you have created the fragment-defining neighborhood, you can move on to the large neighborhood search itself, which is essentially the same a performing a standard local search. You begin by creating the large neighborhood.

Add the following code after the comment // Create the LNS neighborhood

      IloNHood nhood = SegmentLNSNHood(env, scene);

This code creates the large neighborhood to be used in the search. This takes care of the first part of LNS: the definition of a fragment. The second part is the completion method. For this (and as is common in LNS), you will use the initial solution goal to complete the search. This goal will, however, be limited in search capacity so as to avoid long search times in fragments which may have no improving solutions. Experience has shown that this limitation is essential to LNS, although the best limit can vary by problem and quality of the heuristic used in the completion goal (good heuristics are likely to require less search in the completion goal than poorer ones).

Add the following code after the comment

// Create the LNS completion goal

      IloGoal complete = IloLimitSearch(env, goal, IloFailLimit(env, 100));

As LNS can explore a much larger neighborhood than is typical of standard neighborhood searches, normally there is less reliance on a metaheuristic to guide the search, and as such greedy search is often employed. That is the technique that you will use here.

You will now create the local search move goal by inserting the following code after the comment // Create a greedy local search move goal

      IloGoal move = IloSingleMove(
        env, solution, nhood, IloImprove(env), complete
      );

Next, you perform the local search loop. This is just as for other greedy local searches, except that the stopping condition is altered. As the fragment is generated randomly, a failed solve is not an indication that the search should stop, as success depends on the particular randomized fragment generated. Thus, the search is stopped only after a certain number of tries are made without success. The total number of choice points used is totalled to give an indication of total search effort. The following code is provided for you:

      // Enter the local search loop
      IloInt choicePoints = 0;
      IloInt noMove = 0;
      IloInt movesTried = 0;
      while (noMove < 100) {
        movesTried++;
        if (solver.solve(move)) {
          noMove = 0;
          cout << movesTried << ": Cost = "
               << solver.getValue(idleCost) << endl;
        }
        else
          noMove++;
        choicePoints += solver.getNumberOfChoicePoints();
      }
      cout << "Total choice points = " << choicePoints << endl;