IBM ILOG Solver User's Manual > Local Search > Basic Local Search > What is local search? > A simple local search procedure

A simple local search procedure

 INDEX Gray bullet PREVIOUS NEXT

The combination of solutions and goals offers a simple way of implementing local search procedures. The basic process is to change the solution and then test it against the problem constraints. The algorithm is as follows:

  1. Start with an initial solution s.
  2. Store the cost of s as currCost.
  3. Make a change to s.
  4. If s violates constraints or has cost >= currCost, revert the change.
  5. Go to step 2.

In this way, we only move to legal improving solutions. We reject solutions that do not improve the cost or that violate problem constraints. This is known as a greedy improvement algorithm, as it only makes changes to the solution that improve the cost.

In what follows, we will apply this technique to a modified version of the map coloring presented in Chapter 5, Using Objectives: Map Coloring with Minimum Colors.

© Copyright IBM Corp. 1987, 2009. Legal terms. PREVIOUS NEXT