Complexity of local search for the p-median problem

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0–1 local saddle points, and classical Karush–Kuhn–Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.     

Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

加细函数正交性的一个判别准则

In this note, a criterion for orthonormality of refinable functions via characteristicpolynomial of a matrix is given.     

The Nonchiral Fusion Rules in Rational Conformal Field Theories

We introduce a general method in order to construct the nonchiral fusion rules which determine the operator content of the operator product algebra for rational conformal field theories. We are particularly interested in the models of the complementary D-like solutions of the modular invariant partition functions with cyclic center Z _N . We find that the nonchiral fusion rules have a Z _N -grading structure.     

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).     

Numerical treatment of retarded boundary integral equations by sparse panel clustering

Stefan Sauter Institute for Mathematics, University of Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland ^{We consider the wave equation in a boundary integral formulation.The discretization in time is done by using convolution quadraturetechniques and a Galerkin boundary element method for the spatialdiscretization. In a previous paper, we have introduced a sparseapproximation of the system matrix by cut-off, in order to reducethe storage costs. In this paper, we extend this approach byintroducing a panel clustering method to further reduce thesecosts.}     

Quadratic Actions in Dependent Fields and the Action Principle

General field theories are considered, within the functional differential formalism of quantum field theory, with interaction Lagrangian densities L _I (x;λ), with λ a generic coupling constant, such that the following expression ∂ L _I (x;λ)/∂ λ may be expressed as quadratic functions in dependent fields but may, in general, be arbitrary functions of independent fields. These necessarily include, as special cases, present renormalizable gauge theories. It is shown, in a unified manner, that the vacuum-to-vacuum transition amplitude (the generating functional) may be explicitly derived in functional differential form which, in general, leads to modifications to computational rules by including such factors as Faddeev–Popov ones and modifications thereof which are explicitly obtained. The derivation is given in the presence of external sources and does not rely on any symmetry and invariance arguments as is often done in gauge theories and no appeal is made to path integrals.     

A Generalization of Ostrowski Integral Inequality for Mappings Whose Derivatives Belong to L_1 [a,b] and Applications in Numerical Integration

A generalization of Ostrowski integral inequality for mappings whose derivatives belong to L_1 [a,b], and applications for general quadrature formulae are given.     

基于粗糙集的经济预警规则发现

应用粗糙集的理论和方法对经济预警有关数据进行分析,挖掘其中隐含的有用信息,提取规则并对规则进行约简,从而求取表达经济预警信息的最小决策规则,为经济预警有用信息的获取提供一种有效的方法.     

旋转压电纳米梁的振动分析

本文基于非局部弹性理论，对旋转压电纳米梁模型的振动进行了分析．首先由哈密顿原理导出旋转压电纳米梁的动力学控制方程及相应的边界条件；再通过微分求积法对控制方程和两类边界条件进行离散；最后通过数值计算分析振动特性．通过改变旋转角速度、轮毂半径、非局部参数以及外部电压分析它们对压电纳米梁振动频率的影响关系．数值结果表明这些参数对压电纳米梁固有频率有不可忽略的影响，本文进一步讨论了旋转角速度对结构模态的影响．