Two exact algorithms for the capacitated p-median problem

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any ratio.Received: December 2002, Revised: August 2003AMS classification: 90C10, 90C27     

An additive bounding procedure for the asymmetric travelling salesman problem

In this paper, new lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences. The new bounds are combined in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981). Both procedures have been imbedded in a simple branch and bound algorithm and experimentally evaluated on hard test problems.     

Influence of magnetic quantization on the effective electron mass in Kane-type semiconductors

Summary We study the effective electron mass at the Fermi level in Kane-type semiconductors on the basis of fourth order in effective mass theory and taking into account the interactions of the conduction electrons, heavy holes, light holes and split-off holes, respectively. The results obtained are then compared to those derived on the basis of the well-known three-band Kane model. It is found, takingn-Hg_1−x Cd _x Te as an example, that the effective electron mass at the Fermi level in accordance with fourth-order model depends on the Fermi energy, magnetic quantum number and the electron spin respectively due to the influence of band nonparabolicity only. The dependence of effective mass on electron spin is due to spin-orbit splitting parameter of the valence band in three-band Kane model and the Fermi energy due to band nonparabolicity in two-band Kane model. The same mass exhibits an oscillatory magnetic-field dependence for all the band models as expected since the origin of oscillations in the effective mass in nonparabolic compounds is the same as that of the Shubnikov-de Hass oscillations. In addition, the corresponding results for parabolic energy bands have been obtained from the generalized expressions under certain limiting conditions.     

The one-dimensional Hubbard model for large or infiniteU

The magnetic properties of the one-dimensional Hubbard model with a hardcore interaction on a ring (periodic boundary conditions) are investigated. At finite temperatures it is shown to behave up to exponentially small corrections as a pure paramagnet. An explicit expression for the ground-state degeneracies is derived. The eigenstates of this model are used to perform a perlurbational treatment for large but finite interactions. In first order inU ¹ an effective Hamiltonian for the one-dimensional Hubbard model is derived. It is the Hamiltonian of the one-dimensional Hcisenberg model with antiferromagnetic couplings between nearest neighbor spins. An asymptotic expansion for the ground-state energy is given. The results are valid for arbitrary densities of electrons.     

等式与界约束非线性优化信赖域算法的全局收敛

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＣｏｎｓｉｄｅｒｔｈｅｆｏｌｌｏｗｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ :ｍｉｎｉｍｉｚｅｆ(ｘ)ｓｕｂｊｅｃｔｔｏＣ(ｘ) =0 ,　ａ≤ｘ≤ｂ ,( 1 .1 )ｗｈｅｒｅｆ(ｘ) :Ｒｎ→Ｒ ,Ｃ(ｘ) =(ｃ1(ｘ) ,ｃ2 (ｘ) ,...,ｃｍ(ｘ) ) Ｔ:Ｒｎ→Ｒｍ ａｒｅｔｗｉｃｅｃｏｎｔｉｎｕｏｕｓｌｙｄｉｆｆｅｒｅｎｔｉａｂｌｅ,ｍ≤ｎ ,ａ ,ｂ∈Ｒｎ.Ｔｒｕｓｔｒｅｇｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｖｅｒｙｅｆｆｅｃｔｉｖｅｆｏｒｓｏｌｖｉｎｇｎｏｎｌｉｎｅａｒｏｐｔｉｍｉ…     

关于图的下完美邻域数的上界一些结果

本文主要讨论了图的下完美邻域数 ,并给出了θ(G) =γ(G)的充分必要条件 ,并讨论了一些特殊图类的下完美邻域数的上界 ,特别对于树采用了对所有点分层的方法进行了较细致的讨论 ,给出了紧上界θ(T)≤ [n3] .     

广义保险模型的破产概率问题研究

本文对于广义保险模型，利用鞅的表示性，随机Thiele微分方程，计数过程以及随机积分的有关理论，研究了保险的破产概率问题，得到了破产概率上界的理论形式以及Lunberg指数。     

谱半径前六位的n阶单圈图

恰含一个圈的简单连通图称为单圈图。Cn记n个顶点的圈。△（i,j,κ）记C3的三个顶点上分别接出i,j,κ条悬挂边所得的图，其中i≥j≥κ≥0.Sl^n-l记Cl的某一顶点上接出n-l条悬挂边所得到的图。△（n-4 1,0,0)记△（n-4,0,0)的某个悬挂点上接出一条悬挂边所得到的图。本文证明了：若把所有n(n≥12）阶单圈图按其最大特征值从大到小的顺序排列，则排在前六位的依次是S3^n-3，△（n-4,1,0),△（n-4 1,0,0),S4^n-4,△（n-5,2,0),△（n-5,1,1)。     

On perturbations of matrix pencils with real spectra, a revisit

This paper continues earlier studies by Bhatia and Li on eigenvalue perturbation theory for diagonalizable matrix pencils having real spectra. A unifying framework for creating crucial perturbation equations is developed. With the help of a recent result on generalized commutators involving unitary matrices, new and much sharper bounds are obtained.

     

On laplace continued fraction for the normal integral

The Laplace continued fraction is derived through a power series. It provides both upper bounds and lower bounds of the normal tail probability % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiqbfA6agzaaraaaaa!3DC0!\[\bar \Phi\](x), it is simple, it converges for x>0, and it is by far the best approximation for x3. The Laplace continued fraction is rederived as an extreme case of admissible bounds of the Mills' ratio, % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiqbfA6agzaaraaaaa!3DC0!\[\bar \Phi\](x)/(x), in the family of ratios of two polynomials subject to a monotone decreasing absolute error. However, it is not optimal at any finite x. Convergence at the origin and local optimality of a subclass of admissible bounds are investigated. A modified continued fraction is proposed. It is the sharpest tail bound of the Mills' ratio, it has a satisfactory convergence rate for x1 and it is recommended for the entire range of x if a maximum absolute error of 10^-4 is required.The efforts of the author were supported by the NSERC of Canada.