Journal article
Convergence in Probability of Compressed Annealing
Mathematics of operations research, Vol.29(4), pp.837-860
11/2004
DOI: 10.1287/moor.1040.0095
Abstract
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.
Details
- Title: Subtitle
- Convergence in Probability of Compressed Annealing
- Creators
- Jeffrey W. Ohlmann - University of IowaJames C. Bean - University of Michigan–Ann ArborShane G. Henderson - Cornell University
- Resource Type
- Journal article
- Publication Details
- Mathematics of operations research, Vol.29(4), pp.837-860
- DOI
- 10.1287/moor.1040.0095
- ISSN
- 0364-765X
- eISSN
- 1526-5471
- Language
- English
- Date published
- 11/2004
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380402702771
Metrics
10 Record Views