一类B可微方程的非精确阻尼牛顿法

本文提出了求解一类基于双障碍问题的Ｂ可微方程的非精确阻尼牛顿法,并在一定条件下,证明了该算法的全局收敛性和二阶收敛性。     

How to Get the Original Discrete Approximation for the Pyramid Algorithm of Multiresolution Decomposition

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｔｈｉｓｐａｐｅｒ,ｗｅｕｓｅｔｈｅｎｏｔａｔｉｏｎｓＺ,Ｒ,Ｌ２（Ｒ）ａｎｄｌ２ｆｏｒｔｈｅｓｅｔｏｆｉｎｔｅｇｅｒｓ,ｒｅ－ａｌｓ,ｓｑｕａｒｅｉｎｔｅｇｒａｂｌｅｆｕｎｃｔｉｏｎｓａｎｄｓｑｕａｒｅｓｕｍｍａｂ...     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

化学蚁群算法与多组分导数荧光光谱解析

在分析化学计量学中 ,每一种新算法的诞生都会带动新一轮的研究热潮的掀起 ,并极大的推动着化学计量学的发展 .因此 ,积极开展分析化学计量学新算法的研究具有重大的理论和实际意义 .蚁群算法 ( Ant Colony Algorithm,缩写 ACA)也称蚁群系统 ( ACS) ,是意大利学者 Dorigo等[1] 新近提出的一种模拟进化算法 .该算法具有正反馈、分布式计算、鲁棒性强及易与其它算法相结合等突出优点 ,是求解组合优化问题的一种尚佳方法 .目前已被成功地应于通讯、交通和人工智能等领域[2～ 5] .尤其是最近用蚁群算法编程的微型机器人的问世 [6 ] ,更引起…     

A linear time algorithm to remove winding of a simple polygon

In this paper, we present a linear time algorithm to remove winding of a simple polygon P with respect to a given point q inside P. The algorithm removes winding by locating a subset of Jordan sequence that is in the proper order and uses only one stack.     

A combinatorial proof of the Lebesgue identity

We present a combinatorial proof of the Lebesgue identity based on the insertion algorithm of Zeilberger.     

On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint

In this paper we consider the problem of partitioning large sparse graphs, such as finite element meshes. The heuristic which is proposed allows to partition into connected and quasi-balanced subgraphs in a reasonable amount of time, while attempting to minimize the number of edge cuts. Here the goal is to build partitions for graphs containing large numbers of nodes and edges, in practice at least 10⁴. Basically, the algorithm relies on the iterative construction of connected subgraphs. This construction is achieved by successively exploring clusters of nodes called fronts. Indeed, a judicious use of fronts ensures the connectivity of the subsets at low cost: it is shown that locally, i.e. for a given subgraph, the complexity of such operations grows at most linearly with the number of edges. Moreover, a few examples are given to illustrate the quality and speed of the heuristic.The work of this author was partially supported by the DGA/DRET under contract 93-1192 and by the Army Research Office under contract DAAL03-91-C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1).The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1), and ONR under contract ONR-N00014-92-J-1890.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

Kullback-Liebler测度在地震记录反演中的应用

在地震记录反演中,盲目反褶积是一个相当困难的问题.讨论这个问题现有各种方法,如累积矩法等.本文利用Likas等处理图像恢复的变分法来讨论地震记录反演中的盲目反褶积问题.利用Kullback-Liebler信息测度获得一个非常有用的统计函数(即变分函数),此函数的极值点就含有所要求的反射系数序列的信息,并且拟订出求此泛数极值点的一套算法.     

Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines

In this paper, we study the permutation flow shop scheduling problems with deteriorating jobs on no-idle dominant machines. The objective is to minimize one of the two regular performance criteria, namely, makespan and total completion time. For each objective, the following dominant machines constraint: idm, ddm, idm–ddm and ddm–idm are considered. We present a polynomial time solution algorithm for each of the four cases.