Table of Content

15 June 2022, Volume 26 Issue 2

Previous Issue    Next Issue

Equilibrium analysis in the retrial queue with an unreliable server

Yu ZHANG, Jinting WANG

2022, 26(2):  1-15.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.001

Asbtract ( 2646 )   HTML ( 141)   PDF (1036KB) ( 243 )  

Figures and Tables | References | Related Articles | Metrics

This paper studies customers' equilibrium joining strategy in an M/M/1 constant retrial queue with an unreliable server, where the server may break down under the busy and idle states. In this system, there is no waiting space in front of the server. If a customer finds the server idle upon arrival, he occupies the server immediately. Otherwise, if the server is found busy, the customer can choose to leave a message so that the server can search for customers in the retrial orbit who have left messages before in order to serve them when it is free. Once the server breaks down, the customer being served will be squeezed out of the system and new customers are not allowed to join again. According to the different information provided for customers, this paper investigates the system characteristics at steady state and customers' equilibrium joining strategies based on a reward-cost function. Further, the server's revenue and social welfare functions are established. Through comparisons, it is found revealing the queue length may not bring a greater revenue for the server or a larger social welfare.

A stochastic Bregman ADMM with its application in training sparse structure SVMs

Jiahao LYU, Honglin LUO, Zehua YANG, Jianwen PENG

2022, 26(2):  16-30.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.002

Asbtract ( 2710 )   HTML ( 59)   PDF (895KB) ( 336 )  

Figures and Tables | References | Related Articles | Metrics

A new stochastic Bregman multiplier alternating direction method (S-B-ADMM) is proposed for non-convex optimization problems with multiple separable blocks. It is shown that the sequence produced by the S-B-ADMM under the periodic update rule converges asymptotically to a stationary solution of the Lagrangian function of the original problem. Under the random update rule, we prove the almost surely convergence of the sequence produced by the S-B-ADMM. Numerical experiments results illustrate the feasibility of the S-B-ADMM for training sparse structural support vector machines.

An SAA approach for a class of second-order cone stochastic inverse quadratic programming problem

Bo WANG, Li CHU, Liwei ZHANG, Hongwei ZHANG

2022, 26(2):  31-44.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.003

Asbtract ( 2739 )   HTML ( 60)   PDF (829KB) ( 358 )  

Figures and Tables | References | Related Articles | Metrics

In this paper, we consider a class of stochastic inverse quadratic second-order cone programming problem. This stochastic model contains complementarity constraints, and is more proper to model some class of real world problems. By employing the techniques of stochastic sampling and smoothing, we construct auxiliary approximate sub-problems to solve the original model. In addition, we proved that if the solutions of the approximate sub-problems converge, then with probability one the limit is the C-stationary point of the original problem. If strict complementarity condition and the second order necessary condition hold, then with probability one the limit is an M-stationary point. A simple numerical test verified the applicability of our approach.

A Shapley solution for bipartite rationing problems and its application to museum pass problems

Doudou GONG, Genjiu XU, Dongshuang HOU

2022, 26(2):  45-54.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.004

Asbtract ( 2686 )   HTML ( 17)   PDF (816KB) ( 267 )  

Figures and Tables | References | Related Articles | Metrics

Bipartite rationing problem was studied to divide a short supply between resource and sink nodes in a bipartite graph. It had been used to deal with numerous issues in the real world, such as, the allocations of aid relief during natural disasters, utilities like electricity and natural gas, and talents of different types to universities, etc. From the view of marginal contribution of coalitions, this paper proposed the Shapley solution of bipartite rationing problems calculated by linear programming, and characterized it by cooperative game and axiomatization. First, we defined the cooperative game of bipartite rationing problems, called the bipartite rationing game, and proved that the Shapley value of the corresponding cooperative game coincides with the solution we propose. Then, we showed that the Shapley solution is the unique feasible allocation satisfying priority-consistency. Finally, we considered the application of the Shapley solution to museum pass problems, and discussed the allocations of the revenue of single tickets and pass tickets of each participating museum.

Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable

Wenjie LI, Yujing LI, Hailing LIU

2022, 26(2):  55-63.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.005

Asbtract ( 2640 )   HTML ( 17)   PDF (835KB) ( 145 )  

References | Related Articles | Metrics

There are $n$ jobs $J_1, J_2, \cdots, J_n$ to be scheduled on the single machine. Each job $J_{j}$ has a nonnegative arriving time $r_{j}$, a positive processing time $p_{j}$, and a nonnegative weight $w_{j}$. We consider one restricted model: the jobs have agreeable release times and processing times (i.e., if $r_{i}\geq r_{j}$, then $p_{i}\geq p_{j}$). Under this restricted model, we study the single-machine online schedule to minimize the maximum weighted completion time of jobs or the total weighted completion times of jobs. We present two best possible online algorithms with the competitive ratio of both $\frac{\sqrt{5}+1}{2}$.

Modified PRP conjugate gradient method for unconstrained optimization

Huiling ZHANG, Naoerzai SAI, Xiaoyun WU

2022, 26(2):  64-72.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.006

Asbtract ( 2951 )   HTML ( 22)   PDF (823KB) ( 375 )  

Figures and Tables | References | Related Articles | Metrics

Based on the PRP conjugate gradient method, we propose an efficient modified PRP conjugate gradient method for solving large-scaled unconstrained optimization problems by using the structure of the CG_DESCENT conjugate gradient method. The proposed method generates a sufficient descent direction at each iteration, which is independent of any line search. Its global convergence and linear convergence rate are established under standard Wolfe line search. The numerical results show that the proposed methods is effective for the given test problems.

Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection

Chunyan BI, Long WAN, Wenchang LUO

2022, 26(2):  73-82.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.007

Asbtract ( 2597 )   HTML ( 12)   PDF (861KB) ( 211 )  

Figures and Tables | References | Related Articles | Metrics

In this paper, we consider the uniform parallel machine scheduling problem with release dates and job rejection. In this problem, given a set of jobs to be arranged subject to the job release dates, each job is either accepted to process on one of $m$ uniform parallel machines or rejected by paying its rejection penalty. The goal is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. When $m$ is a fixed constant, we provide a pseudo-polynomial time dynamic programming exact algorithm. When $m$ is arbitrary, we derive an approximation algorithm. If the number of accepted jobs is no less than $(m-1)$, then the derived approximation algorithm achieves the performance ratio of 3; otherwise, the derived approximation algorithm achieves the performance ratio of $(2+\rho)$, where $\rho$ is the ratio of the maximum machine processing speed to the minimum machine processing speed. In the end, by a numerical experiment, we illustrate the running way for the derived approximation algorithm.

An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems

Xiaoli HUANG, Yuelin GAO, Bo ZHANG, Xia LIU

2022, 26(2):  83-100.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.008

Asbtract ( 2742 )   HTML ( 14)   PDF (871KB) ( 293 )  

Figures and Tables | References | Related Articles | Metrics

In order to better solve the quadratically constrained quadratic programming problem(QCQP), an adaptive linearized relaxation technique based on the framework of the branch and bound algorithm is proposed in this paper, which theoretically proved that this new delimitation technique is considerable for solving (QCQP). The branch operation in this paper adopts the conditional dichotomy to facilitate effective division of the rectangle; the reduction technique is used to delete some regions that do not contain the global optimal solution to speed up the convergence of the algorithm. Finally, the numerical results show that the proposed algorithm in this paper is effective and feasible.

Population monotonic allocation schemes for shortest path games

Zerong CHEN, Han XIAO

2022, 26(2):  101-110.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.009

Asbtract ( 2723 )   HTML ( 21)   PDF (864KB) ( 192 )  

Figures and Tables | References | Related Articles | Metrics

Population monotonic allocation schemes (PMAS-es for short) are allocation schemes for cooperative games. PMAS-es provide a core allocation for each subgame in a cross monotonic way and hence ensure the dynamic stability of the grand coalition. This paper investigates PMAS-es for cooperative cost games arising from the shortest path problem. We provide a dual-based combinatorial characterization for PMAS-es of shortest path games. Inspired by Maschler scheme for computing the nucleolus, we show that a PMAS can be determined by solving a linear program of exponential size. Moreover, we manage to solve the linear program and derive the same PMAS as the combinatorial method earlier for shortest path games.

Strong edge-coloring of planar graphs

Yuehua BU, Heng ZHANG

2022, 26(2):  111-127.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.010

Asbtract ( 2700 )   HTML ( 14)   PDF (1349KB) ( 188 )  

Figures and Tables | References | Related Articles | Metrics

A strong edge coloring of graph $G$ is on the basis of the proper edge coloring and requiring any two edges at distance at most 2 receive distinct colors, the smallest integer of strong edge coloring called a figure of colors used strong edge chromatic number of $G$. In this paper, the configuration of the minimal counter example is given, and then the power transfer method is used to prove that the strong chromatic index of plane graphs with $g(G)\geq5$, $\Delta(G)\geq6$ and $5$-cycle do not intersect is at most $4\Delta(G)-1$.

Smoothing Newton method for the tensor stochastic complementarity problem

Xiquan SHAN, Meixia LI, Jinyu LIU

2022, 26(2):  128-136.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.011

Asbtract ( 2677 )   HTML ( 10)   PDF (785KB) ( 167 )  

Figures and Tables | References | Related Articles | Metrics

In recent years, more and more people realize that stochastic complementarity problem plays an important role in economic management. Some scholars have extended the stochastic complementarity problem from matrices to tensors and proposed the stochastic complementarity problem of tensors. In this paper, we introduce a class of smooth functions, propose a smooth Newton algorithm, and prove the global and local convergence of the algorithm. Finally, the effectiveness of the algorithm is verified by numerical experiments.

The maximum Laplacian separator of $ k $-cyclic graph

Guidong YU, Zheng RUAN, Axiu SHU

2022, 26(2):  137-142.  doi:10.15960/j.cnki.issn.1007-6093.2022.02.012

Asbtract ( 2607 )   HTML ( 10)   PDF (1098KB) ( 136 )  

Figures and Tables | References | Related Articles | Metrics

Let $ G $ be an $ n $-order $ k $-cyclic graph. The $ k $-cyclic graph is a simply connected graph which the number of edges is equal to the number of vertices adding $ k-1 $. Let $ \mu_{1}(G) $ and $ \mu_{2}(G) $ be the largest eigenvalue and the second largest eigenvalue of the Laplacian matrix of $ G $, respectively. The Laplacian separator of graph $ G $ is defined as $ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $. In this paper, we study the maximun Laplacian separator of $ k $-cyclic graph with given order, and characterize the according extremal graph. The result generalizes the existing conclusions when $ k=1, 2, 3 $.