Class IloLargeNHoodI

This class is a special sub-class of IloNHoodI which is designed to ease the writing of Large Neighborhood Search methods (see the IBM ILOG Solver User's Manual). Large Neighborhood Search is a local search technique which relies on constraint programming to explore a neighborhood which is defined by allowing a subset of the decision variables to change their value from that taken in the current solution.

Traditional Solver goals are used to perform the exploration of the neighborhood, but the IloNHoodI class is used to define exactly what variables may change their value. This variable subset is usually referred to as the solution fragment. Technically, the way in which this fragment is created is to return a solution delta (IloNHoodI::define) from IloNHoodI::define which includes all the variables of the fragment, but with a non-restorable status (see IloSolution::setRestorable). This will induce the Solver's local search to produce a neighbor which has all the variables in the fragment in their uninstantiated state, their domains reduced only by the propagation of problem constraints. That is, it is as if the variables mentioned in the delta had their current assignments relaxed. At this point a completion goal can explore all (or some) combinations of values for these variables, in an attempt to look for a better solution.

This class makes it possible to define deltas as described above without worrying about restore status and so on. One of the easiest ways to subclass this class is to use the macro ILODEFINELNSFRAGMENT0 (or one of its variants) which is ideal for most uses. Direct subclassing is seldom necessary, except for more advanced uses. Whether you use ILODEFINELNSFRAGMENT0, or directly subclass IloLargeNHoodI, the only thing you really need to worry about is that you call the IloLargeNHoodI::addToFragment member function for each variable you wish to be able to change its value.

You can operate this class in essentially two modes. The first is the simplest and is used by ILODEFINELNSFRAGMENT0. This mode supposes that the neighborhood has only one neighbor (which might be termed a meta-neighbor as it creates the possibility to move to a large number of distinct assignments) and the solution fragment is defined by the member function IloLargeNHoodI::defineFragment. Diversity of search is ensured by generating the fragment in a randomized way. In this case, IloLargeNHoodI::defineFragment is the only function that you need define in the subclass.

In the second mode, the neighborhood can have an arbitrary number of neighbors. Here, diversity is assured via the number of neighbors (as for traditional neighborhoods), and so randomization is not essential (but also not forbidden). In this second case, two member functions need to be redefined: IloLargeNHoodI::getSize, which delivers the number of neighbors, and IloLargeNHoodI::defineFragmentAtIndex which defines the fragment for a particular index given. As an example of this second kind of neighborhood, consider fragments defined over an array of variables x of size n. If there is some interest in relaxing a contiguous portion of the variables, you might consider as fragment i the variables of indices i-k to i+k (ignoring boundary conditions for now) where k is a non-negative integer.

This constructor creates an instance of a neighborhood to be used with Large Neighborhood Search on an environment, using env as an allocation environment. The optional name name becomes the name of the newly created neighborhood.

This member function should be called from either IloLargeNHoodI::defineFragment or IloLargeNHoodI::defineFragmentAtIndex (depending on which one is overloaded) to add a variable to the fragment currently being defined. You should pass as solver the instance of the Solver received in IloLargeNHoodI::defineFragment or IloLargeNHoodI::defineFragmentAtIndex. var is the variable to add to the fragment. If var is already in the fragment, then an exception (an instance of IloException) is raised. The member function IloLargeNHoodI::isInFragment can be used to determine if a variable is already in the fragment.

Normally, you need not overload this member function. It performs some setup tasks, calls IloLargeNHoodI::defineFragmentAtIndex, and afterwards builds the solution delta from a record of the calls that were made to IloLargeNHoodI::addToFragment. It is strongly recommended that you do not overload this function. If overloading is necessary, you must call IloLargeNHoodI::define(solver, index) and return the defined solution delta.

When you wish to create a large neighborhood which will use a randomized procedure to generate diverse fragments, this is the member function you should overload. In this member function, you make a call to IloLargeNHoodI::addToFragment for each variable you wish to add to the fragment. The default behavior of this function is to raise an exception (an instance of IloException) indicating that a fragment-defining function must be overloaded.

When you wish to create a large neighborhood which will create a distinct set of fragments, this is the member function (together with IloLargeNHoodI::getSize) that you should overload. The default behavior is to call IloLargeNHoodI::defineFragment, ignoring the index index.

This member function returns the current solution from which fragments are to be defined. This solution was passed to the IloLargeNHoodI::start function to begin looking for neighbors.

This member function should be overloaded if you wish to define a Large Neighborhood Search with more than a single meta-neighbor. This function should return the number of meta-neighbors (ways of defining a fragment). When this function is overloaded, you should also overload the IloLargeNHoodI::defineFragmentAtIndex to return the correct fragment for any given index.

This member function returns IloTrue if and only if the variable var is in the fragment. Otherwise, it returns IloFalse. The parameter solver is the instance of IloSolver driving the neighborhood.

Normally, you need not overload this member function. It performs some housekeeping tasks, and keeps solution locally so that you can access it via IloLargeNHoodI::getCurrentSolution. If you do need to overload this function, ensure that you call IloLargeNHoodI::start(solver, solution) before any other code in your function.