Researcher profile

Gerald Paul

Gerald Paul contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Data Structures and Algorithms cond-mat.dis-nn cond-mat.other cond-mat.stat-mech Distributed, Parallel, and Cluster Computing math.CO Neural and Evolutionary Computing physics.comp-ph physics.gen-ph

Trust snapshot

Quick read

Trust 21 - Emerging

7works

0followers

9topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2012arXiv

A GPU implementation of the Simulated Annealing Heuristic for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems. An effective heuristic for obtaining approximate solutions to the QAP is simulated annealing (SA). Here we describe an SA implementation for the QAP which runs on a graphics processing unit (GPU). GPUs are composed of low cost commodity graphics chips which in combination provide a powerful platform for general purpose parallel computing. For SA runs with large numbers of iterations, we find performance 50-100 times better than that of a recent non-parallel but very efficient implementation of SA for the QAP

preprint2011arXiv

An efficient implementation of the simulated annealing heuristic for the quadratic assignment problem

The quadratic assignment problem (QAP) is one of the most difficult combinatorial optimization problems. One of the most powerful and commonly used heuristics to obtain approximations to the optimal solution of the QAP is simulated annealing (SA). We present an efficient implementation of the SA heuristic which performs more than 100 times faster then existing implementations for large problem sizes and a large number of SA iterations.

preprint2011arXiv

The Random Quadratic Assignment Problem

Optimal assignment of classes to classrooms \cite{dickey}, design of DNA microarrays \cite{carvalho}, cross species gene analysis \cite{kolar}, creation of hospital layouts cite{elshafei}, and assignment of components to locations on circuit boards \cite{steinberg} are a few of the many problems which have been formulated as a quadratic assignment problem (QAP). Originally formulated in 1957, the QAP is one of the most difficult of all combinatorial optimization problems. Here, we use statistical mechanical methods to study the asymptotic behavior of problems in which the entries of at least one of the two matrices that specify the problem are chosen from a random distribution $P$. Surprisingly, this case has not been studied before using statistical methods despite the fact that the QAP was first proposed over 50 years ago \cite{Koopmans}. We find simple forms for $C_{\rm min}$ and $C_{\rm max}$, the costs of the minimal and maximum solutions respectively. Notable features of our results are the symmetry of the results for $C_{\rm min}$ and $C_{\rm max}$ and the dependence on $P$ only through its mean and standard deviation, independent of the details of $P$. After the asymptotic cost is determined for a given QAP problem, one can straightforwardly calculate the asymptotic cost of a QAP problem specified with a different random distribution $P$.

preprint2010arXiv

An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems

We propose and develop an efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems. The traditional implementation of the heuristic applicable to all quadratic assignment problems is of O(N^2) complexity per iteration for problems of size N. Using multiple priority queues to determine the next best move instead of scanning all possible moves, and using adjacency lists to minimize the operations needed to determine the cost of moves, we reduce the asymptotic complexity per iteration to O(N log N ). For practical sized problems, the complexity is O(N).

preprint2010arXiv

Comparative Performance of Tabu Search and Simulated Annealing Heuristics for the Quadratic Assignment Problem

For almost two decades the question of whether tabu search (TS) or simulated annealing (SA) performs better for the quadratic assignment problem has been unresolved. To answer this question satisfactorily, we compare performance at various values of targeted solution quality, running each heuristic at its optimal number of iterations for each target. We find that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets.

preprint2009arXiv

Catastrophic cascade of failures in interdependent networks

Many systems, ranging from engineering to medical to societal, can only be properly characterized by multiple interdependent networks whose normal functioning depends on one another. Failure of a fraction of nodes in one network may lead to a failure in another network. This in turn may cause further malfunction of additional nodes in the first network and so on. Such a cascade of failures, triggered by a failure of a small faction of nodes in only one network, may lead to the complete fragmentation of all networks. We introduce a model and an analytical framework for studying interdependent networks. We obtain interesting and surprising results that should significantly effect the design of robust real-world networks. For two interdependent Erdos-Renyi (ER) networks, we find that the critical average degree below which both networks collapse is <k_c>=2.445, compared to <k_c>=1 for a single ER network. Furthermore, while for a single network a broader degree distribution of the network nodes results in higher robustness to random failure, for interdependent networks, the broader the distribution is, the more vulnerable the networks become to random failure.

preprint2006arXiv

A Complexity O(1) Priority Queue for Event Driven Molecular Dynamics Simulations

We propose and implement a priority queue suitable for use in event driven molecular dynamics simulations. All operations on the queue take on average O(1) time per collision. In comparison, previously studied queues for event driven molecular dynamics simulations require O(log $N$) time per collision for systems of $N$ particles.