Table of Content

15 September 2010, Volume 14 Issue 3

Previous Issue    Next Issue

Original Articles

On a Primal-Dual Neural Network for Online Solution of Linear Programming

2010, 14(3):  1-10. 

Asbtract ( 2190 )  

Related Articles | Metrics

 This paper investigates the theory of primal linear-programming (LP) problem and its dual problems, which could be used to develop a kind of recurrent neural network for solving online LP problems as well as kinematic control of redundant manipulators. For example, a so-called usual primal-dual neural network (PDNN) initiated by Tang et al. However, due to the complexity and diversity of duality theory, that PDNN needs to be improved so as to obtain the optimal solution(s) instead of feasible solutions. Computer-simulation results substantiate the efficacy and correctness of the improved PDNN model for online solution of LP problems.

The Minimal Genus of Circular Graph C(n,m)

2010, 14(3):  11-18. 

Asbtract ( 1735 )  

Related Articles | Metrics

The orientable and nonorientable minimal genus of all the circular graphs are given in this paper. In the meanwhile, the strong  minimal genus of some circular graphs are discussed too.

Online Scheduling with Reassignment under  Non-Simultaneous Machine Available Times

Hou Liying, Kang Liying

2010, 14(3):  19-30. 

Asbtract ( 1752 )  

Related Articles | Metrics

In this paper, we consider online scheduling problems on two parallel machines with reassignment under non-simultaneous machine available times. The objective is to minimize the maximum completion time (makespan). We study two different versions and propose the best possible algorithms.

The Elimination Cutwidth Problem for Graphs

ZHANG Zhen-Kun, GAO Feng-Xin

2010, 14(3):  32-40. 

Asbtract ( 1614 )  

Related Articles | Metrics

The graph-searching problem is a well-known $NP-$complete problem in combinatorial optimization. Now we make a restriction on the graph-searching problem that an edge is closed as soon as it is searched and need not be searched again. The problem arises from epidemic prevention,  the maintenance and repairing of pipeline networks, etc. This restrictive graph-searching problem can be transformed into the elimination cutwidth problem for graphs. In this paper, a polynomial-time algorithm and some fundamental properties of elimination cutwidth $EC(G)$ are mainly presented. Also, the relations with other parameters (such as treewidth and pathwidth) and some special graph results are discussed.  

Inexact Newton  Method for  Semismooth Operator  Equations in Banach Space

LIU Jing, GAO Yan

2010, 14(3):  41-47. 

Asbtract ( 1674 )  

Related Articles | Metrics

In this paper, we propose two inexact Newton methods for locally Lipschitzian semismooth function and prove  their local convergence results under some conditions. The present inexact Newton methods could be viewed as the extensions of previous ones with same convergent results in finite-dimensional space.  

A New Vehicle Routing Problem and It's Two Stage Algorithm

WANG Ke-Feng, YE Chun-Ming, TANG Guo-Chun

2010, 14(3):  55-63. 

Asbtract ( 2123 )  

Related Articles | Metrics

In this paper, a new vehicle routing problem, split and simultaneous pickup and delivery vehicle routing problem with time windows constraints (SVRPSPDTW), was provided for the first time under the actual background in the third party logistics of auto parts. Then the mathematic model of this problem and the heuristic algorithm to solve the problem, i.e. two stage algorithm,  was given. In the end, the computational experiment was done based on the modified Solomn's benchmark.

rojected Self-Scaling Symmetric Rank One Quasi－Newton Methods for Nonlinear Monotone Equations

LIU Hao, QIAN Xiao-Yan, NI Qin

2010, 14(3):  64-72. 

Asbtract ( 1966 )  

Related Articles | Metrics

 In this paper, two self-scaling symmetric rank one algorithms  with projection are proposed for solving nonlinear monotone equations. In the two algorithms, a simple  rule in choosing parameters in symmetric rank one is modified and  a cautious update rule is used. Under the condition that the nonlinear  monotone function is Lipschitz  continuous, the global convergence of these two algorithms is proved.  Compared with the same type BFGS algorithms, some preliminary numerical  experiments  are also done. The results indicate that the numerical performance of   SSR1 class algorithms may be competitive with that of the counterparts.

 A Polynomial Time Algorithm for the Economic Lot－size  Problem with Multiple Transportation Channels

BAI Qing-Guo, XU Jian-Teng, ZHANG Yu-Zhong

2010, 14(3):  73-82. 

Asbtract ( 1929 )  

Related Articles | Metrics

For the centralization of management,reduction in cost,and  reinforcement of the competitive advantage,the supplier usually concentrates on production and utsources the transportation of products to a Distribution Center. The Distribution Center decides the modes and the time to transport  according to the demand of the retailer.  Hence the supplier, Distribution Center and the retailer form   a two-echelon supply chain system.  This paper considers the economic lot-size problem of   the two-echelon supply chain in which the transportation modes   are characterized by different all-unit quantity discount cost structures.   Several optimality properties are proposed for this problem,  and a polynomial time algorithm is developed for a special case.  

Simulated Annealing Algorithm for Vehicle Routing  Problem with Time Window under Time-Dependent

YANG Shan-Lin, MA Hua-Wei, GU Tie-Jun

2010, 14(3):  83-90. 

Asbtract ( 2109 )  

Related Articles | Metrics

The vehicle routing problem with time window (VRPTW) is one of the routing optimization problems with capacity and time window constraints. Most of the literatures about it suppose that vehicle's speed is constant and ignore the influence of dynamic factors. We consider the speed as a time-dependent piecewise function, and use simulated annealing algorithm to solve the VRPTW under time-dependent.Experiment results show that the algorithm can solve the problem efficiently.  

Rule of Fictitious Play in the Learning Process  with Incomplete Learning Times

DING Zhan-Wen, CAI Chao-Ying, YANG Hong-Lin, JIANG Shu-Min

2010, 14(3):  91-100. 

Asbtract ( 1938 )  

Related Articles | Metrics

In this paper we have generalized the time frequency of learning in the repeated games to study the problems of strategy converging and utility consistency under the fictitious play rule.  We have showed that in the process of incomplete learning, the strict Nash Equilibria are absorbing for the fictitious play provided they are played by uniform learning and the fictitious play has the property of utility consistency when the learning times are frequent enough and the fictitious play exhibits infrequent switches.

Models to Hedge Whole Period Risks   and Empirical Analysis

2010, 14(3):  101-108. 

Asbtract ( 2143 )  

Related Articles | Metrics

The traditional hedging models only consider the asset risk at the end of hedging period and the information supplied by the sample of assets prices are not fully taken into account. A kind of hedging models,called whole period hedging models, are proposed to fully take the information of assets prices into account and to consider the risks of hedging assets at the whole hedging period. The whole period hedging models control the risks in a stable level during the whole hedging period by minimizing the asset risks of different time periods within the hedging period. Empirical analyses and comparisons are made based on Hu-Shen 300 index and it's simulated stock index future. GARCH curves are presented to show the dynamic ffects of these hedging models. Empirical and comparison results show that the effects of the whole period hedging models are better than those of the traditional hedging models, and that the whole period hedging models can reduce the risks when the hedging is terminated ahead of the hedging period. 

A Filter Algorithm for Minimax Problems

YANG Xiao-Hui

2010, 14(3):  109-121. 

Asbtract ( 1619 )  

Related Articles | Metrics

In this paper, a filiter algorithm is proposed to solve Minimax problems with inequality constrains.  Based on the sequential quadratic programming method, the penalty function is not  required by filter strategy. Under some suitable conditions, the global convergence and superlinear  convergence are obtained. Some numerical results show that the method in this paper is effective.

Extended AS-GN Hybrid Conjugate Gradient Method

YAN Hui, Chen-Lan-Ping

2010, 14(3):  122-128. 

Asbtract ( 1696 )  

Related Articles | Metrics

In this paper, we propose a new algorithm for unconstrained optimization.It makes  Touati-Ahmed and Storey's  and Nocedal and Gilbert's hybrid conjugate gradient methods to be special cases under precise line search.From the construction of the new formula $\beta_{k}$, the   new algorithm satisfies descent  conditions turally. And this property depends neither on the line search used nor on the convexity of the objective function.Under normal conditions, we prove the new method  can ensure the global convergence. Numerical results also show its efficiency.