The Algorithm Design Manual Second Edition

k on the total defect level for each individual assembly. But what was the best

way to score a set of assemblies? We could just return the number of acceptable

complete assemblies as our score—an integer from 1 to b. Although this was indeed

what we wanted to optimize, it would not be sensitive to detect when we were

making partial progress towards a solution. Suppose one of our swaps succeeded in

bringing one of the nonfunctional assemblies much closer to the not-radio limit k.

That would be a better starting point for further progress than the original, and

should be favored.

My final cost function was as follows. I gave one point for every working assem-

bly, and a significantly smaller total for each nonworking assembly based on how

close it was to the threshold k. The score for a nonworking assembly decreased

exponentially based on how much it was over k. Thus the optimizer would seek

to maximize the number of working assemblies, and then try to drive another

assembly close to the limit.

I implemented this algorithm, and then ran the search on the test case they

provided. It was an instance taken directly from the factory floor. Not-radios turn

out to contain m = 8 important parts types. Some parts types are more expensive

than others, and so they have fewer available candidates to consider. The most

---

7 . 7

W A R S T O R Y : A N N E A L I N G A R R A Y S

263

suffix

prefix

AA

AG

GA

GG

AA

AAAA

AAAG

AAGA

AAGG

AG

AGAA

AGAG

AGGA

AGGG

GA

GAAG

GAAG

GAGA

GAGG

GG

GGAA

GGAG

GGGA

GGGG

Figure 7.12: A prefix-suffix array of all purine 4-mers

constrained parts type had only eight representatives, so there could be at most

eight possible assemblies from this given mix.

I watched as simulated annealing chugged and bubbled on the problem instance.

The number of completed assemblies instantly climbed (1, 2, 3, 4) before progress

started to slow a bit. Then came 5 and 6 in a hiccup, with a pause before assembly

7 came triumphantly together. But tried as it might, the program could not put

together eight not-radios before I lost interest in watching.

I called and tried to admit defeat, but they wouldn’t hear it. It turns out that

the best the factory had managed after extensive efforts was only six working not-

radios, so my result represented a significant improvement!