Theory and applications of compressed annealing.
Jeffrey W. Ohlmann · Deep Blue (University of Michigan) · 2003
Operations managers are often faced with large-scale decision-making problems that are difficult to solve to optimality. We analyze compressed annealing, a heuristic approach for solving large-scale combinatorial optimization problems. Compressed annealing is a variant of simulated annealing that integrates a variable penalty method with heuristic search to address optimization problems with relaxed constraints. The concept of pressure is introduced to parameterize the value of the penalty multiplier. We present a theoretical framework to study the behavior of compressed annealing. We provide necessary and sufficient conditions that ensure the metaheuristic's convergence in probability to the set of global optima. Guided by theoretical insight, we develop practical joint cooling and compression schedules. We employ compressed annealing on an asset replacement problem considering the issues of stochastic deterioration, budget limits, and time-variant costs due to technological change. We perform computational experiments on data sets constructed from information provided by trucking companies. Empirical results illustrate the effectiveness of compressed annealing; replacement plans obtained via compressed annealing outperform a trade cycle approach commonly implemented in the trucking industry. To test compressed annealing's robustness, we apply the algorithm to the traveling salesman problem with time windows (TSPTW). The variable penalty approach of compressed annealing allows a search considering tours infeasible with respect to the time windows. Compressed annealing obtains best-known results on numerous data sets from the literature.