Consider a set of N offices whose centers are located at the 2D
coordinates 
. These are to
be occupied by N people whose interactions---coefficients of
angst---are denoted by 
. We seek
to minimize the function
which one can interpret as the total angst of the system.
Here, 
is the location of the 
person's
office, which must be one member of the set
For step (1) of CGO, we take
which can be considered as the angst felt by individual
person i. We take 
with 
(With 
values as defined below, the results
degrade significantly for 
above 2.0.) For this problem with
g thus defined, step (1) of CGO insures that only people who are
relatively ``unhappy'' with their office want to find a new office,
while those who are happy with their office don't want to move. For
step (2) of CGO, we permute those people who want new offices in a
random fashion: Choose a random number for each person who wants a new
office. Sort these random numbers, and shadow the sort operations on
their office assignments.
We consider problems with 20, 30, 40, 60, and 100 people. We use random
locations 
in the unit square, and we choose the 
randomly between -1 and +1 with 
and 
. We
attempt to find the minimum value of A using CGO and SA with the
rearrangement suggested by Lin and Kernighan[11]. For a given
number of people we start both methods from ten different starting
configurations. Both methods use the same annealing
schedule[12]. We try up to 100N arrangements at a given
temperature, stopping if 10N successful moves occur at a given
temperature. Then we lower the temperature by a factor of 
. At the
annealing step, the temperature is 
, where
is the initial temperature. For the runs reported here, we use
and 
; we anneal for 40 annealing steps, at which
temperature the configurations for both methods were frozen in.
We give results in table ii. CGO finds significantly lower values of A, both minimum and mean, than SA using the Lin--Kernighan rearrangement. The CGO runs take about two--thirds the computer time of the SA runs. We have annealed up to 100 times more slowly for some cases without altering the qualitative results of table ii.
The Lin--Kernighan rearrangement works exceptionally well for the traveling salesperson problem (TSP), but appears to have difficulties for the OAP. For the TSP the only relevant distances are those between a city and its neighbors, while in the OAP a person must consider all of the other people, not just neighbors. Perhaps, the Lin--Kernighan rearrangement is optimal for the TSP because it allows consideration of changes in distances to neighbors at the endpoints of a segment while leaving distances for other cities unaffected. But for the OAP changes in angst for people at the endpoints of the reversed or transported segment cannot be considered independently of the changes in angst for other people. CGO provides an effective method for moving unhappy people, while leaving the happy ones where they are.