Minimizing Talent Wait Cost Using LNS

This lesson introduces the concept of large neighborhood search (LNS). LNS is a search technique which is a hybrid of traditional neighborhood search techniques and constraint programming. The basic idea is simple: at each step of the local search method, a subset of the decision variables is chosen (invariably in a randomized fashion) and referred to as the fragment. All decision variables not in the fragment must keep their values as in the current solution. All variables in the fragment are free to take their values from their initial domains (subject to constraint propagation). A constraint programming goal is then used to complete the assignment by instantiating the variables in the fragment. This goal is usually subject to some acceptance conditions or constraints, for instance that any new assignment is better than the current one in the case of a greedy search. The completion goal is also normally limited by a fail limit to avoid the exponential run-times that can be seen using complete search. Regardless of whether a better solution was found during completion, the process is repeated from the selection of a new fragment. As in traditional local search procedures, a number of iterations or a time limit usually terminates the search.

LNS is a successful technique which can be applied to a range of problems. The crucial part is the selection of a fragment. One method is to select a fragment completely at random. While this can work in some cases, normally there is a better way to select a fragment that can be determined by some consideration of the problem. This example introduces you to the LNS framework provided in Solver IIM and addresses such key points as fragment generation at the end of the chapter.

Make a copy of the example file YourSolverHome/examples/src/tutorial/lstalent_partial.cpp and open this copy in your development environment. This file is a program that is only partially completed. You will fill in the blanks in each step in this section. At the end of the section, you will have completed the example and you can compile and run the program.