Table of Content

15 September 2013, Volume 17 Issue 3

Previous Issue    Next Issue

Original Articles

On atom-bond connectivity index of line and total graphs

2013, 17(3):  1-10. 

Asbtract ( 2085 )   PDF (611KB) ( 926 )  

References | Related Articles | Metrics

The atom-bond connectivity (ABC) index of a connected graph G=(V,E) is defined as ABC(G)=\sum\limits_{uv\in E(G)} \sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}}, where d(u) and d(v) are the degrees of u and u, respectively.  Atom-bond connectivity (ABC) index has been used in the study of the heat  formation in alkanes and the stability and the strain energy of alkane hydrocarbon. We present the lower and the upper bounds on ABC index of line and total graphs, and characterize graphs for which these bounds are tight.

An ODE-based hybrid method based on the nonmonotone technique

LIU Yuanyuan, OU Yigui

2013, 17(3):  11-22. 

Asbtract ( 1483 )   PDF (588KB) ( 856 )  

References | Related Articles | Metrics

In this paper, a new ODE-based hybrid method is proposed for solving unconstrained optimization problems, which combines the idea of IMPBOT algorithm with the nonmonotone line search technique. A main feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step. If the trial step cannot be accepted, a modified Wolfe-type nonmonotone line search is performed to generate a new iterative point, thus avoiding resolving the linear equation system. Under some assumptions, the algorithm is proven to be globally and locally convergent. Numerical results are also reported that show the efficiency of this proposed method.

A decision support system for purchasing and inventory management of oilfield class-A materials

LIU Ruoyang, CUI Jinchuan

2013, 17(3):  23-34. 

Asbtract ( 1758 )   PDF (774KB) ( 717 )  

References | Related Articles | Metrics

In order to provide decision support for the material manager in Chinese Daqing oilfield in making rational purchasing plan to obtain the oilfield materials, considering the practical problems in ''purchasing", ''demand" and ''inventory" and their interactions, such as demand increasing in materials demand, shortage in warehouse capacity, and large growth in purchasing cost, this paper uses forecasting and optimization theory and constructs the decision support prototype system for purchasing and inventory management of oilfield class-A materials, which includes forecasting module, optimization module and adjustment and evaluation module. Furthermore, the numerical simulation using four kinds of materials in Yinlang warehouse shows 10.35%, 8.07% saving rate in 2009 and 2010 respectively. Finally, some improved suggestions on the system have been proposed in large-scale promotion in Chinese Daqing oilfield, such as dealing with the incomplete data, improving the prediction accuracy, designing fast algorithm to solve complicated model and completing the adjustment and evaluation module.

Pebbling numbers of middle graphs of cycles and Graham's conjecture

YE Yongsheng, LIU Fang, ZHAI Mingqing

2013, 17(3):  35-44. 

Asbtract ( 1442 )   PDF (520KB) ( 765 )  

References | Related Articles | Metrics

  A pebbling move on a graph G consists of taking two pebbles off one vertex and placing  one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f(G), is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. For any connected graphs G and H, Graham conjectured that  f(G\times H)\leq f(G)f(H). In this paper, we show  the pebbling numbers of  middle graphs of  cycles, and discuss that Graham^,s conjecture holds for  middle  graphs of some cycles.

Creating an equivalent multi-phases activity network by adding the least dummy activities

SU Zhixiong, QI Jianxun, KAN Zhinan

2013, 17(3):  45-56. 

Asbtract ( 1275 )   PDF (760KB) ( 638 )  

References | Related Articles | Metrics

Network planning can be used to show many difficult problems intuitively in project management, which helps to analyze and solve them. But it also has obvious defects, for example, (1) direction character with no loop of an activity network illuminates that dynamic programming is capable to it, but non-phases of an activity network in generally makes the algorithm cannot be used directly; (2) an activity network which created arbitrarily may be intricate easily in presentation, which leads difficulty to study; (3) the problem of representing activity-on-arc representation network with the least dummy activities is NP-hard, therefore many different activity networks may be created for an activity system, which blocks study on scheduling and planning management, etc. It will help to resolve above problems if transforming an activity network into an equivalent multi-phases network that each activity lies in a corresponding phase. Creating an equivalent multi-phases activity network need to add dummy activities. In this article, we design a method to create the equivalent multi-phases network by adding the least dummy activities to an activity network, which helps to found a more appropriate representation of activity network.

 The restricted connectivity of complete-transposition networks

WANG Guoliang, SHI Haizhong

2013, 17(3):  57-64. 

Asbtract ( 1382 )   PDF (668KB) ( 687 )  

References | Related Articles | Metrics

Complete-transposition networks are a class of important Cayley graphs in networks design. The k-restricted vertex(edge)-connectivity of a graph G is the minimum cardinality of a set of vertices (edges) in G whose removal results in disconnected and each component has at least k vertices, denoted by \kappa_{k}(\lambda_{k}). The k-restricted vertex(edge)-connectivity is one of the most parameters to evaluate the reliability of a network, it is also a refined measure of the fault tolerance of the graph. In general, the larger the k-restricted vertex(edge)-connectivity of a network, the more reliable the network. The paper proves that 2-restricted vertex(edge)-connectivity and 3-restricted vertex(edge)-connectivity of complete-transposition networks, that is, when n\geq4, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6, when n\geq3, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.

Non-smooth optimality conditions for a class of dynamic systems with variable structure

LI Lihua, GAO Yan, WANG Gexia

2013, 17(3):  65-72. 

Asbtract ( 1150 )   PDF (557KB) ( 624 )  

References | Related Articles | Metrics

In this paper, non-smooth optimality conditions for a class of event-driven dynamic systems with variable structure are investigated. By introducing a new time variable, the dynamical optimal problems with variable structure are transformed into classical optimal problems. Based on the knowledge of generalized differential and classical optimal theory, necessary optimality conditions of Frechet superdifferential form for this dynamic system are obtained, which generalize some existing relevant results. It is shown that, in the continuous process of the system, the control variable, the adjoint variable and the state variable satisfy the  adjoint equations and the minimum principles. At the changing instants of the system model, the adjoint variables make certain jump and the Hamiltonian is continuous. At last, one example is given to illustrate the efficiency of the main results.

Review on constraint qualifications and  optimality conditions for mathematical programs with equilibrium constraints

LI Jianling, XIE Qin, JIAN Jinbao

2013, 17(3):  73-85. 

Asbtract ( 2220 )   PDF (632KB) ( 932 )  

References | Related Articles | Metrics

This is a survey on constraint qualifications and optimality conditions for mathematical programs with equilibrium constraints (MPEC for short). Some important international research results on constraint qualifications and the corresponding optimality conditions for MPEC are introduced. The context included are as follows: (1) Some constraint qualifications in common use for MPEC (e.g., MPEC-LICQ, MPEC-MFCQ) and some latest developed constraint qualifications (e.g., constant rank constraint qualifications), and their relationships; (2) Various stationary points for MPEC; (3) Optimality conditions for MPEC. Finally, we discuss some future research perspectives of constraint qualifications and optimality conditions for MPEC.

A dual method for the pose estimation problem

HAN Yingwei, XIA Yong

2013, 17(3):  86-92. 

Asbtract ( 1632 )   PDF (643KB) ( 783 )  

References | Related Articles | Metrics

The pose estimation problem is one of the key problems in computer graphics, machine vision, and photogrammetry. It is to estimate the rotation and translation between a camera and  an object based on  given 3D-to-2D reference points. Recently, with the help of a quaternion model, semidefinite programming relaxation (SDR) and sum-of-square relaxation (SOS) are proposed in literature.  In this paper, by adding redundant constraints to the original problem, we develop a Lagrangian dual model for pose estimation, which can be reformulated as a semidefinite program. We use SeDuMi to solve these three models. They are captured in matrices of 117\times32 (SDR), 266\times70 (SOS) and  81\times 12 (Dual), respectively. Numerical results show that our method is not only fast but also very efficient.

The M/M/1 queue with controlled multiple vacations under Bernoulli policy

ZHANG Hongbo

2013, 17(3):  93-100. 

Asbtract ( 1644 )   PDF (591KB) ( 833 )  

References | Related Articles | Metrics

In this paper, we study an M/M/1 queue with multiple vacation policy under the assumption that the decisions whether or not to take a new vacation and take what kind of vacation depend on certain probability, when the server becomes empty. For the queue model, by the quasi-birth-and-death (QBD) process and matrix geometric method, we derive the analytic expression of the stationary queue length, and demonstrate stochastic decomposition structures of the stationary queue length and sojourn time. Moreover, we also obtain the additional queue length and the additional delay. The results show that the classical M/M/1 queue, the M/M/1 queue with vacation or with working vacation are special cases of our model.

Existence of strong Berge equilibrium under uncertainty

DENG Xicai, XIANG Shuwen, ZUO Yu

2013, 17(3):  101-107. 

Asbtract ( 1560 )   PDF (517KB) ( 619 )  

References | Related Articles | Metrics

 Under the assumption that the domain of the undetermined parameters is known, the existence of strong Berge equilibrium for non-cooperative games and generalized non-cooperative games are investigated. Based on the concept of strong Berge equilibrium and NS-equilibrium for non-cooperative games under uncertainty, the notions of strong Berge equilibrium for non-cooperative games and generalized non-cooperative games under uncertainty are defined. Further, the existence of the equilibrium for non-cooperative games and generalized non-cooperative games are proved by using Fan-Glicksberg fixed point theorem. Finally, a numeric example illustrates the feasibility of the proposed method.

Some conclusions of vertex-distinguishing edge coloring of product graph

MA Gang, MA Xiaomin, YE Jianhua, MA Shaoxian

2013, 17(3):  108-114. 

Asbtract ( 1414 )   PDF (548KB) ( 1147 )  

References | Related Articles | Metrics

A proper edge coloring of graph G is called vertex-distinguishing if the set of colors meets to vertex u differs from the set of colors meets to vertex v for any two distinct vertices u and v. The minimum number k for which there exists vertex distinguishing proper edge coloring using k colors is called the vertex distinguishing proper edge chromatic number. In this paper,  we will obtain a conclusion of vertex-distinguishing edge coloring of product graph by using the method of construction,  and get some results of the vertex-distinguishing edge chromatic numbers of product graphs, then obtain vertex-distinguishing edge chromatic numbers of 25 product graphs,  which satisfy the conjecture on VDECC.

 A preemptive multiprocessor order parallel machine scheduling problem

ZHONG Weiya, MA Wenhui, HUO Zhiming

2013, 17(3):  115-123. 

Asbtract ( 1415 )   PDF (539KB) ( 700 )  

References | Related Articles | Metrics

Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51) study the following problem: there are n orders each of which requests various quantities of the different product types. All the orders are available for processing at time t=0, and preemption is allowed. Order i has a weight \omega_{i} and its completion time is the time when its last requested product type is completed. The goal is to find a preemptive schedule such that the total weighted completion time \sum\limits_{i=1}^n\omega_{i}C_{i} is minimized. They show that this problem is NP-hard and propose a heuristic with worst-case ratio analysis. When reading the proof of Theorem 2 in this paper, we find that some statements are not correct. In this paper, we show that although the proof of Theorem 2 is not valid, the conclusion is still right. Furthermore, we propose an improved approximation algorithm for a special case.

Equivalence on vectorial Ekeland's variational principle in locally convex space

WAN Xuan, ZHAO Kequan

2013, 17(3):  124-128. 

Asbtract ( 1144 )   PDF (488KB) ( 625 )  

References | Related Articles | Metrics

In this paper, based on equivalent formulations of various types of Ekeland's variational principle, we consider the equivalence on vectorial Ekeland's variational principle for monotonically semicontinuous mappings with perturbations given by a convex bounded subset of directions multiplied by the distance function in locally convex spaces. Firstly, by using a vectorial Ekeland's variational principle in locally convex spaces, we present a simple proof of vectorial Caristi-Kirk's fixed-point theorem, vectorial Takahashi's nonconvex minimization theorem and vectorial Oettli-Th\'{e}ra's theorem. Furthermore, we study the equivalence among the vectorial Ekeland's variational principl, the vectorial Caristi-Kirk's fixed-point theorem, the vectorial Takahashi's nonconvex minimization theorem and the vectorial Oettli-Th\'{e}ra's theorem.