Unforeseen Consequences of “Tabu” Choices

Fred W. Glover, Unforeseen Consequences of “Tabu” Choices—A Retrospective, INFORMS Journal on Computing, 2022, Volume 34, Issue 3, Pages 1306-1308.

This retrospective is written upon receiving The IJOC Test of Time Award for the papers “Tabu Search—Part 1 and —Part 2,” a delightful capstone to an unanticipated (and exceptionally fun) adventure.

Application-driven research: 

The year was 1970, and I had just joined the Business School at the University of Colorado, Boulder. A colleague who was instrumental in arranging this new position informed me of a combinatorial optimization problem the Bell System wanted to solve, with too many binary variables to be approachable by available methods. A procedure to obtain a local optimum was apparent, but Bell was casting about to discover a useful way to go farther.

The approach of the solution: 

Reflecting on this challenge brought back the memory of a psychology experiment I’d done a few years earlier as a doctoral student in an artificial intelligence (AI) class. (AI was enjoying a surge of popularity at the time, and its seesaw trajectory of dropping into the doldrums in the mid-1970s before dramatically recovering in the 1980s lay still in the future.) The purpose of the experiment was to discover how graduate students with varied backgrounds might go about finding good solutions to a combinatorial optimization problem I disguised as a word problem.

The outcome was surprising. Independent of their backgrounds, the students all followed a similar scheme in the way they generated a series of choices for probing various solution possibilities. There was a difference, however, between the procedures used by students who were more and less successful at finding the best solutions. The less successful students would either forget or discount the impact of choices made at an earlier stage and would effectively become “locked into” a set of decisions that proved less than desirable. The successful students initially made choices like those of their unsuccessful counterparts but more readily identified and modified previous choices that were relevant to change, ultimately finding their way to better solutions. 

Two features of this experiment struck me as particularly intriguing. First, it offered an alternative to the Freudian view that people become stuck in unproductive behavior primarily because of repressing earlier experiences. By contrast, the experiment suggested that access to better decisions can just as easily be lost by simply forgetting or discounting the relevance of earlier choices. Second, these students (who arguably were all decent problem solvers) proceeded by temporarily enforcing their choices and then gradually revising them over time. The students constructed their solution paths more flexibly than by generating branches in a tree, and the difference between more and less successful approaches lay in an ability to recover and change previous decisions that were influential. 

Keep improving even under rejection: 

This primitive form of TS worked surprisingly well, getting significantly better results for the Bell problems than the best previously discovered. However, my associates and I were caught off guard when the Bell System group dismissed these results as not possibly being as good as claimed. We were politely informed that Bell researchers were much better versed in ways to solve the problem than we were. The subtext was that academics should stick to academic pursuits and leave practical applications to those better qualified for dealing with them.

Although this response was disappointing, research interests that claimed a higher priority propelled me forward without much thought about the Bell rejection. Throughout this period, I was deeply involved in integer programming (IP) and network optimization, and I speculated that the approach devised for the Bell System application, which was a special instance of an IP problem, might be applicable to other integer programming problems. Drawing on ideas I’d been contemplating for IP heuristics using surrogate constraints, I devised supplementary strategies for handling more general applications. The resulting procedures included a forerunner of the TS path relinking strategy called scatter search, an intensification procedure based on a notion of strongly determined and consistent variables, and the first embodiment of the TS strategic oscillation approach. These elements were assembled in a short tutorial paper featuring the strategic oscillation approach, which was illustrated using separate tabus for alternating phases of oscillation, without using tabu terminology. Published in Decision Sciencesin 1977, the paper went largely unnoticed.