Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems

In Balas and Niehaus (1996), we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm—selection, population replacement and mutation—and develop a steady-state genetic algorithm that performs better than its competitors on most problems.     

Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.     

A study of ACO capabilities for solving the maximum clique problem

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph. We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.     

Subgraph extraction and metaheuristics for the maximum clique problem

The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of an order of all the vertices whereby those belonging to a maximum clique stay close enough to each other. Such an order can be identified via the extraction of a particular subgraph from the original graph. The problem can consequently be seen as a permutation problem that can be addressed efficiently by metaheuristics. We first design a memetic algorithm (MA) for this purpose. Computational experiments conducted on the DIMACS benchmark instances clearly show that our MA not only outperforms existing genetic approaches, but it also compares very well to state-of-the-art algorithms regarding the maximal clique size found after different runs. Furthermore, we show that a hybridization of MA with an iterated local search (ILS) improves the stability of the algorithm. This hybridization (MA-ILS) permits to find two distinct maximal cliques of size 79 and one of size 80 for the C2000.9 instance of the DIMACS benchmark.     

Extended clique initialisation in examination timetabling

Many examination timetabling procedures employ a phased approach in which the first phase is often the allocation of a large set of mutually conflicting examinations which form a clique in the associated problem graph. The usual practice is to identify a single maximum clique, often quite arbitrarily, in this first phase. We show that in typical examination timetabling problems, unlike random graphs, there are often many alternative maximum cliques, and even larger dense subsets of nodes that are almost cliques. A number of methods are proposed for extending the scope of the clique initialisation to include a larger subset of examinations by considering sub-maximum cliques and/or quasi-cliques.     

Evolution towards the Maximum Clique

As is well known, the problem of finding a maximum clique in a graph isNP-hard. Nevertheless, NP-hard problems may have easy instances. This paperproposes a new, global optimization algorithm which tries to exploit favourabledata constellations, focussing on the continuous problem formulation: maximizea quadratic form over the standard simplex. Some general connections of thelatter problem with dynamic principles of evolutionary game theory areestablished. As an immediate consequence, one obtains a procedure whichconsists (a) of an iterative part similar to interior-path methods based on theso-called replicator dynamics; and (b) a routine to escape from inefficient,locally optimal solutions. For the special case of finding a maximum clique ina graph where the quadratic form arises from a regularization of the adjacencematrix, part (b), i.e. escaping from maximal cliques not of maximal size, isaccomplished with block pivoting methods based on (large) independent sets,i.e. cliques of the complementary graph. A simulation study is included whichindicates that the resulting procedure indeed has some merits.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

A hybrid iterated local search heuristic for the maximum weight independent set problem

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.     

A nonconvex quadratic optimization approach to the maximum edge weight clique problem

The maximum edge weight clique (MEWC) problem, defined on a simple edge-weighted graph, is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. We establish the correspondence between local maxima of the proposed formulation and maximal cliques of the underlying graph, implying that the characteristic vector of a MEWC in the graph is a global optimizer of the continuous problem. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented.     

An independent set approach for the communication network of the GPS III system

In this article, we describe an algorithm to find the optimal communication network for the new GPS III satellite system. Finding a possible network will be translated to a maximum clique problem and an efficient algorithm for finding all maximum cliques under these special circumstances is described.     

Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study

This paper compares the performance of genetic algorithms (GAs) on large-scale maximum expected coverage problems to other heuristic approaches. We focus our attention on a particular formulation with a nonlinear objective function to be optimized over a convex set. The solutions obtained by the best genetic algorithm are compared to Daskin's heuristic and the optimal or best solutions obtained by solving the corresponding integer linear programming (ILP) problems. We show that at least one of the GAs yields optimal or near-optimal solutions in a reasonable amount of time.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Speeding up branch and bound algorithms for solving the maximum clique problem

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525–547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.     

A finding maximal clique algorithm for predicting loop of protein structure

In this paper we equate the problem of predicting the loop 3D structure in the comparative modeling to a problem of finding the maximal clique with the best weight. Each possible conformation of a residue in a loop sequence is represented as a node in a graph. Edges are then drawn between pairs of nodes that are consistent with each other. Edge and nodes are weighted according to some fixed criteria. Once the entire graph is constructed, all the maximal sets of cliques are found using an algorithm of artificial neural network models. The cliques with the best weights represent the optimal conformation of the region of loop sequence.     

Calibrating continuous multi-objective heuristics using mixture experiments

A genetic algorithm heuristic that uses multiple rank indicators taken from a number of well established evolutionary algorithms including NSGA-II, IBEA and SPEA2 is developed. It is named Multi-Indicator GA (MIGA). At every iteration, MIGA uses one among the available indicators to select the individuals which will participate as parents in the next iteration. MIGA chooses the indicators according to predefined probabilities found through the analysis of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the point that provides the maximum we also find good algorithm parameters. To the best of our knowledge, this is the first paper where mixture experiments are used for heuristic tuning. The design of mixture experiments approach allowed the authors to identify and exploit synergy between the different rank indicators. This is demonstrated by our experimental results in which the tuned MIGA compares favorably to other well established algorithms, an uncalibrated multi-indicator algorithm, and a multi-indicator algorithm calibrated using a more conventional approach.     

An indirect genetic algorithm for set covering problems

This paper presents a new type of genetic algorithm for the set covering problem. It differs from previous evolutionary approaches first because it is an indirect algorithm, ie the actual solutions are found by an external decoder function. The genetic algorithm itself provides this decoder with permutations of the solution variables and other parameters. Second, it will be shown that results can be further improved by adding another indirect optimisation layer. The decoder will not directly seek out low cost solutions but instead aims for good exploitable solutions. These are then post-optimised by another hill-climbing algorithm. Although seemingly more complicated, we will show that this three-stage approach has advantages in terms of solution quality, speed and adaptability to new types of problems over more direct approaches. Extensive computational results are presented and compared to the latest evolutionary and other heuristic approaches to the same data instances.     

Planar maximal covering location problem under block norm distance measure

This paper introduces a new model for the planar maximal covering location problem (PMCLP) under different block norms. The problem involves locating g facilities anywhere on the plane in order to cover the maximum number of n given demand points. The generalization, in this paper, is that the distance measures assigned to facilities are block norms of different types and different proximity measures. First, the PMCLP under different block norms is modelled as a maximum clique partition problem on an equivalent multi-interval graph. Then, the equivalent graph problem is modelled as an unconstrained binary quadratic problem (UQP). Both the maximum clique partition problem and the UQP are NP-hard problems; therefore, we solve the UQP format through a genetic algorithm heuristic. Computational examples are given.     

A Localized Implementation of the Iterative Proportional Scaling Procedure for Gaussian Graphical Models

In this article, we propose localized implementations of the iterative proportional scaling (IPS) procedure by the strategy of partitioning cliques for computing maximum likelihood estimations in large Gaussian graphical models. We first divide the set of cliques into several nonoverlapping and nonempty blocks, and then adjust clique marginals in each block locally. Thus, high-order matrix operations can be avoided and the IPS procedure is accelerated. We modify the Swendsen–Wang Algorithm and apply the simulated annealing algorithm to find an approximation to the optimal partition which leads to the least complexity. This strategy of partitioning cliques can also speed up the existing IIPS and IHT procedures. Numerical experiments are presented to demonstrate the competitive performance of our new implementations and strategies.     

Multi-neighborhood tabu search for the maximum weight clique problem

Given an undirected graph G=(V,E) with vertex set V={1,??,n} and edge set E?V×V. Let w:V??Z ⁺ be a weighting function that assigns to each vertex i??V a positive integer. The maximum weight clique problem (MWCP) is to determine a clique of maximum weight. This paper introduces a tabu search heuristic whose key features include a combined neighborhood and a dedicated tabu mechanism using a randomized restart strategy for diversification. The proposed algorithm is evaluated on a total of 136 benchmark instances from different sources (DIMACS, BHOSLIB and set packing). Computational results disclose that our new tabu search algorithm outperforms the leading algorithm for the maximum weight clique problem, and in addition rivals the performance of the best methods for the unweighted version of the problem without being specialized to exploit this problem class.