凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

A Penalty Approach for Generalized Nash Equilibrium Problem

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach.     

线性分式运输问题的一个解法

线性分式运输问题是线性分式规划问题的一种特殊情况，通常可以用线性分式规划问题的一般解法来解这类问题，本文针对分式运输问题的特点给出了一种简便的解法．     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.      

Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

TWO-GRID CHARACTERISTIC FINITE VOLUME METHODS FOR NONLINEAR PARABOLIC PROBLEMS＊

In this work, two-grid characteristic finite volume schemes for the nonlinear parabolic problem are considered. In our algorithms, the diffusion term is discretized by the finite volume method, while the temporal differentiation and advection terms are treated by the characteristic scheme. Under some conditions about the coefficients and exact solution, optimal error estimates for the numerical solution are obtained. Furthermore, the two- grid characteristic finite volume methods involve solving a nonlinear equation on coarse mesh with mesh size H, a large linear problem for the Oseen two-grid characteristic finite volume method on a fine mesh with mesh size h = O（H2） or a large linear problem for the Newton two-grid characteristic finite volume method on a fine mesh with mesh size h = 0（I log hll/2H3）. These methods we studied provide the same convergence rate as that of the characteristic finite volume method, which involves solving one large nonlinear problem on a fine mesh with mesh size h. Some numerical results are presented to demonstrate the efficiency of the proposed methods.     

基于全局搜索算法的不平衡指派问题研究

目前求解不平衡指派问题的主要是将其转化为平衡的指派问题后再去处理.针对不平衡指派问题提出了全局搜索算法,算法不用将不平衡问题转化为平衡问题进行求解,而是基于全局最优策略对任务进行指派,方法理论更加简单,操作更加方便,使得不平衡指派问题得到了很好地解决,同时,这种算法对平衡指派问题、运输问题等依然有效.     

双人合作的在线雪橇租赁问题

以往的文献只研究了单人雪橇租赁问题,本文将雪橇租赁问题扩展到了双人合作情形.研究了两个在线决策者的合作博弈模型,给出了TBS策略和BCS策略,并求出了双方收益分配的纳什均衡解.结论显示,TBS策略具有最小竞争比,但基于该策略的合作却不稳定,需要契约维持;BCS策略不具有最小竞争比,却是占优策略,基于该策略的合作是稳定的。因此存在合作可能的情况下,选择BCS策略的合作总比非合作要好。文章第4节详细的比较了TBS策略和BCS策略。   此外,文章还得到了一个有意思的发现,随着参与人的增加,竞争比是有可能不上升的.这一发现与经典的在线问题(如k-server问题)的结论不一样,在k-server问题中,随着参与者(服务器)的增加,竞争比会呈线性提高》。     

学生面试问题的分配策略

就学生面试问题中的教师分配策略进行了系统的分析.首先我们分别给出并证明了在面试老师数一定,满足没有两个老师相同以及三个老师相同情形下的,可承担面试学生数的四个上界.然后提出了2种分配算法:排队算法和集合压缩算法,计算结果表明,所提算法可以很好的逼近理论上界.针对文理各半的情形,我们也同样提出并证明了类似的上界,两种分配策略同样适合文理各半的情形.在不分文理和文理各半的两种情况下,我们提出的分配策略都能很好的逼进甚至达到上界,同时也说明了我们理论界是一个很紧的上界.     

On the Computational Complexity of the Minimum Committee Problem

Two special cases of the Minimum Committee Problem are studied, the Minimum Committee Problem of Finite Sets (MCFS) and the Minimum Committee Problem of a System of Linear Inequalities(MCLE). It is known that the first of these problems is NP-hard (see (Mazurov et al., Proc. Steklov Inst. Math., 1:67–101, 2002)). In this paper we show the NP-hardness of two integer optimization problems connected with it. In addition, we analyze the hardness of approximation to the MCFS problem. In particular, we show that, unless NP⊂TIME(n ^O(loglogn )), for every ε>0 there are no approximation algorithms for this problem with approximation ratio (1–ε)ln (m–1), where m is the number of inclusions in the MCFS problem. To prove this bound we use the SET COVER problem, for which a similar result is known (Feige, J. ACM, 45:634–652, 1998). We also show that the Minimum Committee of Linear Inequalities System (MCLE) problem is NP-hard as well and consider an approximation algorithm for this problem.      

A Successive Projection Algorithm for Solving the Multiple-Sets Split Feasibility Problem

The multiple-sets split feasibility problem (MSFP) arises in many areas and it can be unified as a model for many inverse problems where the constraints are required on the solutions in the domain of a linear operator as well as in the operator's range. Some existing algorithms, in order to get the suitable step size, need to compute the largest eigenvalue of the related matrix, estimate the Lipschitz constant, or use some step-size search scheme, which usually requires many inner iterations. In this article, we introduce a successive projection algorithm for solving the multiple-sets split feasibility problem. In each iteration of this algorithm, the step size is directly computed, which is not needed to compute the largest eigenvalue of the matrix or estimate the Lipschitz constant. It also does not need any step-size search scheme. Its theoretical convergence results are also given.     

求解守恒型奇异摄动问题的一个一致收敛高阶方法

本文对守型恒奇异摄动问题(1.1)给出了一个一致收敛的高阶方法.首先将原问题(1.1)转换为二个一阶初值问题(1.4),即(1.1)的解是(1.4)的两个解的线性组合.然后对初值问题(1.4)构造了一个O(hm+1)一致收敛的差分格式.因此由关系式(1.3),我们得到了原问题的一个O(hm+1)一致精度的解,这里m是任意给定的非负整数.最后给出了数值结果.     

The Transmission Problem of Viscoelastic Waves

In this paper we consider the transmission problem of viscoelastic waves. That is, we study the wave propagations over materials consisting of elastic and viscoelastic components. We show that for this types of materials the dissipation produced by the viscoelastic part is strong enough to produce exponential decay of the solution, no matter how small is its size. We also show that the linear model is well posed.     

A strongly polynomial simplex method for the linear fractional assignment problem

In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is strongly polynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton’s method or binary search, no polynomial time bound for the simplex method for LFAP is known.     

Very Large-Scale Neighborhood Search for the K-Constraint Multiple Knapsack Problem

The K-Constraint Multiple Knapsack Problem (K-MKP) is a generalization of the multiple knapsack problem, which is one of the representative combinatorial optimization problems known to be NP-hard. In K-MKP, each item has K types of weights and each knapsack has K types of capacity. In this paper, we propose several very large-scale neighborhood search (VLSN) algorithms to solve K-MKP. One of the VLSN algorithms incorporates a novel approach that consists of randomly perturbing the current solution in order to efficiently produce a set of simultaneous non-profitable moves. These moves would allow several items to be transferred from their current knapsacks and assigned to new knapsacks, which makes room for new items to be inserted through multi-exchange movements and allows for improved solutions. Computational results presented show that the method is effective, and provides better solutions compared to exact algorithms run for the same amount of time. This paper was written during Dr. Cunha's sabbatical at the Industrial and Systems Engineering Department at the University of Florida, Gainesville as a visiting faculty     

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

Stoxes方程初边值问题的Phragmen－Lindelof二择性原理

本文对非定常的Ｓｔｏｋｅｓ方程的初边值问题证明了Ｐｈｒａｇｍｅｎ－Ｌｉｎｄｅｌｏｆ二择性原理，即证明Ｓｔｏｋｅｓ流函数的能量，随着与带状区域有限端距离的增加必定或者按指数率增长或者按指数率衰减．对能量衰减情况建立了Ｓｔｏｋｅｓ流速度的最大模的点点估计．并提出求全能量上界的方法．     

Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based Environment

The buffer allocation problem (BAP) is a well-known difficult problem in the design of production lines. We present a stochastic algorithm for solving the BAP, based on the cross-entropy method, a new paradigm for stochastic optimization. The algorithm involves the following iterative steps: (a) the generation of buffer allocations according to a certain random mechanism, followed by (b) the modification of this mechanism on the basis of cross-entropy minimization. Through various numerical experiments we demonstrate the efficiency of the proposed algorithm and show that the method can quickly generate (near-)optimal buffer allocations for fairly large production lines.     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。