Operations Research Transactions

An alternating direction numerical method for a type of inverse quadratic programming problem

LU Yue, ZHANG Jihong, ZHANG Liwei

2014, 18(2): 1-16.

Asbtract ( 1120 )

PDF (603KB) ( 1053 )

References | Related Articles | Metrics

An alternating direction numerical method for a type of inverse quadratic programming problem is considered, we first give an explicit formula of the solution to the matrix-variable sub-problem, and provide two algorithms for finding an approximate solution to the vector-variable subproblem. One of these two algorithms is based on the fixed point theorem and the other is a semi-smooth Newton method. Numerical experiments show the efficiency and effectiveness of the proposed algorithm for inverse quadratic programming problems.

A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem

XU Dachuan, WAN Wei, WU Chenchen, XU Wenqing

2014, 18(2): 17-28.

Asbtract ( 1016 )

PDF (1193KB) ( 839 )

References | Related Articles | Metrics

In this paper, we consider the two-stage stochastic fault-tolerant facility location problem with uniform connectivity requirement where the clients to be served are only revealed at stage two (thus unknown at stage one). The facilities may be opened at either stage, with possibly different opening costs, depending on the stage and the set of clients to be served (called a scenario). Each client to be served in such a scenario has to be connected to r \geq 1 distinct facilities. Given all possible scenarios and the corresponding probabilities, the objective is to determine two subsets of facilities to be opened at the two stages and to connect the clients in the realized scenario to r distinct opened facilities such that the total expected opening and connection cost is minimized. Based on the special structure of the problem, we offer a primal-dual (combinatorial) 3-approximation algorithm.

Some properties of the expected value model in stochastic data envelopment analysis

LAN Yixin, WANG Yingming

2014, 18(2): 29-39.

Asbtract ( 873 )

PDF (577KB) ( 891 )

References | Related Articles | Metrics

The expected value model in stochastic data envelopment analysis (SDEA) is especially useful for evaluating the efficiency of the decision making units (DMUs) with fixed inputs and stochastic outputs. In this paper, we reinvestigate some properties of this model to extend its potential usage.
In order to identify the type of the DMUs' efficiency of the expected value model in SDEA, we first propose four types of stochastic efficiencies stochastic expected inefficiency, stochastic expected weak efficiency, stochastic expected efficiency and stochastic expected super-efficiency. We, then, develop three propositions to show the relationship between stochastic efficiency and the expected efficiency. Based on the above research findings, we demonstrate two important properties: (1) The stochastic efficiency is an increase function of the significance level when the expected efficiency remains fixed; (2) The stochastic efficiency is an increase function of the expected efficiency when the significance level remains fixed. Finally, we illustrate the above results by using stochastic simulations and a numerical example.

Energy and Hamiltonicity of graphs

YU Guidong, ZHANG Chao, GONG Qijuan

2014, 18(2): 40-48.

Asbtract ( 977 )

PDF (495KB) ( 685 )

References | Related Articles | Metrics

Let G be an undirected simple graph and A(G) be the adjacency matrix of G. This paper gives some sufficient conditions for G to have a Hamiltonian path or cycle or to be Hamilton-connected in terms of eigenvalues of the complement of G, and gives a sufficient condition for a bipartite graph to have Hamiltonian cycles in terms of eigenvalues of its quasi-complement. These results improve some known results.

A new wide neighborhood infeasible interior-point algorithm for semidefinite programming

FENG Zengzhe, ZHANG Xixue, LIU Jianbo$, FANG Liang

2014, 18(2): 49-58.

Asbtract ( 1025 )

PDF (567KB) ( 691 )

References | Related Articles | Metrics

A new infeasible interior-point algorithm for solving semidefinite programming is proposed, based on a new wide neighborhood. Under suitable assumptions, it shows that the algorithm's iterate complexity bound is O(\sqrt{n}L), which is better than the best result O(n\sqrt{n}L) in this class algorithm so far, and is the same as the best known bound of feasible interior point algorithms.

On connected three multiply K_{n}-residual graphs

DUAN Huiming, ZENG Bo, DOU Zhi

2014, 18(2): 59-68.

Asbtract ( 1010 )

PDF (1798KB) ( 601 )

References | Related Articles | Metrics

Erd\"{o}s P, Harary F and Klawe M studied $K_{n}$-residual graphs, and came up with some conclusions and assumptions on $m$-$K_{n}$-residual graphs. In this paper, with the method of including excluding principle and set operations, we studied 3-$K_{n}$-residual graphs and got the formula for calculating the minimum order of 3-$K_{n}$-residual graphs and constructed its extremal graph when the minimum degree is $n$. When $n=2$, the minimum order of 3-$K_{2}$-residual graph is 11, and related extremal graph is constructed. When $n=3$, the minimum order is 20, and two non-isomorphic 3-$K_{3}$-residual graphs are obtained, which doesn't meet the conclusions drawn by Erd\"{o}s, et al. When $n=4$, the minimum order of 3-$K_{4}$-residual graph is 22, and related extremal graph is constructed. Besides when $n=8$, two non-isomorphic 3-$K_{8}$-residual graphs are obtained, and they don't meet the conclusions drawn by Erd\"{o}s, et al. At last, when $n=9,10$, the only extremal graph with minimum order of 48 and 52 respectively validates the conclusions by Erd\"{o}s, et al.

On the crossing number of products of K_3,3 with S_n

OUYANG Zhangdong, HUANG Yuanqiu

2014, 18(2): 69-76.

Asbtract ( 914 )

PDF (980KB) ( 904 )

References | Related Articles | Metrics

Computing the crossing number of a graph is NP-complete. The results of crossing numbers of products of complete bipartite graph with stars are only very scarce up to date. In this paper, the relationship of crossing number for K_{3,3}\square S_n and K_{3,3,n} is established by some new contraction operations. Thus, a new approach to completely determine the crossing number of K_{3,3}\square S_n is provided.

Emergency evacuation model and algorithm with the limited number of rescue equipments

YANG Jianfang, GAO Yan

2014, 18(2): 77-86.

Asbtract ( 1039 )

PDF (1215KB) ( 1073 )

References | Related Articles | Metrics

In real evacuation mission, there might be fewer rescue equipments than the number of available evacuation paths. When this situation occurs, a mathematical model is given with objective function minimizing evacuation time and a k-limited flow control algorithm is designed based on flow velocity in this paper. First the feasible path sets would be calculated by sending the largest possible number of evacuees on the shortest path to the nearest destination, and k-shortest paths from it is regarded as the initial solution. Then the algorithm can be realized by updating network according to the flow velocity, in the same time, the path set with minimal evacuation time should be preserved in each iteration. Finally, a numerical example is presented to show the effectiveness and feasibility of this algorithm.

The research progress of robust portfolio optimization

LIANG Xikun, XU Chengxian, ZHENG Dong

2014, 18(2): 87-95.

Asbtract ( 1467 )

PDF (528KB) ( 1249 )

References | Related Articles | Metrics

This paper reviews the recent progresses and trends of the researches on the robust portfolio optimization. Based on the mean-variance model of portfolio optimization, the history of robust portfolio optimization is looked back. Meanwhile, the research focus of robust portfolio optimization and the present research status at home and abroad are introduced in details. Moreover, some new viewpoints are proposed for future development directions and for some main research contents in the field of robust portfolio optimization so as to provide reference for the related research works in the future.

A ranking method for the assignment problem with mutiple optimal solutions

XU Yisong, WANG Yingming

2014, 18(2): 96-102.

Asbtract ( 1507 )

PDF (492KB) ( 947 )

References | Related Articles | Metrics

In some cases, the optimal solution is not unique. Because the player’s payoff in each optimal solution is different, each player would pursue the optimal solution which can maximize his own payoff to the extent. To resolve this problem, we proposed a bargainging model of the cooperative assignment problem and a compensation function in the perspective of individual rationality. With the bargaining model and the compensation function, we proposed a mehtod to ensure the uniqueness of the assignment problem's optimal solution.

Stochastic orders and aging properties on record values

WU Jintang

2014, 18(2): 103-110.

Asbtract ( 970 )

PDF (488KB) ( 567 )

References | Related Articles | Metrics

This paper studies stochastic orders and aging properties of record values. Any stochastic order on two underlying distributions defined only through the behavior of their distribution functions is proved to be inherited by the usual record values. It is also shown that the expected consecutive increment of usual record values preserves the excess wealth order of the underlying distributions. Aging behaviors of the consecutive increments of a sequence of k-record values are investigated as well.

Bicyclic graph with the maximal Estrada indices

XU Weiwei, WANG Wenhuan

2014, 18(2): 111-118.

Asbtract ( 1125 )

PDF (855KB) ( 865 )

References | Related Articles | Metrics

Let \mathcal{B}^+_{n} be the set of bipartite bicyclic graphs with n vertices. In \mathcal{B}^+_{n}, ordering the graphs in terms of their maximal Estrada indices was considered. With the aid of a relationship between the Estrada index and the largest eigenvalue of the bipartite graphs, we deduce the graphs with the largest and the second largest Estrada indices in \mathcal{B}^+_{n} for n\geq 8.

On axiomatizations of the \tau value for bicooperative quasibalanced games

WU Meirong, SUN Hao, CHEN Hui

2014, 18(2): 119-125.

Asbtract ( 959 )

PDF (486KB) ( 769 )

References | Related Articles | Metrics

There are three options for each participant in bicooperative games which can depict real life accurately. We study the \tau value on the basis of this research, then complete the axiomatizations of the \tau value for bicooperative quasibalanced games. The \tau value is based on the construction of upper bound, gap function and concession vector for bicooperative games.

Table of Content