Thesis (doctoral)--Rheinischen-Friedrich-Wilhelms-Universität. / "August 1999." Includes bibliographical references (p. 106-109) and index.

Thesis (Ph.D.)--McMaster University, 2004. / Advisor: Rajat Bhaduri. Includes bibliographical references ( p. 162-168). Also available online.

Thesis (M. Sc.)--University of Canterbury, 2006. / Typescript (photocopy). Includes bibliographical references (p. 57-59). Also available via the World Wide Web.

Ph.D.

Simulated Annealing is a general purpose combinatorial optimization technique which has been applied to many problems in VLSI design. In essence, simulated annealing is Monte Carlo iterative improvement with the ability to conditionally accept uphill moves. The notion of a cooling schedule is common to all simulated annealing implementations. A cooling schedule can be thought of as simulated annealing's control mechanisms. Experiential work has been done on estimating the cost of an optimal solution to some combinatorial optimization problem instances. Such an estimate can be used to determine termination criteria for general purpose optimization techniques such as iterative improvement or simulated annealing. We have extended this idea and designed a complete simulated annealing general cooling schedule based on the cost of an optimal solution to a problem instance. We call the resultant schedule an extended goal-directed general cooling schedule. One of the major problems with simulated annealing is its long computation times. This problem can be addressed by first using a fast heuristic to find a good initial configuration and then applying simulated annealing. This approach is called Simulated Sintering. To exploit the potential of simulated sintering one needs an appropriate general cooling schedule. The extended goal-directed cooling schedule is equally applicable to simulated annealing and simulated sintering. To date, no one cooling schedule has proven suitable for all optimization problem instances. In our view, no such cooling schedule exits. Consequently, we have attempted to identify the type of problem best suited to optimization by simulated annealing and simulated sintering using the extended goal-directed schedule. We have applied the extended goal-directed schedule to standard-cell placement and floorplanning problems using both simulated annealing and simulated sintering. Within this context, we have compared the performance of the extended goal-directed schedule to other published schedules. Our results indicate that in terms of layout quality, the extended goal-directed schedule performs as well or better than the other schedules. In this dissertation, we have developed a new general cooling schedule. Our evaluation of the extended goal-directed schedule suggests that it is a useful research contribution in the area of simulated annealing algorithms. / Graduate

Les problèmes d’optimisation combinatoire sont d’un grand intérêt à la fois pour le monde scientifique et le monde industriel. La communauté scientifique a oeuvré pour la simplification de certains problèmes issus du monde industriel vers des modèles d’optimisation combinatoire. Parmi ces problèmes, on peut trouver des problèmes appartenant à la famille du problème du sac à dos (knapsack). Dans cette thèse, nous considérons une variante du problème du sac à dos : le problème du sac à dos avec des contraintes disjonctives (Knapsack with Disjunctive Constraints). En raison de la difficulté de cette problématique, nous nous sommes intéressés au développement de méthodes heuristiques produisant des solutions de bonne qualité en un temps de calcul modéré. Nos travaux de recherche s’appuient sur le principe de la recherche par voisinage. Bien que cette façon de faire nous conduise vers des solutions approchées,leur utilisation ainsi que les résultats que nous avons obtenus restent intéressants tout en gardant un temps d’exécution raisonnable. Afin de résoudre des instances de grande taille pour la problématique étudiée, nous avons proposé des méthodes séquentielles et parallèles. Ces deux techniques de résolution sont basées sur la recherche par voisinage. Dans un premier temps, une première méthode de recherche par voisinage aléatoire a été proposée. Elle s’appuie sur la combinaison de deux procédures : une première procédure qui cherche à construire une série de solutions partielles et une deuxième procédure qui complète chacune des solutions partielles courantes par une exploration de son voisinage. Ensuite, une deuxième méthode adaptative a été mise en place. Elle s’appuie sur un système d’optimisation par colonie de fourmis pour simuler une recherche guidée et une procédure de descente pour explorer au mieux les solutions produites au cours du processus de recherche. Finalement, une troisième méthode a été élaborée dans le but de faire évoluer la performance des méthodes de recherche par voisinage. Dans cette partie de nos travaux de recherche, nous avons proposé une recherche par voisinage aléatoire parallèle. Nous nous appuyés sur l’exploration simultanée de différents (sous) espaces de recherche par différents processeurs, où chaque processeur adopte sa propre stratégie aléatoire pour construire ses propres voisinages en fonction de ses informations internes récoltées / Combinatorial optimization problems are of high interest both for the scientific world and for the industrial world. The research community has simplified many practical situations as combinatorial optimization problems. Among these problems, we can find some problems belonging to the knapsack family. This thesis considers a particular problem belonging to the knapsack family, known as the disjunctively constrained knapsack problem. Because of the difficulty of this problem, we are searching for approximate solution techniques with fast solution times for its large scale instances. A promising way to solve the disjunctively constrained knapsack problem is to consider some techniques based upon the principle of neighborhood search. Although such techniques produce approximate solution methods, they allow us to present fast algorithms that yield interesting solutions within a short average running time. In order to tackle large scale instances of the disjunctively constrained knapsack problem, we present sequential and parallel algorithms based upon neighborhood search techniques. The first algorithm can be viewed as a random neighborhood search method. This algorithm uses a combination of neighborhood search techniques in order to randomly explore a series of sub-solution spaces, where each subspace is characterized by a neighborhood of a local optimum. The second algorithm is an adaptive neighborhood search that guides the search process in the feasible solution space towards high quality solutions. This algorithm uses an ant colony optimization system to simulate the guided search. The third andlast algorithm is a parallel random neighborhood search method which exploits the parallelism for exploring simultaneously different sub-solution spaces by several processors. Each processor adopts its own random strategy to yield its own neighborhoods according to its internal information

No description available.

Genetic algorithms are stochastic search techniques based on the mechanics of natural selection and natural genetics. Genetic algorithms differ from traditional analytical methods by using genetic operators and historic cumulative information to prune the search space and generate plausible solutions. Recent research has shown that genetic algorithms have a large range and growing number of applications. The research presented in this thesis is that of using genetic algorithms to solve some typical combinatorial optimization problems, namely the Clique, Vertex Cover and Max Cut problems. All of these are NP-Complete problems. The empirical results show that genetic algorithms can provide efficient search heuristics for solving these combinatorial optimization problems. Genetic algorithms are inherently parallel. The Connection Machine system makes parallel implementation of these inherently parallel algorithms possible. Both sequential genetic algorithms and parallel genetic algorithms for Clique, Vertex Cover and Max Cut problems have been developed and implemented on the SUN4 and the Connection Machine systems respectively.

No description available.

An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes. / Includes bibliography. / Dissertation (PhD)--Florida Atlantic University, 2021. / FAU Electronic Theses and Dissertations Collection