Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).     

On the use of some known methods forT-colorings of graphs

A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is a variant of the generalT-coloring problem related in the literature. We want to color the vertices of a graph in such a way that the two colors assigned to two adjacent verticesi andj differ by at least _ij , wheret _ij is a fixed coefficient associated to the edge [i, j]. The goal is to minimize the length of the spectrum of colors used. We present here the results produced by well-known heuristics (tabu search and simulated annealing) applied to the considered problem. The results are compared with optimal colorings obtained by a branch-and-bound algorithm.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

Simulated annealing algorithm for the robust spanning tree problem

This paper addresses the robust spanning tree problem with interval data, i.e. the case of classical minimum spanning tree problem when edge weights are not fixed but take their values from some intervals associated with edges. The problem consists of finding a spanning tree that minimizes so-called robust deviation, i.e. deviation from an optimal solution under the worst case realization of interval weights. As it was proven in Kouvelis and Yu (Robust Discrete Optimization and Its Applications, Kluwer Academic, Norwell, 1997), the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated annealing, in order to calculate an approximate solution for large scale instances efficiently. We describe theoretical aspects and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop a metaheuristic approach for solving the robust spanning tree problem.     

A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems

This paper approximately solves the high school timetabling problem using a simulated annealing based algorithm with a newly-designed neighborhood structure. In search for the best neighbor, the heuristic performs a sequence of swaps between pairs of time slots, instead of swapping two assignments as in a standard simulated annealing. The computational results show that the proposed heuristic, which is tested on two sets of benchmark instances, performs better than existing approaches.     

并行机问题的模拟退火调度算法研究

研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.     

A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling

In this study, a general framework is proposed that combines the distinctive features of three well-known approaches: the adaptive memory programming, the simulated annealing, and the tabu search methods. Four variants of a heuristic based on this framework are developed and presented. The performance of the proposed methods is evaluated and compared with a conventional simulated annealing approach using benchmark problems for job shop scheduling. The unique feature of the proposed framework is the use of two short-term memories. The first memory temporarily prevents further changes in the configuration of a provisional solution by maintaining the presence of good elements of such solutions. The purpose of the second memory is to keep track of good solutions found during an iteration, so that the best of these can be used as the starting point in a subsequent iteration. Our computational results for the job shop scheduling problem clearly indicate that the proposed methods significantly outperform the conventional simulated annealing.     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

Molecular conformation on the CM-5 by parallel two-level simulated annealing

In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.Also a researcher at the Army High Performance Computing Research Center, University of Minnesota, Minneapolis, MN 55415     

Parallelizing simulated annealing algorithms based on high-performance computer

We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance computers and applied them to a set of standard function optimization problems in order to test their performances. According to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely, parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great time cost if the random search space was considerably expanded. The most effective way we found in identifying the global optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success rate and solution quality.     

Combining simulated annealing with local search heuristics

We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities, in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.     

Simulated annealing for complex portfolio selection problems

This paper describes the application of a simulated annealing approach to the solution of a complex portfolio selection model. The model is a mixed integer quadratic programming problem which arises when Markowitz’ classical mean–variance model is enriched with additional realistic constraints. Exact optimization algorithms run into difficulties in this framework and this motivates the investigation of heuristic techniques. Computational experiments indicate that the approach is promising for this class of problems.     

基于蝙蝠退火算法的无等待流水线调度问题研究

无等待流水线调度问题(no-wait flow shop scheduling problem,NWFSP)是一类比较重要的复杂生产调度问题,并已经被证明是典型的NP问题.蝙蝠算法(Bat algorithm,BA)是一种较新颖的群体智能算法.本文针对蝙蝠算法在求解无等待流水线调度问题上的不足,提出一种蝙蝠退火算法,它通过采用ROV的编码方式以实现离散问题的连续编码,同时为了避免算法早熟现象引入了模拟退火算法.算法采用基于NEH的局部搜索规则,在很大程度上提高了算法的性能.利用标准Car问题和Rec问题算例进行仿真实验,结果表明了改进算法的可行性和有效性.     

Solving a Real World Assignment Problem with a Metaheuristic

This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem (GAP). The large-scale number of variables in the related 0-1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reductions of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.     

基于模拟退火算法的矩形优化排样问题的研究

考虑了一种矩形优化排样系统中遗传算法和模拟退火算法的结合算法.首先建立了该系统的通用数学模型.然后给出了求解该问题的遗传模拟退火算法.最后用VC++6.0模拟算例的结果表明该算法是一种行之有效的方法.     

A hybrid simulated annealing for solving an extended model of dynamic cellular manufacturing system

This paper develops a mixed-integer programming model to design the cellular manufacturing systems (CMSs) under dynamic environment. In dynamic environment, the product mix and part demand change under a multi-period planning horizon. Thus, the best designed cells for one period may not be efficient for subsequent periods and reconfiguration of cells is required. Reconfiguration may involve adding, removing or relocating machines; it may also involve a change in processing rout of part types from a period to another. The advantages of the proposed model are as follows: considering the batch inter/intra-cell material handling by assuming the sequence of operations, considering alternative process plans for part types, and considering machine replication. The main constraints are maximal cell size and machine time-capacity. The objective is to minimize the sum of the machine constant and variable costs, inter- and intra-cell material handling, and reconfiguration costs. An efficient hybrid meta-heuristic based on mean field annealing (MFA) and simulated annealing (SA) so-called MFA–SA is used to solve the proposed model. In this case, MFA technique is applied to generate a good initial solution for SA. The obtained results show that the quality of the solutions obtained by MFA–SA is better than classical SA, especially for large-sized problems.     

A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints

The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a variant of the classical vehicle routing problem in which customers are served by a heterogeneous fleet of vehicles. These vehicles have different capacities, fixed and variable operating costs, length and width in dimension, and two-dimensional loading constraints. The objective of this problem is to minimize transportation cost of designed routes, according to which vehicles are used, to satisfy the customer demand. In this study, we proposed a simulated annealing with heuristic local search (SA_HLS) to solve the problem and the search was then extended with a collection of packing heuristics to solve the loading constraints in 2L-HFVRP. To speed up the search process, a data structure was used to record the information related to loading feasibility. The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP). In addition, the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.     

Solving a dynamic cell formation problem using metaheuristics

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed by using some traditional metaheuristic methods such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Most of previous researches were done under the static condition. Due to the fact that CF is a NP-hard problem, then solving the model using classical optimization methods needs a long computational time. In this research, a nonlinear integer model of CF is first given and then solved by GA, SA and TS. Then, the results are compared with the optimal solution and the efficiency of the proposed algorithms is discussed.