Using dual network bounds in algorithms for solving generalized set packing partitioning problems

This article deals with a method to compute bounds in algorithms for solving the generalized set packing/partitioning problems. The problems under investigation can be solved by the branch and bound method. Linear bounds computed by the simplex method are usually used. It is well known that this method breaks down on some occasions because the corresponding linear programming problems are degenerate. However, it is possible to use the dual (Lagrange) bounds instead of the linear bounds. A partial realization of this approach is described that uses a network relaxation of the initial problem. The possibilities for using the dual network bounds in the approximation techniques to solve the problems under investigation are described.     

Prediction-correction alternating direction method for a class of constrained min-max problems

The problems concerned in this paper are a class of constrained min-max problems. By introducing the Lagrange multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. However, to obtain components of the predictor one by one, we use an alternating direction method. And then the new iterate is generated by a minor correction. Global convergence of the proposed method is proved. Finally, numerical results for a constrained single-facility location problem are provided to verify that the new method is effective for some practical problems.      

Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions

Mukherjee and Basu proposed a new method for solving fuzzy assignment problems. In this paper, some fuzzy assignment problems and fuzzy travelling salesman problems are chosen which cannot be solved by using the fore-mentioned method. Two new methods are proposed for solving such type of fuzzy assignment problems and fuzzy travelling salesman problems. The fuzzy assignment problems and fuzzy travelling salesman problems which can be solved by using the existing method, can also be solved by using the proposed methods. But, there exist certain fuzzy assignment problems and fuzzy travelling salesman problems which can be solved only by using the proposed methods. To illustrate the proposed methods, a fuzzy assignment problem and a fuzzy travelling salesman problem is solved. The proposed methods are easy to understand and apply to find optimal solution of fuzzy assignment problems and fuzzy travelling salesman problems occurring in real life situations.     

A meshless method for nonhomogeneous polyharmonic problems using method of fundamental solution coupled with quasi-interpolation technique

This paper proposes a meshless method based on coupling the method of fundamental solutions (MFS) with quasi-interpolation for the solution of nonhomogeneous polyharmonic problems. The original problems are transformed to homogeneous problems by subtracting a particular solution of the governing differential equation. The particular solution is approximated by quasi-interpolation and the corresponding homogeneous problem is solved using the MFS. By applying quasi-interpolation, problems connected with interpolation can be avoided. The error analysis and convergence study of this meshless method are given for solving the boundary value problems of nonhomogeneous harmonic and biharmonic equations. Numerical examples are also presented to show the efficiency of the method.     

关于吴方法在双层规划中的一个应用

双层规划及多层规划这一数学规划研究中的较新领域因其坚实的经济背景及丰富的数学内涵在二十年来的发展过程中变得越来越吸引人们的关注. 在通常解双层规划问题时往往采用数值计算的方法, 得到的解并不一定是全局最优解. 该文介绍了一个全新的解双层规划问题的方法,它与数值计算法不同, 采用的是符号计算, 依据了计算机代数与代数几何的理论. 作者通过对文献[1]中的几个双层规划问题的上机计算, 得出了与之不同的全面彻底的解答, 在比较过程中, 发现不仅所得的结果要比文献[1]中答案更进一步, 而且也证明了文章的新方法在解这一类问题时,是简明和行之有效的.     

用非线性方程组求解等式约束非线性规划问题的降维算法

本文研究线性和非线性等式约束非线性规划问题的降维算法.首先,利用一般等式约束问题的降维方法,将线性等式约束非线性规划问题转换成一个非线性方程组,解非线性方程组即得其解;然后,对线性和非线性等式约束非线性规划问题用Lagrange乘子法,将非线性约束部分和目标函数构成增广的Lagrange函数,并保留线性等式约束,这样便得到一个线性等式约束非线性规划序列,从而,又将问题转化为求解只含线性等式约束的非线性规划问题.     

A new method for solving fuzzy transportation problems using ranking function

In the literature, several methods are proposed for solving transportation problems in fuzzy environment but in all the proposed methods the parameters are represented by normal fuzzy numbers. [S.H. Chen, Operations on fuzzy numbers with function principal, Tamkang Journal of Management Sciences 6 (1985) 13–25] pointed out that in many cases it is not to possible to restrict the membership function to the normal form and proposed the concept of generalized fuzzy numbers. There are several papers in the literature in which generalized fuzzy numbers are used for solving real life problems but to the best of our knowledge, till now no one has used generalized fuzzy numbers for solving the transportation problems. In this paper, a new method is proposed for solving fuzzy transportation problems by assuming that a decision maker is uncertain about the precise values of the transportation cost, availability and demand of the product. In the proposed method transportation cost, availability and demand of the product are represented by generalized trapezoidal fuzzy numbers. To illustrate the proposed method a numerical example is solved and the obtained results are compared with the results of existing methods. Since the proposed method is a direct extension of classical method so the proposed method is very easy to understand and to apply on real life transportation problems for the decision makers.     

Some Test Problems on Applications of Wu＇s Method in Nonlinear Programming Problems

ＳｏｍｅＴｅｓｔＰｒｏｂｌｅｍｓｏｎＡｐｐｌｉｃａｔｉｏｎｓｏｆＷｕ＇ｓＭｅｔｈｏｄｉｎＮｏｎｌｉｎｅａｒＰｒｏｇｒａｍｍｉｎｇＰｒｏｂｌｅｍｓ吴天骄ＳｏｍｅＴｅｓｔＰｒｏｂｌｅｍｓｏｎＡｐｐｌｉｃａｔｉｏｎｓｏｆＷｕ＇ｓＭｅｔｈｏｄｉｎＮｏｎｌｉｎ...     

Chebyshev tau matrix method for Poisson-type equations in irregular domain

In this paper, a new meshless method, Chebyshev tau matrix method (CTMM) is researched. The matrix representations for the differentiation and multiplication of Chebyshev expansions make CTMM easy to implement. Problems with curve boundary can be efficiently treated by CTMM. Poisson-type problems, including standard Poisson problems, Helmholtz problems, problems with variable coefficients and nonlinear problems are computed. Some numerical experiments are implemented to verify the efficiency of CTMM, and numerical results are in good agreement with the analytical one. It appears that CTMM is very effective for Poisson-type problems in irregular domains.     

An alternating direction method of multipliers for elliptic equation constrained optimization problem

We propose an alternating direction method of multipliers (ADMM) for solving the state constrained optimization problems governed by elliptic equations. The unconstrained as well as box-constrained cases of the Dirichlet boundary control, Robin boundary control, and right-hand side control problems are considered here. These continuous optimization problems are transformed into discrete optimization problems by the finite element method discretization, then are solved by ADMM. The ADMM is an efficient first order algorithm with global convergence, which combines the decomposability of dual ascent with the superior convergence properties of the method of multipliers. We shall present exhaustive convergence analysis of ADMM for these different type optimization problems. The numerical experiments are performed to verify the efficiency of the method.     

An interpolation matched interface and boundary method for elliptic interface problems

An interpolation matched interface and boundary (IMIB) method with second-order accuracy is developed for elliptic interface problems on Cartesian grids, based on original MIB method proposed by Zhou et al. [Y. Zhou, G. Wei, On the fictious-domain and interpolation formulations of the matched interface and boundary method, J. Comput. Phys. 219 (2006) 228-246]. Explicit and symmetric finite difference formulas at irregular grid points are derived by virtue of the level set function. The difference scheme using IMIB method is shown to satisfy the discrete maximum principle for a certain class of problems. Rigorous error analyses are given for the IMIB method applied to one-dimensional (1D) problems with piecewise constant coefficients and two-dimensional (2D) problems with singular sources. Comparison functions are constructed to obtain a sharp error bound for 1D approximate solutions. Furthermore, we compare the ghost fluid method (GFM), immersed interface method (IIM), MIB and IMIB methods for 1D problems. Finally, numerical examples are provided to show the efficiency and robustness of the proposed method.     

Parallel finite element splitting-up method for parabolic problems

An efficient method for solving parabolic systems is presented. The proposed method is based on the splitting-up principle in which the problem is reduced to a series of independent 1D problems. This enables it to be used with parallel processors. We can solve multidimensional problems by applying only the 1D method and consequently avoid the difficulties in constructing a finite element space for multidimensional problems. The method is suitable for general domains as well as rectangular domains. Every 1D subproblem is solved by applying cubic B-splines. Several numerical examples are presented.     

New initial-value method for singularly perturbed boundary-value problems

An initial-value method is given for second-order singularly perturbed boundary-value problems with a boundary layer at one endpoint. The idea is to replace the original two-point boundary value problem by two suitable initial-value problems. The method is very easy to use and to implement. Nontrivial text problems are used to show the feasibility of the given method, its versatility, and its performance in solving linear and nonlinear singularly perturbed problems.This work was supported in part by the Consiglio Nazionale delle Ricerche, Contract No. 86.02108.01, and in part by the Ministero della Pubblica Istruzione.     

On the Pironneau-Polak method of centers

The method of centers is a well-known method for solving nonlinear programming problems having inequality constraints. Pironneau and Polak have recently presented a new version of this method. In the new method, the direction of search is obtained, at each iteration, by solving a convex quadratic programming problem. This direction finding subprocedure is essentially insensitive to the dimension of the space on which the problem is defined. Moreover, the method of Pironneau and Polak is known to converge linearly for finite-dimensional convex programs for which the objective function has a positive-definite Hessian near the solution (and for which the functions involved are twice continuously differentiable). In the present paper, the method and a completely implementable version of it are shown to converge linearly for a very general class of finite-dimensional problems; the class is determined by a second-order sufficiency condition and includes both convex and nonconvex problems. The arguments employed here are based on the indirect sufficiency method of Hestenes. Furthermore, the arguments can be modified to prove linear convergence for a certain class of infinite-dimensional convex problems, thus providing an answer to a conjecture made by Pironneau and Polak.     

Carleman estimates for the regularization of ill-posed Cauchy problems

This work is a survey of results for ill-posed Cauchy problems for PDEs of the author with co-authors starting from 1991. A universal method of the regularization of these problems is presented here. Even though the idea of this method was previously discussed for specific problems, a universal approach of this paper was not discussed, at least in detail. This approach consists in constructing of such Tikhonov functionals which are generated by unbounded linear operators of those PDEs. The approach is quite general one, since it is applicable to all PDE operators for which Carleman estimates are valid. Three main types of operators of the second order are among them: elliptic, parabolic and hyperbolic ones. The key idea is that convergence rates of minimizers are established using Carleman estimates. Generalizations to nonlinear inverse problems, such as problems of reconstructions of obstacles and coefficient inverse problems are also feasible.     

A Stochastic/Perturbation Global Optimization Algorithm for Distance Geometry Problems

We present a new global optimization approach for solving exactly or inexactly constrained distance geometry problems. Distance geometry problems are concerned with determining spatial structures from measurements of internal distances. They arise in the structural interpretation of nuclear magnetic resonance data and in the prediction of protein structure. These problems can be naturally formulated as global optimization problems which generally are large and difficult. The global optimization method that we present is related to our previous stochastic/perturbation global optimization methods for finding minimum energy configurations, but has several key differences that are important to its success. Our computational results show that the method readily solves a set of artificial problems introduced by Moré and Wu that have up to 343 atoms. On a set of considerably more difficult protein fragment problems introduced by Hendrickson, the method solves all the problems with up to 377 atoms exactly, and finds nearly exact solution for all the remaining problems which have up to 777 atoms. These preliminary results indicate that this approach has very good promise for helping to solve distance geometry problems.     

焊接过程瞬态温度场与残余应力场

本文根据焊接热传导及热弹塑性的研究现状,对如下两个问题进行了探讨.首先,采用非线性问题线性化的方法对非线性非定常温度场问题的边界元法做了改进,并将其用于焊接热传导分析:其次,提出“等放线膨胀系数法”考虑相变对于应力场的影响,并将其用于焊接热弹塑性分析.实例的数值计算结果与实测数据的对比分析表明本文方法行之有效.     

分析土壤半无限域的一种有限层方法(Ⅱ)——几种特殊情形及算例*

本文就几种特殊情形用作者所研究的一种用于横观各向同性体动力学的有限层法作了简化分析,分别讨论了二维问题、轴对称问题以及静力问题,并推广到介质具有粘性性质的情形.对于轴对称情形,本文还给出两个算例,表明作者所研究的有限层法用于分析半无限域层状土壤介质是可行的,因而为研究土壤与结构相互作用问题提供了一条新途径.     

On Numerov's method for a class of strongly nonlinear two-point boundary value problems

The purpose of this paper is to give a numerical treatment for a class of strongly nonlinear two-point boundary value problems. The problems are discretized by fourth-order Numerov's method, and a linear monotone iterative algorithm is presented to compute the solutions of the resulting discrete problems. All processes avoid constructing explicitly an inverse function as is often needed in the known treatments. Consequently, the full potential of Numerov's method for strongly nonlinear two-point boundary value problems is realized. Some applications and numerical results are given to demonstrate the high efficiency of the approach.     

Reproducing kernel method for singularly perturbed turning point problems having twin boundary layers

A numerical method is proposed for solving singularly perturbed turning point problems exhibiting twin boundary layers based on the reproducing kernel method (RKM). The original problem is reduced to two boundary layers problems and a regular domain problem. The regular domain problem is solved by using the RKM. Two boundary layers problems are treated by combining the method of stretching variable and the RKM. The boundary conditions at transition points are obtained by using the continuity of the approximate solution and its first derivatives at these points. Two numerical examples are provided to illustrate the effectiveness of the present method. The results compared with other methods show that the present method can provide very accurate approximate solutions.