An effective local search for the maximum clique problem

We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.     

A simple simulated annealing algorithm for the maximum clique problem

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.     

最大团问题的改进遗传算法求解

最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。     

一种基于匹配交叉求解最大团问题的Memetic算法

针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法.     

A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem

The efficiency of metaheuristic algorithms depends significantly on the number of fitness value evaluations performed on candidate solutions. In addition to various intelligent techniques used to obtain better results, parallelization of calculations can substantially improve the solutions in cases where the problem is NP-hard and requires many evaluations. This study proposes a new parallel tabu search method for solving the Maximum Vertex Weight Clique Problem (MVWCP) on the Non-Uniform Memory Access (NUMA) architectures using the OpenMP parallel programming paradigm. Achieving scalability in the NUMA architectures presents significant challenges due to the high complexity of their memory systems, which can lead to performance loss. However, our proposed Tabu-NUMA algorithm provides up to $18\times$ speed-up with 64 cores for ten basic problem instances in DIMACS-W and BHOSLIB-W benchmarks. And it improves the performance of the serial Multi Neighborhood Tabu Search (MN/TS) algorithm for 38 problem instances in DIMACS-W and BHOSLIB-W benchmarks. We further evaluate our algorithm on larger datasets with thousands of edges and vertices from Network Data Repository benchmark problem instances, and we report significant improvements in terms of speed up. Our results confirm that the Tabu-NUMA algorithm is among the best recent algorithms for solving MVWCP on the NUMA architectures.     

An exact bit-parallel algorithm for the maximum clique problem

This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.     

Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring

The linear programming relaxation of the minimum vertex coloring problem, called the fractional coloring problem, is NP-hard. We describe efficient approximation procedures for both the weighted and unweighted versions of the problem. These fractional coloring procedures are then used for generating upper bounds for the (weighted or unweighted) maximum clique problem in the framework of a branch-and-bound procedure. Extensive computational testing shows that replacing the standard upper bounding procedures based on various integer coloring heuristics with the somewhat more expensive fractional coloring procedure results in improvements of the bound by up to one-fourth in the unweighted and up to one-fifth in the weighted case, accompanied by a decrease in the size of the search tree by a factor of almost two.This research was supported by the National Science Foundation under Grant No. DDM-9201340 and the Office of Naval Research through Contract N00014-85-K-0198.     

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为[O(1.380np(n)),]其中[p(n)]表示问题规模数[n]的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的[O(1.380np(n))]降为[O(1.325np(n))]。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。     

基于均匀免疫优化算法的最大团问题求解

最大团问题是一种典型的组合优化问题,具有广泛的应用背景。针对最大团问题的NP特性,提出了一种基于免疫克隆优化的智能求解算法。描述了最大团问题的数学模型,设计了求解最大团问题的抗体编码、亲和度函数、变异算子及抗体修正方法。在免疫克隆参数设置时,将其描述为多因素多水平的均匀设计,减少了设置参数的实验次数。通过最大团问题的基准算例进行了实验。结果表明,本算法求解效果较好,并且求解速度较快。     

On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem

When searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy.     

Intelligent-guided adaptive search for the maximum covering location problem

Computational intelligence techniques are part of the search process in several recent heuristics. One of their main benefits is the use of an adaptive memory to guide the search towards regions with promising solutions. This paper follows this approach proposing a variation of a well-known iteration independent metaheuristic. This variation adds a learning stage to the search process, which can improve the quality of the solutions found. The proposed metaheuristic, named Intelligent-Guided Adaptive Search (IGAS), provides an efficient solution to the maximum covering facility location problem. Computational experiments conducted by the authors showed that the solutions found by IGAS were better than the solutions obtained by popular methods found in the literature.     

On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem.     

A tutorial on branch and cut algorithms for the maximum stable set problem

This tutorial provides an overview of various characteristics of effective branch and cut type algorithms for the maximum stable set problem. We discuss several facet‐defining inequalities for the stable set polytope along with their separation routines. In particular, we review implementation tweaks for the separation routines and reference empirical studies, illustrating the performance of these cutting planes for benchmark graphs. In addition to the polyhedral study, we present basic preprocessing, discuss heuristic methods particularly suited within a branch and cut framework, and examine a branching rule.     

An improved algorithm for the maximum agreement subtree problem

In this paper, we solve the maximum agreement subtree problem for a set T of k rooted leaf-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn³)-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn²+n²logk−2nloglogn) and O(kn3−1/(k−1)) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k<2+(logn−logloglogn)/(loglogn), the first implementation will be significantly faster than Bryant's algorithm. For k=3, it yields the best known algorithm which runs in O(n²lognloglogn)-time.     

Physical mapping of chromosomes: A combinatorial problem in molecular biology

This paper is concerned wth the physical mapping of DNA molecules using data about the hybridization of oligonucleotide probes to a library of clones. In mathematical terms, the DNA molecule corresponds to an interval on the real line, each clone to a subinterval, and each probe occurs at a finite set of points within the interval. A stochastic model for the occurrences of the probes and the locations of the clones is assumed. Given a matrix of incidences between probes and clones, the task is to reconstruct the most likely interleaving of the clones. Combinatorial algorithms are presented for solving approximations to this problem, and computational results are presented.Research supported in part by NSF Grant No. CDA-9211106.Research supported in part by NSF Grant No. CCR-9005448.     

The maximum linear arrangement problem for trees under projectivity and planarity

A linear arrangement is a mapping π from the n vertices of a graph G to n distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the edges as semicircles above said line. In this setting, the length of an edge is defined as the absolute value of the difference between the positions of its two vertices in the arrangement, and the cost of an arrangement as the sum of all edge lengths. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In the planar variant for free trees, vertices have to be arranged in such a way that there are no edge crossings. In the projective variant for rooted trees, arrangements have to be planar and the root of the tree cannot be covered by any edge. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements, and show that caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby generalizing a previous extremal result on trees.     

New heuristic algorithms for solving the planar p-median problem

In this paper we propose effective heuristics for the solution of the planar p-median problem. We develop a new distribution based variable neighborhood search and a new genetic algorithm, and also test a hybrid algorithm that combines these two approaches. The best results were obtained by the hybrid approach. The best known solution was found in 466 out of 470 runs, and the average solution was only 0.000016% above the best known solution on 47 well explored test instances of 654 and 1060 demand points and up to 150 facilities.     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

On single-walk parallelization of the job shop problem solving algorithms

New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine-grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU, General-Purpose computing on Graphics Processing Units).