Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).     

最佳粮库地址的选择

管理部门通常要选择适当的地方建造粮库 ,所需服务范围已知 ,各部门运输量给定 .需为他们选择合适的地方 ,使总运费最少 .某乡的九个村 (A,B,C,… ,H,I)如图 1 ,各村距离给出 ,并标明它们各自上缴公粮数 .管理部门希望在村内或道路上建立一个粮库 ,最大限度地减少运输费用 .问题的解法有几种方案 ,对于本题来说 ,穷举搜索法是可行的 .另外 ,我们提出一种分析求解法 ,可找到优化解 .它利用图论的基础知识先求出图 1的各顶点间的最小路径 ,再进一步求出图的绝对中心 (即粮库的地址 ) ,其中的有关计算利用了 C++语言程序 .在此基础上 ,还可对问题的参数作更精细的分析 .概括地说 ,穷举搜索法对于简单的区域是行之有效的 .但对于更加一般化的问题 ,利用计算机可快捷准确地得到答案 .通过建立模型 ,我们得到下面两个结论 :(1 )我们找到最优解是 E点 ,其总运费为 1 2 775元 .(2 )模型具有广泛性 ,对于更一般的区域 ,可利用计算机总可以求出最优解 .     

Density functional studies of molecular structures of N-methyl formamide, N,N-dimethyl formamide, and N,N-dimethyl acetamide

Density functional theory was applied to the calculation of molecular structures of N-methyl formamide (NMF), N,N-dimethyl formamide (DMF), and N,N-dimethyl acetamide (DMA). DFT calculations on NMF, DMF, and DMA were performed using a combination of the local functional of Vosko, Wilk, and Nusair (VWN) with the nonlocal exchange functional of Becke and the nonlocal correlational functional of Lee, Yang, and Parr (BLYP). The adiabatic connection method (ACM) of Becke has also been used, for the first time, for the calculation of molecular structures of NMF, DMF, and DMA. The calculated molecular structures are in excellent agreement with the experimental geometries of NMF and DMA derived from gas-phase electron-diffraction studies. Sparse experimental data on the gas-phase geometry of DMF reported in the literature compares well with the DFT results on DMF. DFT emerges as a powerful method to calculate molecular structures.     

Project Scheduling with Multiple Modes: A Genetic Algorithm

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.     

On the numerical solution of the linear complementarity problem

The well-known linear complementarity problem with definite matrices is considered. It is proposed to solve it using a global optimization algorithm in which one of the basic stages is a special local search. The proposed global search algorithm is tested using a variety of randomly generated problems; a detailed analysis of the computational experiment is given.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Effects of initial states on the quantum correlations in the generalized Grover search algorithm

We investigate the correlations between two qubits in the Grover search algorithm with arbitrary initial states by numerical simulation. Using a set of suitable bases, we construct the reduced density matrix and give the numerical expression of correlations relating to the iterations. For different initial states, we obtain the concurrence and quantum discord compared with the success probability in the algorithm. The results show that the initial states affect the correlations and the limit point of the correlations in the searching process. However, the initial states do not influence the whole cyclical trend.     

A UNIVERSAL APPROACH FOR CONTINUOUS OR DISCRETE NONLINEAR PROGRAMMINGS WITH MULTIPLE VARIABLES AND CONSTRAINTS

IntroductionExtensive research works have been published for solving nonlinear mathematicprogramming problems.Nonetheless,it is still difficult to find an effective and universalapproach for general programming problems with multiple design variables and …     

双相介质参数反演的混沌搜索方法

混沌运动能在一定的范围内按自身的规律不重复地遍历所有状态。利用这个特点 ,本文将混沌运动引入到双相介质参数反问题的研究中。首先利用边界元方法实现了由介质参数到地表位移的非线性映射 ,然后通过建立合成位移与实测位移的相关函数将参数识别问题归结为优化问题 ,最后利用混沌运动指导优化搜索求得介质参数。算例结果表明了混沌搜索方法用于双相介质参数反演问题的可行性和有效性     

SKATE: A docking program that decouples systematic sampling from scoring

SKATE is a docking prototype that decouples systematic sampling from scoring. This novel approach removes any interdependence between sampling and scoring functions to achieve better sampling and, thus, improves docking accuracy. SKATE systematically samples a ligand's conformational, rotational and translational degrees of freedom, as constrained by a receptor pocket, to find sterically allowed poses. Efficient systematic sampling is achieved by pruning the combinatorial tree using aggregate assembly, discriminant analysis, adaptive sampling, radial sampling, and clustering. Because systematic sampling is decoupled from scoring, the poses generated by SKATE can be ranked by any published, or in‐house, scoring function. To test the performance of SKATE, ligands from the Asetex/CDCC set, the Surflex set, and the Vertex set, a total of 266 complexes, were redocked to their respective receptors. The results show that SKATE was able to sample poses within 2 Å RMSD of the native structure for 98, 95, and 98% of the cases in the Astex/CDCC, Surflex, and Vertex sets, respectively. Cross‐docking accuracy of SKATE was also assessed by docking 10 ligands to thymidine kinase and 73 ligands to cyclin‐dependent kinase. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2010