The main idea behind Large Neighborhood Search is to focus the search on a sub-part of the decision variables of the problem. In this approach, we start from a known solution (current solution) and try to improve it by restoring (freezing) the values subset of some decision variables stored in this solution, while leaving other decision variables free. A goal is then used to try fix these remaining decision variables.

The set of decision variables is partitioned into two sets: the set of selected decision variables, and the other variables. Different restore policies are then applied, depending if the variable belongs or not to the set of selected decision variables.

To define the set of selected decision variables, use the pure virtual member function defineSelected of the class IloLargeNHoodI. Its signature is:

IloSolution IloLargeNHoodI::defineSelected(IloSolver solver, IloInt index)

The instance of class IloSolution returned must contain the set of selected decision variables corresponding to the neighbor with index index.

At first glance, a large neighborhood and a neighborhood look very similar. But there are also some differences:

• In a local search approach, the neighborhoods are enumerated explicitly (method define). The size of the neighborhood is the number of neighbors. A goal may be used to validate the neighbor: to check for an instance where all the constraints are fulfilled.
• In a large neighborhood approach, the size of the neighborhood is the number of sub-problems to solve. Each sub-problem may contain a potentially a large number of neighbors, and thus is a combinatorial problem itself. To exhibit a neighbor a search algorithm must be used.

Suppose there is a scheduling problem made of three activities requiring a unary resource. Further, we have found a first solution and wish to iteratively select an activity and try to relocate it on the resource. In a local search approach, the size of the neighborhood is nine: each activity can be either first, last or in the middle on the resource. A sub-goal may be used to ensure that all other constraints are fulfilled (side constraints). In a large neighborhood search approach, the number of sub-problems to solve is the number of activities (three in this case). For each sub-problem, we can use, for instance, the goal IloRankForward to find a neighbor.

Large neighborhoods dedicated to scheduling problems derive from the class IloSchedulerLargeNHoodI.

Two predefined neighborhoods dedicated to scheduling problems are available:

• IloRelocateActivityNHood which iteratively selects an activity and tries to reschedule it somewhere else.
• IloTimeWindowNHood which iteratively selects a time window and tries to reschedule the activities within the time window.

The class IloSchedulerLargeNHoodI provides specialization of functionalities available in class IloLargeNHoodI for activities and resource constraints. For instance, in class IloLargeNHood, there is a member function isSelected used to check if an extractable is selected or not:

IloBool isSelected(IloExtractable extr) const;

A similar member function exists on class IloLargeNHood to check if activities and resource constraints are selected:

IloBool isSelected(IloActivity activity) const;

IloBool isSelected(IloResourceConstraint rc) const;

In addition to the above functionalities, the main difference between class IloSchedulerLargeNHoodI and class IloLargeNHoodI is that class IloSchedulerLargeNHoodI overloads the method finalizeDelta. To ease the definition of neighborhoods dedicated to scheduling problems, this method removes from any resource constraint that is not selected the next, the previous, the direct successors and the direct predecessors, in case these are selected. These are then replaced by new appropriate direct predecessors and direct successors.

As an example, suppose a set of activities are scheduled on a unary resource, and a time window neighborhood is applied. In the following equation, R is the resource, [Ai] represents an activity and | represents the time window boundary.

R: [A0][A1]..[Ai-1] | A[i]..[Aj] | [Aj+1]..[Ak]

Here, the time window contains all activities from Ai to Aj. In the current solution Ai is the next (and also the direct successor) of Ai-1. Similarly in the current solution, activity Aj is the previous (and also the direct predecessors) of activity Aj+1. Both the next of Ai-1, the successor of Ai-1, the previous of Aj+1 and the direct predecessors of Aj+1 are removed. Also, Aj+1 is set as the successor of Ai-1, and Ai-1 is set as the predecessor of Aj+1.

There are two ways to extend the library with new large neighborhoods:

• by combining existing large neighborhoods.
• by deriving from class IloLargeNHoodI.

   IloSchedulerLargeNHood n1 = IloRelocateActivityNHood(env);
   IloSchedulerLargeNHood n2 = IloRelocateActivityNHood(env);
   IloLargeNHood nhood = IloUnionNHood(env, n1, n2);

  IloSchedulerLargeNHood n1 = IloRelocateActivityNHood(env);
  IloSchedulerLargeNHood n2 = IloTimeWindowNHood(env, 20, 10);
  IloLargeNHood nhood = IloIntersectNHood(env, n1, n2);

      IloSolution defineSelected(IloSolver solver, IloInt index);
      void start(IloSolver solver, IloSolution);
      IlcInt getSize(IloSolver solver, IloInt index);

      void defineRestoreInfo(IloSolver solver, IloSolution delta);
      void finalizeDelta(IloSolver solver, IloSolution delta);