Map-coloring problem. The coloring problem deals with determining the least number of colors for painting the regions of a map such that no two adjacent regions will have the same color. Figure 10.7

(a) provides an example of a 6-region map. The problem can be modeled as a network in which the nodes represent the regions as shown in Figure 10.7(b). An arc between two nodes signifies that the corresponding two regions are adjacent (share a common border). The map-coloring problem can represent other practical situations, as Problem 10-22 demonstrates.

An SA heuristic can be applied to the coloring problem. The starting solution, x0, can be determined in one of two ways:
1. Assign a unique color to each node of the network. Thus, x0 = 11, 2,

c, 62 for the network in Figure 10.7(b), 2. Use a greedy algorithm that starts by assigning color 1 to node 1. Next, given that nodes 1, 2,

c, and i - 1 use the colors 1, 2,

c, and

c, c … i - 1, assign the smallest color number in the set 11, 2,

c, c2 to node i without creating bad arcs (those whose two end nodes use the same color). If none can be found, apply a new color c + 1. For the network in Figure 10.7(b), the successive steps for constructing x0 are x0 1 = 112 x0 2 = 11, 22 x0 3 = 11, 2, 32 x0 4 = 11, 2, 3, 12 x0 5 = 11, 2, 3, 1, 42 x0 = x0 6 = 11, 2, 3, 1, 4, 22 The greedy algorithm uses 4 color classes, C1 = 11, 12, C2 = 12, 22, C3 = 132, C4 = 142, that apply to nodes 1 and 4, nodes 2 and 6, node 3, and node 5, respectively.
A neighborhood solution, xi+1, is determined by changing the color of a random node in xi to a random color in the same set. For example, given x0 = 11, 2, 3, 1, 4, 22 and its associated color set c0 = 11, 2, 3, 42, random selections of color 1 from c0 and node (position) 5 from x0 give x1 = 11, 2, 3, 1, 1, 22 The new color classes of x1 are C1 = 11, 1, 12, C2 = 12, 22, and C3 = 132 corresponding to nodes (1, 4, 5), (2, 6), and (3), respectively. To generate x2 from x1, randomly select a color from c1 = 11, 2, 32 to replace the color of a randomly selected node in x1. If necessary, repeat the random exchange until x2 becomes distinct from x1.
Next, we develop a measure of performance for solution. A simple measure calls for the minimization of the number of bad arcs (those whose two end nodes bear the same color). A more sophisticated measure can be developed in the following manner: Solution x1 is better than x0 from the standpoint of reducing the number of color classes (i.e., uses less colors by increasing the size of at least one color class), but simultaneously increases the chance of creating bad arcs. Specifically, x0 of the greedy algorithm has no bad arcs, and x1 has one bad arc, 4–5. Thus, an empirical measure of performance that balances the two conflicting situations [increasing the sizes (cardinalities) of the color classes and, simultaneously, reducing the number of bad arcs] calls for maximizing f1x2 = a k j=1 1 Cj  22 - 2a k k=1 Cj . Aj 
where k = Number of color classes Aj = Set of bad arcs associated with color class j

[The notation  S  represents the number of elements (cardinality) of the set S.] In terms of x0 and x1 of the greedy algorithm, we have f1x02 = 122 + 22 + 12 + 122 - 212 * 0 + 2 * 0 + 1 * 0 + 1 * 02 = 10 f1x12 = 132 + 22 + 122 - 213 * 1 + 1 * 0 + 2 * 02 = 8 The two values show that x1 is worse than x0 [recall that we are maximizing f(x)]. Hence, per SA heuristic, we accept x1 if R 6 e-f1x02 -f1x12/T.
Note that the generation of xi+1 from xi may result in an infeasible color assignment.
(This point does not arise in Examples 10.3-3 and 10.3-4 because of the nature of the associated problems.) In these cases, an infeasible move can be accepted using the probability condition of SA, but the best solution is updated only if a better feasible solution is encountered.
Apply three additional SA iterations to the coloring network in Figure 10.7(b)
using the greedy algorithm to determine the starting solution and the measure of performance f(x), as explained above.