IBM ILOG Solver User's Manual > Local Search > Minimizing Talent Wait Cost Using LNS > Tips on using Large Neighborhood Search > The completion goal

The simplest way to use a completion goal in LNS is simply to use the initial solution goal as a completion goal. The idea here is that if the initial solution goal is to considered as a goal which is well adapted to providing good solutions to the problem as whole, then we can also suppose that it will produce good solutions to problem fragments.

One disadvantage of using the initial solution goal "as is" to complete the fragment is that if the fragment is large, the completion goal can take a long time to search the entire search space of the fragment. This exponential search time is what you would like to avoid in using a local search method. So, in practice any completion goal used in an LNS context is limited (normally by a fail limit imposed using IloFailLimit). This allows LNS to examine many more fragments in the same time frame, avoiding becoming bogged down in very long searches of fragments which have no improving solutions.

When you use pure tree search to find solutions to a constraint programming problem, normally you try to find a good heuristic for the problem, that is a variable and value selection rule which will tend to lead to better solutions. This is also true for the completion goal, but will come for free if you use the same goal to complete the fragment as you do to find the initial solution.

A good heuristic is also particularly important in fragment completion as the search goal will be limited (see above) and so will have much less explorative power that a complete goal. As such, it is useful if the search can find good solutions without making many mistakes i.e. a good heuristic is desirable. That also means that for better heuristics, you can probably make do with a lower fail limit in the completion goal, and conversely for a poor heuristic, the fail limit will need to be higher, and search time per iteration will increase.

If you don't have an idea of what a good heuristic may be, or it seems too difficult to come up with a good goal, one technique which can increase robustness of the completion goal is to add some randomization to the completion goal (see for example IloRandomPerturbation in the IBM ILOG Solver Reference Manual). This will distribute the assignments made more evenly between the available values, meaning that the completion goal will not produce fragment completions in the same vein each time, but will vary them.