A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

An algorithm for finding hamilton cycles in random directed graphs

We describe a polynomial (O(n^1.5)) time algorithm DHAM for finding hamilton cycles in digraphs. For digraphs chosen uniformly at random from the set of digraphs with vertex set {1, 2, …, n} and m = m(n) edges the limiting probability (as n → ∞) that DHAM finds a hamilton cycle equals the limiting probability that the digraph is hamiltonian. Some applications to random “travelling salesman problems” are discussed.     

On the addressing problem for directed graphs

The “distance” from vertexu to vertexv in a strongly connected digraph is the number of arcs in a shortest directed path fromu tov. The addressing problem, first formulated in the undirected case by Graham and Pollak, entails the assignment of a string of symbols to each vertex in such a way that the distances between vertices are equal to modified Hamming distances between corresponding strings. A scheme for addressing digraphs is proposed, and the minimum address length is studied both in general and in certain special cases. The problem has some interesting reformulations in terms of matrix factorization and extremal set theory. Supported by NSF grant MCS 84-02054.     

A recognition algorithm for the intersection graphs of directed paths in directed trees

Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of directed paths in a directed tree is called a directed path graph. In this paper we present an efficient algorithm which constructs to a given graph a representation by a family of directed paths on a directed tree, if one exists. Also, we prove that a graph is a proper directed path graph if and only if it is a directed path graph.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

A simulated annealing heuristic for the team orienteering problem with time windows

This paper presents a simulated annealing based heuristic approach for the team orienteering problem with time windows (TOPTW). Given a set of known locations, each with a score, a service time, and a time window, the TOPTW finds a set of vehicle tours that maximizes the total collected scores. Each tour is limited in length and a visit to a location must start within the location’s service time window. The proposed heuristic is applied to benchmark instances. Computational results indicate that the proposed heuristic is competitive with other solution approaches in the literature.     

A simulated annealing heuristic for the one-dimensional cutting stock problem

This paper presents a new simulated annealing approach to the solution of an integer linear programming formulation of the one-dimensional cutting stock problem. Design and implementation issues are discussed - including a thorough statistical analysis of the effects of various parameters on the efficiency and accuracy of solutions. The performance of the new algorithm is compared to that obtained using an existing simulated annealing based methodology, and results presented herein indicate that the new approach consistently generates more efficient solutions with respect to objective value and execution time.     

A branch and bound algorithm for the acyclic subgraph problem

A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.     

A partitioning algorithm for the multicommodity network flow problem

A partitioning algorithm for solving the general minimum cost multicommodity flow problem for directed graphs is presented in the framework of a network flow method and the dual simplex method. A working basis which is considerably smaller than the number of capacitated arcs in the given network is employed and a set of simple secondary constraints is periodically examined. Some computational aspects and preliminary experimental results are discussed.     

Estimating the convergence of a simulated annealing algorithm for the problem of constructing multiprocessor schedules

An algorithm for constructing a computational system with the minimum number of processors while observing restrictions on system reliability and program execution time is considered. The problem is formulated mathematically, and an algorithm based on simulated annealing is proposed. Asymptotic convergence of the algorithm is formally proved.     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

A simulated annealing approach for the one-machine mean tardiness scheduling problem

In this paper we propose a simulated annealing approach for solving the single machine mean tardiness scheduling problem. The results of a simulation experiment indicate that the proposed method provides much better solutions than two heuristics that gave good results in previous studies. More importantly, the solutions obtained are within less than 1% of optimal solutions.     

Sandpile groups and the coeulerian property for random directed graphs

We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.     

A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks

This paper presents a mathematical model and simulated annealing based solution approach for finding optimal location updates and paging area configuration for mobile communication networks. We use a two-layered zone-based location registration and paging scheme in which the costs of location updates and paging signaling traffic are reduced by introducing a two-step paging process. The location updates and paging procedures in a two-layered scheme are first described, and an approximation of the measure required for calculating the paging-related signaling volume is provided based on assumptions of cell shapes and mobile stations’ movement patterns. A simulated annealing (SA)-based solution method is devised along with a greedy heuristic, and computational experiments are conducted to illustrate the superiority of the proposed SA-based method over other solution methods.     

An approach for the Steiner problem in directed graphs

We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNP_q, FINEP, CAPES and IBM do Brasil.     

Variants of simulated annealing for the examination timetabling problem

This paper is concerned with the use of simulated annealing in the solution of the multi-objective examination timetabling problem. The solution method proposed optimizes groups of objectives in different phases. Some decisions from earlier phases may be altered later as long as the solution quality with respect to earlier phases does not deteriorate. However, such limitations may disconnect the solution space, thereby causing optimal or near-optimal solutions to be missed. Three variants of our basic simulated annealing implementation which are designed to overcome this problem are proposed and compared using real university data as well as artificial data sets. The underlying principles and conclusions stemming from the use of this method are generally applicable to many other multi-objective type problems.     

A morph-based simulated annealing heuristic for a modified bin-packing problem

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.