Table of Content

15 September 2016, Volume 20 Issue 3

Previous Issue    Next Issue

The algorithm and model of pairwise stable networks

ZHEN Mengke, GAO Hongwei, LIU Shuqing, JI Haiqiang

2016, 20(3):  1-10.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.001

Asbtract ( 904 )   PDF (1717KB) ( 643 )  

Related Articles | Metrics

Firstly, by establishing equivalent condition of pairwise stability networks with Jackson-Wolinsky rules, this paper gives an complete algorithm to find pairwise stability network. Secondly, after the introduction of side payments, this paper proofs that the set of pairwise stability network allowing for side payments when adding links is the intersection of the set of pairwise stability network and the set of pairwise stability network allowing for side payments when adding and deleting links. Finally, two explicit pairwise stability network models are considered. Using the algorithm of pairwise stability networks, this paper systematically analyzes this two models’ pairwise stability.

Analysis for a preemptive priority queue with finite capacity

ZHANG Hongbo, ZHOU Gaojun, FENG Pinghua

2016, 20(3):  11-20.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.002

Asbtract ( 668 )   PDF (791KB) ( 383 )  

Related Articles | Metrics

This paper considers an M/M/1 queue that handles arrivals form 2 classes of customers on a preemptive priority basis,  where the lower-priority customers with finite buffering.  The queue model can be described in a quasi-birth-and-death (QBD) process with finitely many phases. By matrix-geometric method,  we get the formula of stationary queue length distribution,  and illustrate the effectiveness of the method by numerical examples.

Approximation algorithms for max cut and  max bisection problems using semi-definite programming relaxations

SUN Ting, LI Gaidi, XU Wenqing

2016, 20(3):  21-32.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.003

Asbtract ( 1261 )   PDF (765KB) ( 479 )  

Related Articles | Metrics

Given an undirected graph with nonnegative weight for each edge, the max cut problem is to partition its vertex set into two parts such that the total weight of crossing edges is maximized. When the optimal solution of its Service Design Package (SDP) relaxation lies in a two-dimension space, Goemans improved the approximation ratio from 0.87856... to 0.88456. Using the Gegenbauer polynomials rounding technique, we obtain an approximation curve depending on the ratio between the optimal value of the SDP relaxation and the total weight,  which has the lowest point 0.88456. We further improve the  approximation ratio curve when the ratio varies from 0.5 to 0.9044. Furthermore, we consider an important variant of the max cut problem, the max bisection problem, in which the equal cardinality constraint for the two parts in the partition is imposed. We also consider the case that the optimal solution of the SDP relaxation for the Max Bisection problem lies in a two-dimension space and obtain a 0.7091-approximation for this variant by using the aforementioned Gegenbauer polynomials rounding technique.

Combining time and position dependent effects on  a single machine subject to maintenance activities

Gou Yan, Zhang Xingong

2016, 20(3):  33-44.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.004

Asbtract ( 812 )   PDF (541KB) ( 472 )  

Related Articles | Metrics

In this paper, we consider combining time and position dependent effects on a single machine subject to deteriorating maintenance activities.  The actual processing time of the job is a function of its position.  We focus on minimizing two classical objectives: the makespan and the sum of the completion times. The proposed two problems can be solved in polynomial time by using the matching algorithm. Finally, the makespan problems can be solved by the group balance principle under some certain conditions.

Gradient-based adaptive quick cuckoo search algorithm

LI Rongyu, LIU Yang

2016, 20(3):  45-56.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.005

Asbtract ( 975 )   PDF (1145KB) ( 497 )  

Related Articles | Metrics

 For the problems of the unbalanced capability between global search and local search of standard cuckoo search (CS) algorithm, a gradient-based adaptive quick cuckoo search (GBAQCS) is proposed. The direction of the step is determined based on the sign of the gradient of the function. On the one hand, the adaptive search strategy is used to balance the global search and local search capability. On the other hand, the current-guided search method is adopted to improve the convergence precision and rate. The simulation experiments show that GBAQCS fully utilizes and balances the global search and local search capability, and greatly improves the convergence speed and quality of solutions compared with other optimization algorithms.

A filled function method based on filter for global optimization with box constraints

HU Quan, WANG Wei

2016, 20(3):  57-67.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.006

Asbtract ( 1059 )   PDF (554KB) ( 517 )  

Related Articles | Metrics

This paper presents a filled function algorithm based on filter technique for the nonconvex global optimization problems with boxed constrains. The filled function method is one of effective methods for solving global optimization problems. And the filter technique is widely used in local optimization algorithm because of its good numerical results. In order to optimize the filled function method, we try to use the filter set to supervise the iteration. In the paper, a new filled function is formulated first and then its necessary characteristics are discussed. Based on that, the algorithm dominated by the filter is proposed and its properties are proved. The numerical results are list at last to show the effectiveness of the algorithm.

The optimality conditions and duality theory for multiobjective semidefinite programming

LI Yongling, YANG Yang, LUO Honglin

2016, 20(3):  68-78.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.007

Asbtract ( 1132 )   PDF (569KB) ( 466 )  

Related Articles | Metrics

This paper aims at the optimality conditions, duality of multiobjective semidefinite programming problems and the optimality conditions for nonconvex  semidefinite programming．We first obtain a necessary and sufficient conditions of KKT condition for nonconvex semidefinite programming, based on this result, the optimality necessary conditions are presented．Furthermore, we discuss the optimality necessary or sufficient conditions for multiobjective semidefinite programming and construct Wolfe dual model for the corresponding problem．Finally, weak and strong duality theorems are established．

The continuity properties of optimal value function  of discrete optimization problems

ZHANG Yuzhong, YANG Xiaoguang

2016, 20(3):  79-84.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.008

Asbtract ( 1155 )   PDF (516KB) ( 443 )  

Related Articles | Metrics

It is undoubtedly significant to study the change rules of the optimal values  of optimization problems, when the set of feasible solutions changes follow some parameters, even if there is no way to get the optimal value generally. For continuous optimization, where the independent variables are numbers or vectors, the characteristics of the optimal value functions following the changing of the variables has been studied extensively, but for discrete optimization problems there is few literature. In this paper some important classical combinatorial optimization problems are considered. We mainly focus on the characteristics of the optimal value functions, here the independent variables are some plans or tours, may not be numbers nor vectors. Parallel scheduling problem, Knapsack problem, Traveling salesman problem are considered in the paper, focusing on  the characteristics of the optimal value functions of these problems if the inputs of parameters are change. Finally, we also consider the characteristics of objective function arised by some famous algorithms such as LPT to  minimize  the makespan of parallel machine schedule.

A class of nonlinear scalarization theorem of vector optimization problems

TANG Liping, YANG Xinmin

2016, 20(3):  85-91.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.009

Asbtract ( 1101 )   PDF (478KB) ( 559 )  

Related Articles | Metrics

In this paper, a class of nonlinear scalarization for vector optimization problem is investigated via Gertewitz functional. We mainly prove the fact that (C, \varepsilon)-weakly efficient solutions or (C, \varepsilon)-efficient solutions of vector optimization problem are equivalent to approximate solutions or strictly approximate solutions of scalar problem, and also  estimate the approximate solutions of this scalar problem.

The clique-coloring  problem in line graphs

LIANG Zuosong

2016, 20(3):  92-98.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.010

Asbtract ( 940 )   PDF (546KB) ( 357 )  

Related Articles | Metrics

A clique is defined as a complete subgraph  maximal under inclusion and having at least two vertices.   A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic.  If G has a  k-clique-coloring, we say that G  is k-clique-colorable. The clique-coloring number  \chi_{C}(G)  is the smallest  integer  k admitting a  k-clique-coloring of G.  In this paper,  we first point out a relation between the clique-coloring number of line graphs of complete graphs  and the generalized Ramsey number. Secondly, we give a polynomial time algorithm for the optimal clique-coloring problem in line graphs of maximum  degree at most 7.

Twin domination in generalized de Bruijn and Kautz digraphs

DONG Yanxia, ZHANG Guang, SHAN Erfang

2016, 20(3):  99-106.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.011

Asbtract ( 996 )   PDF (704KB) ( 374 )  

Related Articles | Metrics

Let G=(V, A) be a digraph with vertex set V and arc set A.  A set T of vertices of G is a twin dominating set of G if for every vertex v\in V(G)\setminus T, there exist u, w\in T (possibly u=w) such that arcs (u,v),(v,w)\in A(G). The twin domination number \gamma^{*}(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we present a new upper bound on the twin domination number of generalized de Bruijn digraphs G_B(n,d) and generalized Kautz digraphs G_K(n,d), which improves the known upper bound in previous literature. For special generalized de Bruijn and Kautz digraphs, we further improve the bounds on twin domination number by directly constructing their twin dominating sets.

Stability to bounded rationality for nonconvexity

WANG Chun, QIU Xiaoling, WANG Nengfa, CHEN Pinbo

2016, 20(3):  107-120.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.012

Asbtract ( 754 )   PDF (616KB) ( 371 )  

Related Articles | Metrics

In recent years, there are many articles about bounded rationality. However, most articles study the properties of bounded rationality under the condition of convexity, and this leads to the limited scope of its application. This paper uses Ekeland variational principle and weaks the assumptions of bounded rationality. Under the condition of nonconvex  we study the stability of bounded rationality model problem. And the solution's stability of the nonconvex Ky Fan point problem, the solution's stability of the nonconvex and noncompact Ky Fan point problem, the solution's stability of the nonconvex Vector-valued function Ky Fan point problem and the solution's stability of the nonconvex and noncompact Vector-valued function Ky Fan point problem are given. As an application, we also give the solution's stability of the nonconvex n-person noncooperative games' bounded rationality model and the solution's stability of the nonconvex multi-objective games' bounded rationality model.

An extended label correcting method for the SUM-MIN bi-criterion path problem in logistics transportation network

HAN Shilian

2016, 20(3):  121-128.  doi:10.15960/j.cnki.issn.1007-6093.2016.03.013

Asbtract ( 680 )   PDF (616KB) ( 390 )  

Related Articles | Metrics

The paper concentrates on the SUM-MIN bi-criterion path problem in the logistics transportation network. An objective aggregation method based on the fuzzy compromise programming technique and an extended label correcting method to solve the aggregated objective are proposed. In the process of aggregating multiple objectives to a single one, the edge evaluation for each objective and the overall evaluation for all the objectives are considered. By assigning the weights to each objective, the decision maker's preference information can be integrated in this aggregation process, and the fuzzy compromise solution can be obtained with the generic aggregation method. Finally, a numerical example shows the solution process of the proposed approach.