To exploit the possibilities of local optimization, you can take advantage of the Solver library.

In fact, you can, at some point, leave aside the backtracking mechanism and concentrate on local optimizations. Starting from a solution with a certain cost, Solver will improve that solution up to the point of getting a satisfactory solution.

This technique has the additional advantage of working remarkably well on very large instances of problems.

As a technique, it is extremely simple in principle. Solver uses generation and propagation to get an initial solution; this solution is then improved by local modifications. The problem constraints, of course, are used to guarantee that the iterations for improvements stay within the authentic solution space.