This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ohlmann, J. W. Articles by Henderson, S. G. Search for Related Content

Convergence in Probability of Compressed Annealing

Department of Management Sciences, University of Iowa, 108 John Pappajohn Business Building, Iowa City, Iowa 52242-1000
Department of Industrial and Operations Engineering, University of Michigan, 1205 Beal Avenue, Ann Arbor, Michigan 48109-2117
School of Operations Research and Industrial Engineering, Cornell University, 230 Rhodes Hall, Ithaca, New York 14853
jeffrey-ohlmann{at}uiowa.edu
jbean{at}umich.edu
sgh9{at}cornell.edu

We consider combinatorial optimization problems for which the formation of a neighborhood structure of feasible solutions is impeded by a set of constraints. Neighborhoods are recovered by relaxing the complicating constraints into the objective function within a penalty term. We examine a heuristic called compressed annealing that integrates a variable penalty multiplier approach within the framework of simulated annealing. We refer to the value of the penalty multiplier as "pressure." We analyze the behavior of compressed annealing by exploring the interaction between temperature (which controls the ability of compressed annealing to climb hills) and pressure (which controls the height of the hills). We develop a necessary and sufficient condition on the joint cooling and compression schedules for compressed annealing to converge in probability to the set of global minima. Our work generalizes the results of Hajek (1988) in the sense that when there are no relaxed constraints, our results reduce to his.

Key Words: simulated annealing; penalty methods; constrained combinatorial optimization
History: Received: March 16, 2003; revision received: November 16, 2003;

This article has been cited by other articles:

				J. W. Ohlmann and B. W. Thomas A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows INFORMS Journal on Computing, January 1, 2007; 19(1): 80 - 90. [Abstract] [PDF]