Efficient multi-swarm PSO algorithms for dynamic environments

Particle swarm optimization has been successfully applied in many research and application areas because of its effectiveness and easy implementation. In this work we extend one of its variants to address multi-modal dynamic optimization problems, the multi-swarm PSO (mPSO) proposed by Blackwell and Branke. The aim of our proposal is to increase the efficiency of this algorithm. To this end, we propose techniques operating at swarm level: one of which divides each swarm into two groups depending on the quality of the particles for facing the loss of diversity, and the other control the number of active swarms during the run using a fuzzy rule. A detailed experimental analysis shows the robustness of our proposal.     

Efficient domain partitioning algorithms for global optimization of rational and Lipschitz continuous functions

A domain partitioning algorithm for minimizing or maximizing a Lipschitz continuous function is enhanced to yield two new, more efficient algorithms. The use of interval arithmetic in the case of rational functions and the estimates of Lipschitz constants valid in subsets of the domain in the case of others and the addition of local optimization have resulted in an algorithm which, in tests on standard functions, performs well.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Implementation of parallel branch-and-bound algorithms – experiences with the graph partitioning problem

Parallel processing is one of the essential concepts in the attempts to increase the computational power available for solving continuous and discrete optimization problems. In the case where an optimization algorithm is search-based, crucial issues of parallel distributed implementations are work-load distribution and granularity, i.e. how to distribute the search space among processors and how to control the amount of processing between interprocessor communication. The present paper compares distributed implementations of two branch-and-bound algorithms for the graph partitioning problem: Given an undirected graph with an even number of edges and weights assigned to each edge, partition the vertices into two subsets of equal size such that the sum of the costs of edges connecting vertices in different subsets is as small as possible. The problem is known to be NP-complete. The two branch-and-bound methods compared differ in design strategy: One is based on time-consuming bound calculations leading to tight bounds and thus a narrow search tree with few nodes, whereas the other employs an easy bound calculation scheme leading to a larger search tree. Both have been implemented on an iPSC-hypercube with 32 processors. We investigate the influence of the design strategy on the performance of the algorithms.     

Efficient sampling in approximate dynamic programming algorithms

Dynamic Programming (DP) is known to be a standard optimization tool for solving Stochastic Optimal Control (SOC) problems, either over a finite or an infinite horizon of stages. Under very general assumptions, commonly employed numerical algorithms are based on approximations of the cost-to-go functions, by means of suitable parametric models built from a set of sampling points in the d-dimensional state space. Here the problem of sample complexity, i.e., how “fast” the number of points must grow with the input dimension in order to have an accurate estimate of the cost-to-go functions in typical DP approaches such as value iteration and policy iteration, is discussed. It is shown that a choice of the sampling based on low-discrepancy sequences, commonly used for efficient numerical integration, permits to achieve, under suitable hypotheses, an almost linear sample complexity, thus contributing to mitigate the curse of dimensionality of the approximate DP procedure.     

Path optimization for graph partitioning problems

This paper presents a new heuristic for graph partitioning called Path Optimization (PO), and the results of an extensive set of empirical comparisons of the new algorithm with two very well-known algorithms for partitioning: the Kernighan-Lin algorithm and simulated annealing. Our experiments are described in detail, and the results are presented in such a way as to reveal performance trends based on several variables. Sufficient trials are run to obtain 99% confidence intervals small enough to lead to a statistical ranking of the implementations for various circumstances. The results for geometric graphs, which have become a frequently used benchmark in the evaluation of partitioning algorithms, show that PO holds an advantage over the others.

In addition to the main test suite described above, comparisons of PO to more recent partitioning approaches are also given. We present the results of comparisons of PO with a parallelized implementation of Goemans' and Williamson's 0.878 approximation algorithm, a flow-based heuristic due to Lang and Rao, and the multilevel algorithm of Hendrickson and Leland.     

An exact algorithm for graph partitioning

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.     

Efficient algorithms to compute all articulation points of a permutation graph

Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.     

Genetic and hybrid algorithms for graph coloring

Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, we examine the performance of several hybrid schemes that can obtain solutions of excellent quality. For some graphs, we illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.     

Approximation algorithms for graph approximation problems

Several versions of the graph approximation problem are under study. Approximation algorithms for these problems are proposed, and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX.     

Efficient algorithms for merging

Efficient algorithms are given to find the maximum lengthn of an ordered list in which 4 elements can be merged using exactlyk comparisons. A top down algorithm for the (2,n) merge problem is discussed and is shown to obtain the optimal merge length first reported by Hwang and Lin. Our algorithms combine this top down approach and strong heuristics, some of which derived from Hwang's optimal algorithm for the (3,n) problem, and produce a lengthn which is close to the optimal lengthf ₄(k).     

Efficient solutions for weight-balanced partitioning problems

We prove polynomial-time solvability of a large class of clustering problems where a weighted set of items has to be partitioned into clusters with respect to some balancing constraints. The data points are weighted with respect to different features and the clusters adhere to given lower and upper bounds on the total weight of their points with respect to each of these features. Further the weight-contribution of a vector to a cluster can depend on the cluster it is assigned to. Our interest in these types of clustering problems is motivated by an application in land consolidation where the ability to perform this kind of balancing is crucial.Our framework maximizes an objective function that is convex in the summed-up utility of the items in each cluster. Despite hardness of convex maximization and many related problems, for fixed dimension and number of clusters, we are able to show that our clustering model is solvable in time polynomial in the number of items if the weight-balancing restrictions are defined using vectors from a fixed, finite domain. We conclude our discussion with a new, efficient model and algorithm for land consolidation.     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

An overview of graph covering and partitioning

While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.     

Separating plane algorithms for convex optimization

The equivalent formulation of a convex optimization problem is the computation of a value of a conjugate function at the origin. The latter can be achieved by approximation of the epigraph of the conjugate function around the origin and gradual refinement of the approximation. This yields a generic algorithm of convex optimization which transforms into some well-known techniques when certain strategies of approximation are employed. It also suggests new algorithmic approaches with promising computational experience and provides a uniform treatment of constrained and unconstrained optimization.     

On a programming language for graph algorithms

An algorithmic language, GRAAL, is defined, as an extension of ALGOL 60 (Revised), for describing and implementing graph algorithms of the type arising in applications. It is based on a set algebraic model of graph theory which defines the graph structure in terms of user specified morphisms between certain set algebraic structures over the node and arc set. Several examples of graph algorithms written in GRAAL are included.This work was in part supported by Grant GJ-1067 from the U.S. National Science Foundation and Grant NGL-21-002-008 from the U.S. National Aeronautics and Space Administration.     

Efficient algorithms for tree reconstruction

In this note, we show thatO(n logn) operations are sufficient to reconstruct an ordered binary tree given its inorder traversal and either its preorder or postorder traversal. An alternative linear representation allows reconstruction usingO(n) operations.     

An efficient memetic algorithm for the graph partitioning problem

We consider the component testing problem of a device that is designed to perform a mission consisting of a random sequence of phases with random durations. Testing is done at the component level to attain desired levels of mission reliability at minimum cost. The components fail exponentially where the failure rate depends on the phase of the mission. The reliability structure of the device involves a series connection of nonidentical components with different failure characteristics. The optimal component testing problem is formulated as a semi-infinite linear program. We present an algorithmic procedure to compute optimal test times based on the column generation technique, and illustrate it with numerical examples.