Operations Research Transactions

Introduction of some algorithms for nonlinear semidefinite programming

LI Jianling, YANG Zhenping, JIAN Jinbao

2016, 20(2): 1-22. doi:10.15960/j.cnki.issn.1007-6093.2016.02.001

Asbtract ( 953 )

PDF (672KB) ( 670 )

References | Related Articles | Metrics

In this paper, some important and effective numerical methods developed in recent years for nonlinear semidefinite programming are introduced, which included augmented Lagrangian methods, sequential semidefinite programming algorithms, sequence of linear equations algorithms and alternating direction multiplier methods. At the end of this paper, some future research perspectives of algorithms for nonlinear semidefinite programming are discussed.

Queue length distribution and numerical calculation of queueing system with delay Min(N,D)-policy

WEI Yingyuan, TANG Yinghui, YU Miaomiao

2016, 20(2): 23-37. doi:10.15960/j.cnki.issn.1007-6093.2016.02.002

Asbtract ( 1093 )

PDF (935KB) ( 467 )

References | Related Articles | Metrics

This paper considers the M/G/1 queueing system under the delay Min(N,D)-policy. By using the renewal process theory, the total probability decomposition technique and the Laplace transform tool, we study the transient and equilibrium properties of the queue length from the beginning of the any initial state, and obtain both the recursion expressions of the Laplace transformation of the transient queue length distribution and the recursion expressions of the steady state queue length distribution. Meanwhile, we present the explicit expression of the additional queue-length distribution. Furthermore, we discuss some special cases, such as N \to \infty, or D \to \infty, or N=1 and P{Y=0}=1 or P{Y=0}=1, respectively. Finally, by numerical examples, we discuss the sensitivity of the steady state queue length distribution towards system parameters, and illustrate the important value of the expressions of the steady state queue length distribution in the system capacity optimum design.

On connected K_{n}-residual graph

DUAN Huiming, LI Yonghong

2016, 20(2): 38-48. doi:10.15960/j.cnki.issn.1007-6093.2016.02.003

Asbtract ( 807 )

PDF (866KB) ( 604 )

References | Related Articles | Metrics

The definition of m-K_{n}-residual graph was raised by P. Erd\"{o}s, F. Harary and M. Klawe. When n\neq 1,2,3,4, they proved that K_{n+1}\times K_{2} is only connected to K_{n}-residual graph which has minimum order. In this paper, we have studied m-K_{n}-residual graph, and obtained some important properties. At the same time, we proved that the connected K_{n}-residual graph of the minimum order and the extremal graph for n=1,2,3,4. When n=1,2, it is the only extremal graph. When n=3,4, we proved just two connected residual graph non isomorphic with the minimum order, so as to thoroughly solve the connected K_{n}-residual graph of the minimum order and extremal graph's problems. Finally we prove that K_{n+1}\times K_{2} is only connected with the minimum order of K_{n}-residual graph, when n\neq 1,2,3,4.

Online hierarchical service scheduling on two identical machines with release times

HOU Liying

2016, 20(2): 49-58. doi:10.15960/j.cnki.issn.1007-6093.2016.02.004

Asbtract ( 1027 )

PDF (599KB) ( 417 )

References | Related Articles | Metrics

This paper considers online scheduling problem on two identical machines under a grade of service, where jobs arrive online over time. The objective is to minimize the maximum completion time. We propose an online algorithm with competitive ratio \frac{7}{4}.

Laplacian spectral characterizations of some classes of multi-cyclic graphs

ZHAI Ruonan, WANG Ligong, DONG Zhanpeng, WANG Zhanqing, MEI Ruoxing

2016, 20(2): 59-68. doi:10.15960/j.cnki.issn.1007-6093.2016.02.005

Asbtract ( 1108 )

PDF (725KB) ( 527 )

References | Related Articles | Metrics

Let G be a simple connected graph. A graph G is called to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G. In this paper, a bicyclic graph \theta_{n}(p_1,p_2,\cdots,p_t) and a m-cyclic graph H_n(m\cdot C_3;p_1,p_2,\cdots,p_t) are defined. It is proved that bicyclic graphs \theta_{n}(p), \theta_{n}(p,q), and tricyclic graphs H_n(3\cdot C_3;p), H_n(3\cdot C_3;p,q) are determined by their Laplacian spectra.

Approximation algorithm for the fault-tolerant facility placement problem with penalties

FANG Rui, LUO Wenchang

2016, 20(2): 69-78. doi:10.15960/j.cnki.issn.1007-6093.2016.02.006

Asbtract ( 756 )

PDF (542KB) ( 489 )

References | Related Articles | Metrics

In the fault-tolerant facility placement problem with penalties, we are given a set of customers and a set of sites, and connection costs between customers and sites. We assume that the connection costs satisfy the metric principle. Each customer has its service demands. We can open an unbounded number of different facilities at each site. Each customer can be either assigned to some different opened facilities in some sites to satisfy its demands or rejected by paying a penalty. The objective is to minimize the total cost of opening facilities and connecting those non-rejected customers to different open facilities, and the reject penalties. In this paper, we formulate the fault-tolerant facility placement problem with penalties as a linear integer programming and give its dual programming. Then we propose a 4-approximation algorithm based on rounding its linear programming and dual programming.

A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming

YANG Yang, LUO Honglin, LUO Huilin

2016, 20(2): 79-87. doi:10.15960/j.cnki.issn.1007-6093.2016.02.007

Asbtract ( 1085 )

PDF (677KB) ( 780 )

References | Related Articles | Metrics

Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming． It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points．Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L)．Numerical analysis are also presented in this paper．Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction．

Second-order characterizations on Benson proper efficient element of set-valued optimization

XU Yihong, YANG Yun

2016, 20(2): 88-96. doi:10.15960/j.cnki.issn.1007-6093.2016.02.008

Asbtract ( 708 )

PDF (456KB) ( 576 )

References | Related Articles | Metrics

This paper introduced a new kind of second-order tangent cone, and related second-order tangent derivative, termed as second-order radial composed tangent derivative. Some properties of second-order radial composed tangent derivative and its relationship to second-order composed tangent derivative are discussed. Sufficient and necessary optimality conditions are established respectively for a Benson proper efficient element of set-valued optimization by second-order radial tangent derivative.

Total transversals in 5-uniform hypergraphs

LIN Yi, NI Zhenyu, SHAN Erfang

2016, 20(2): 97-104. doi:10.15960/j.cnki.issn.1007-6093.2016.02.009

Asbtract ( 1086 )

PDF (533KB) ( 753 )

References | Related Articles | Metrics

Let H=(V,E) be a hypergraph with vertex set V and edge set E. The hypergraph H is k-uniform if every edge of H have size k. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge in H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number \tau_{t}(H) of H is the minimum cardinality of a total transversal in H. For k\geq 2, let b_{k}=\sup_{H\in {\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, where {\mathscr{H}}_{k} denotes the class of all k-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. Recently, Bujt\'as and Henning et al. proved following results: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}. For k\geq 5, b_{k}\leq \frac{2}{7}. What's more, b_{6}\leq\frac{1}{4}, and for k\geq 7, b_{k}\leq \frac{2}{9}. In this paper, we show that b_{5}\leq\frac{4}{15} for 5-uniform hypergraphs and this improves the upper bound of b_{5}.

A kind of inexact parallel splitting method for solving the fairest core in cooperative game

WANG Siqi, XIE Zheng, DAI Li

2016, 20(2): 105-112. doi:10.15960/j.cnki.issn.1007-6093.2016.02.010

Asbtract ( 927 )

PDF (757KB) ( 489 )

References | Related Articles | Metrics

In this paper, considering the characteristics of the core and the Shapley value in cooperative game, we transform the fairest core problem into a separable convex optimization problem with two variable. A kind of inexact parallel splitting method is proposed for solving the fairest core by introducing the operator splitting method framework of structured variational inequalities. Furthermore, the proposed method makes full use of the simple closed convexity of the feasible region in the solved problem, and all sub-problems are easy to be solved inexactly. Finally, some numerical results of a simple example indicate the convergence and validity of this method.

A hybrid bundle method for nonsmooth convex optimization

ZHANG Qingye, GAO Yan

2016, 20(2): 113-120. doi:10.15960/j.cnki.issn.1007-6093.2016.02.011

Asbtract ( 928 )

PDF (515KB) ( 527 )

References | Related Articles | Metrics

A hybrid bundle method for nonsmooth convex optimization problems is proposed. In this method, the next iterate point is obtained by solving a subproblem which is formed by adding proximal term to the objective function and trust region constraint to the feasible region. The proposed algorithm combines proximal bundle method with trust region bundle method and switches between them automatically. Convergence analysis shows that the algorithm we proposed is global convergent. Finally, a numerical example is given to verify the validity of the method we proposed.

Scalarization of weakly C(\varepsilon)-efficient solutions via quasi interior in vector optimization

ZHANG Wanli, XIA Yuanmei, ZHAO Kequan

2016, 20(2): 121-126. doi:10.15960/j.cnki.issn.1007-6093.2016.02.012

Asbtract ( 1081 )

PDF (503KB) ( 455 )

References | Related Articles | Metrics

In this paper, some characterizations of co-radiant sets via quasi interior are obtained. Furthermore, under the nearly C(\varepsilon)-subconvexlikeness, an alternative theorem is established and a linear scalarization result of weakly C(\varepsilon)-efficient solutions via quasi interior is given for a class of vector optimization problems with set-valued maps.

Table of Content