最小最大二点集覆盖问题分析及改进算法设计

本文考虑二中心问题的扩展问题-最小最大二点集覆盖问题。给定两个平面点集P₁和P₂,分别包含m和n个点,求两个圆分别覆盖P₁和P₂,并且要求两圆半径与两圆圆心距三者中的最大值最小。本文主要贡献在于分析半径变化过程中两个点集中心包之间最近距离的变化关系,其中中心包是点集所具有的一个特殊几何结构,所得到的结果改进了Huang等人之前给出的结果,并且通过该结果设计相应算法,所得到的算法复杂性是目前最好的。     

求解无容量设施选址问题的拉格朗日蝙蝠算法

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是一类经典的组合优化问题,被证明是一种NP-hard问题,易于描述却难于求解.首先根据UFLP的数学模型及其具体特征,重新设计了蝙蝠算法的操作算子,给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法,并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合,设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式,验证了该混合算法用来求解UFLP的可行性,是解决离散型问题的一种有效方式.     

无容量限制设施选址问题的降阶回溯算法

无容量限制设施选址问题(uncapacitated facility location problem, UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

The rectilinear distance Weber problem in the presence of a probabilistic line barrier

This paper considers the problem of locating a single facility in the presence of a line barrier that occurs randomly on a given horizontal route on the plane. The objective is to locate this new facility such that the sum of the expected rectilinear distances from the facility to the demand points in the presence of the probabilistic barrier is minimized. Some properties of the problem are reported, a solution algorithm is provided with an example problem, and some future extensions to the problem are discussed.     

芬布芬-铜（Ⅱ）-牛血清白蛋白相互作用的光谱法研究

模拟生理条件下,应用荧光光谱法研究了芬布芬对牛血清白蛋白,铜（Ⅱ）对牛血清白蛋白以及铜（Ⅱ）对芬布芬和牛血清白蛋白荧光光谱特性的影响.实验表明：铜（Ⅱ）和芬布芬均可使牛血清白蛋白的荧光强度发生静态猝灭,并且在铜（Ⅱ）存在下,芬布芬对牛血清白蛋白的荧光猝灭作用显著增强.根据荧光猝灭双倒数图计算芬布芬和牛血清白蛋白的结合常数为8.44×104,结合位点数为0.97.荧光猝灭双倒数图计算的结果表明,芬布芬和牛血清白蛋白之间的结合常数和结合位点数均随铜（Ⅱ）浓度的增大而增大.很据三者结合反应的研究,进一步探讨了芬布芬、铜（Ⅱ）在生物体内与蛋白质相互作用的机理.     

锂玻璃探测器中子探测效率的刻度

为了精确测量keV能区的中子俘获截面,中国原子能科学研究院正在建造一台4π 全吸收型γ 探测装置---GTAF,锂玻璃探测器将会作为中子束流监视器测量中子能谱。利用5SDH-2 加速器刻度了锂玻璃探测器在两个入射中子单能点(250 和565 keV) 的探测效率,并使用EANT4 和MCNP 程序模拟计算了锂玻璃探测器的相对探测效率。通过归一化实验数据和模拟结果,得到了锂玻璃探测器在10keV~1 MeV 能区的中子探测效率曲线。对于把锂玻璃探测器测量得到的飞行时间谱转化为中子束流能谱,是一项非常重要的工作,同时为探测器效率刻度提供了新方法。In order to accurately measure the neutron capture cross section in the energy range of keVMeV, 4 πgamma-ray total absorption facility (GTAF) is being constructed at China Institute of Atomic Energy (CIAE). The lithium glass detector will be used as a neutron beam monitor for GTAF. The detection efficiency of the lithium glass detector at two incident neutron energy points (250, 565 keV) was calibrated in 5SDH-2 accelerator, and the relative detection efficiency was simulated by GEANT4 and MCNP code. By the normalization of the experimental data and simulation result, the neutron detection efficiency curve of the lithium glass detector between 10 keV and 1 MeV was obtained. This work will be important to convert the Time-of-flight spectrum that be measured by Li-glass detector to the energy spectrum of neutron beam, and provide the new method for calibration of detection efficiency.     

IP modeling of the survivable hop constrained connected facility location problem

We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least λ edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for finding its solution. Finally, we report computational results.     

Robust Optimization for the Connected Facility Location Problem

In this paper we present a robust optimization (RO) model for the Connected Facility Location (ConFL) problem within the framework introduced by Bertsimas and Sim [Bertsimas, D. and M. Sim, Robust discrete optimization and network flows, Mathematical Programming 98 (2003), pp. 49–71], and show how to use a heuristic in conjunction with a lower bounding mechanism to rapidly find high-quality solutions. The use of a heuristic and a lower bound mechanism within this RO approach decreases significantly its computational time and broadens its applicability to other NP-hard problems. Here we present some of our computational results that attest to the efficiency of the approach, particularly on the Robust ConFL problem.