Consider the map coloring problem. In that problem, the map of Western Europe must be colored with only two colors. The constraints dictate that no two countries sharing a border can have the same color. However, in such a case, there is no solution. Therefore, the constraint on Luxembourg having a different color from its neighbors is relaxed, and a cost on its having the same color as a neighbor is added. In that example, the optimal assignment of colors is found using a complete search.

Here, as an introduction to using local search procedures, we replace the complete search for the minimum cost color assignment with a local search.

First of all, we list the definition of the model of the problem:

    IloModel model(env);
    
    IloIntVar Belgium(env, 0, 1), Denmark(env, 0, 1), 
              France(env, 0, 1), Germany(env, 0, 1), 
              Netherlands(env, 0, 1), Luxembourg(env, 0, 1);
    IloIntVarArray AllVars(env);
    AllVars.add(Belgium);
    AllVars.add(Denmark);
    AllVars.add(France);
    AllVars.add(Germany);
    AllVars.add(Netherlands);
    AllVars.add(Luxembourg);
    model.add(AllVars);
    model.add(France != Belgium); 
    model.add(France != Germany); 
    model.add(Belgium != Netherlands); 
    model.add(Germany != Netherlands); 
    model.add(Germany != Denmark); 
    IloIntVar quality(env, 0, 20000);
    model.add(quality == 257 * (France != Luxembourg)
                      + 9043 * (Luxembourg != Germany)
                      +  568 * (Luxembourg != Belgium));
    IloObjective obj = IloMaximize(env, quality);

At this point, if we were using a complete search technique, we would add the objective to the model, create the solver from the model, and use IloSolver::solve(IloGoal) to find the optimal solution. However, here we will use a local search technique which proceeds in two phases. In the first phase, we generate an initial solution, and in the second, we improve it using local search.