Loading...

Table of Content

    15 March 2018, Volume 22 Issue 1
    My 20 years research on alternating directions method of multipliers
    HE Bingsheng
    2018, 22(1):  1-31.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.001
    Asbtract ( 1772 )   PDF (867KB) ( 1460 )  
    References | Related Articles | Metrics

    My research on ADMM dates back to 1997 when I considered the problems from traffic network analysis. Over the last 10 years, the ADMM based on variational inequalities is widely used in optimization. This paper summarizes our research on ADMM over the last 20 years, particularly, the developments in splitting and contraction methods based on ADMM for convex optimization over the last 10 years. We list the main results as well as the motivations. Our analysis is based on the variational inequalities. All methods mentioned fall in a simple unified prediction-correction framework, in which the convergence analysis is quite simple. A through reading will acquaint you with the ADMM, while a more carefully reading may make you familiar with the tricks on constructing splitting methods according to the problem you met. We should notice that the ADMM originates from ALM and PPA, which are good at utilizing the splitting structure. However, it also inherits the intrinsic shortcomings of these first order methods.

    The bounded parallel-batching scheduling with drop-line jobs to minimize total completion time
    JIU Mingzhu, GAO Yuan, YUAN Jinjiang
    2018, 22(1):  32-41.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.002
    Asbtract ( 1222 )   PDF (622KB) ( 311 )  
    Related Articles | Metrics

    In this paper, we consider the bounded parallel-batching scheduling problem with drop-line jobs to minimize the total completion time. In the problem, a parallel-batching machine can handle up to b jobs simultaneously as a parallel batch, where b is the batch capacity, and the processing time of a batch is equal to the longest processing time of the jobs assigned to it. For drop-line jobs, the completion time of each job is equal to the sum of the starting time of the batch containing the job and the processing time of the job. That is, if a batch B has a starting time S, then the starting time of each job J_j contained in batch B is defined to be S, and its completion time is defined as S+p_j, where p_j is the processing time of job J_j. For our problem, we first study some properties of the optimal schedules. Then, based on these properties, we present a dynamic programming algorithm running in O(n^{b (b-1)}) time.

    A merger and acquisition decision of innovative enterprises based on the undesirable return to scale
    ZHANG Xiaoming, WANG Yingming, SHI Hailiu
    2018, 22(1):  42-54.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.003
    Asbtract ( 1185 )   PDF (1369KB) ( 293 )  
    Related Articles | Metrics

    For innovative enterprises, sustainable innovation is the key to obtain and maintain competitive advantage. However, after ten years of construction and  evelopment of innovative enterprises in China, some enterprises have shown the situation that they can weaken the ability of sustainable innovation, and even can not maintain innovation. According to the existing foundation of innovation and the need for their sustainable development of innovative enterprises, this paper expounds the significance of the merger and acquisition (M & A) as an important way to realize the sustainable innovation. At the same time, a method of M & A decision is proposed, which takes into account the return to scale (RTS) of undesirable output. Firstly, a Generalized Data Envelopment Analysis (GDEA) model and a WY-DEA model with undesirable output are established, which are based on the judgment method of scale income which is limited to the desirable output. Secondly, the Generalized DEA model is used to determine whether the RTS of the weak WY-DEA effective M{\&}A schemes are constant, increasing, decreasing or crowded. Then on the basis of the elimination of the congestion plan, the cross efficiency model is used to select the optimal purchasing party. Finally, a numerical example is given to illustrate the feasibility and advantage of the method.

    Minimizing makespan on two parallel machines with learning effects
    ZHU Zhenglu, LU Xiwen
    2018, 22(1):  55-66.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.004
    Asbtract ( 1165 )   PDF (711KB) ( 350 )  
    Related Articles | Metrics

    The scheduling problem with learning effects on two parallel machines is considered in the paper. The objective is to minimize the makespan. First, we discuss the NP-hardness of this problem. Next, we establish the integer programming model to find the optimal solution. Then, based on the simulated annealing algorithm, we propose an approximation algorithm SA and prove that the algorithm SA converges to global optimal solution with probability 1. Finally, we analyze the performance of the algorithm SA by numerical simulation. The results of numerical simulation show that the algorithm SA can reach 99% of the optimal value, it is an effective algorithm for the problem.

    A semidefinite programming rounding algorithm for correlation clustering problem
    WANG Yishui, XU Dachuan, WU Chenchen
    2018, 22(1):  67-76.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.005
    Asbtract ( 1287 )   PDF (1304KB) ( 325 )  
    Related Articles | Metrics

    This paper considers the correlation clustering problem on general graphs with two types of edge weight. Given a graph G=(V,E) where each edge has two types of weight, we need to cluster the set V, subject to the objective so-called maximize agreements, that is, maximizing the total first type of weight for edges within clusters plus the total second type of weight for edges between clusters. This problem is NP-hard. We use outward rotation technique to improve the previous semidefinite programming rounding 0.75-approximation algorithm. The analysis shows that the new algorithm we provide can not improve the
    approximation ratio 0.75, however, it has better performance for lots of instances.

    Strategic stability of cooperative solutions in infinite stage network games
    WANG Lei, LIN Chong, GU Yan, LIU Cui, GAO Hongwei
    2018, 22(1):  77-86.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.006
    Asbtract ( 1257 )   PDF (591KB) ( 396 )  
    Related Articles | Metrics

    The classical cooperative solutions of cooperative games are not time consistent and lack of strategic stability. The theory of strategic stability of cooperative solutions is studied for infinite stage network games. We build the time consistent imputation distribution procedure to realize the dynamic allocation of the cooperative solution, propose the penalty strategies for coalitions, and provide conditions from which the cooperative solution can be supported by a strong Nash equilibrium. The penalty strategy profile in the game is proved to be a strong Nash equilibrium, which ensures the strategic stability of cooperative solutions. The strategic stability of Shapley value in the repeated prisoners dilemma network game is studied as an application of the theory.

    Existence of Nash equilibria in scheduling game on limited machines with activation cost
    ZHANG Long, ZHANG Yuzhong, BAI Qingguo
    2018, 22(1):  87-96.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.007
    Asbtract ( 1724 )   PDF (532KB) ( 459 )  
    Related Articles | Metrics

    In this paper, we investigate game scheduling of jobs in two kinds of limited number of uniform machines with activation cost. The number of machines with speed 1 and activation cost B in the first category is limited. Similarly, the number of machines with speed a(>1) and activation cost aB in the second category is also limited.  Jobs are served as self-interested players who choose a machine with the objective of minimizing their individual cost without considering other players' cost and the total social cost. A job's cost is composed of its machine's load and its share in the machine's activation cost, which is proportionally shared with respect to its size. We design different algorithms for different cases. Then, every assignment obtained by each different algorithm is proved to be a Nash equilibrium.

     Calculation of the customer's sojourn time distribution function in M/G_N/1 queue with customized services using roots method
    ZOU Xuehua, YU Miaomiao, TANG Yinghui, ZHOU Jie
    2018, 22(1):  97-108.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.008
    Asbtract ( 1158 )   PDF (1294KB) ( 299 )  
    Related Articles | Metrics

    Taking the multilingual convenience service hotline for a practical example, we study the numerical method for calculating the customer's sojourn time distribution function in M/G_N/1 queue with customized service. Firstly, we give the Laplace-Stieltjes (LS) transform of the customer's sojourn time by using the embedded Markov chain technique and Pollaczek-Khintchine formula. Secondly, according to the specific type of customized service time distribution function, we give the rational form of the LS transform that mentioned above. By solving the zeros with negative real parts of the denominator of the rational function, namely, the so-called characteristic roots, we finally give the customer's sojourn time probability distribution function by using the method of partial fraction and residue theory.

    Nonlinear shape registration via constrained implicit  representation
    ZHENG Yang, HU Juan, WANG Yongbo, PENG Yaxin
    2018, 22(1):  109-118.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.009
    Asbtract ( 1136 )   PDF (5658KB) ( 336 )  
    Related Articles | Metrics

    This paper addresses the nonlinear shape registration by using the constrained implicit representation for the shape. First, we adopt the level set of the implicit function to represent the shape and model the shape registration, where a global-to-local strategy is applied. Then, in order to improve the regularity, the scale and the bending constraints are introduced to the global and local parameters respectively. Further, a first order variational model is deduced and solved by the gradient descent method. Finally, the comparison of the proposed algorithm with some state-of-the-art approaches on a variety of data sets validates our better performance.

    The pricing of single-name CDS based on product market and capital market in general equilibrium model
    CHEN Yansheng, ZOU Huiwen, CAI Lixiong, ZHU Qun
    2018, 22(1):  119-128.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.010
    Asbtract ( 1048 )   PDF (1321KB) ( 248 )  
    Related Articles | Metrics

    Sub-prime crisis calls for new pricing model of credit derivatives. So we propose a general equilibrium model with product market and capital market to price single-name CDS, and get the Walrasion equilibrium by means of optimization. It can be found that price of CDS in general equilibrium is mixed with factors of capital market and product market. So, it is not only that factors of capital market could affect price of CDS, but factors including risk-free rate, the output elasticity of capital, default rate and recovery rate. Then we examine the dynamics through quantity constrained equilibria out from Walrasion equilibrium by means of computer simulation, and find that price fluctuates acutely and quantity of transaction shrinks when default risk increases. In the process of pricing CDS with reference entity of Industrial and Commercial Bank of China (ICBC), it is found that each factor might be the key factor which affects price of CDS at different period. Lastly. It also can be found that there might be several problems in pricing system during sub-prime crisis, including adjustment of credit and disconnections of pricing and real economy. It can be considered that pricing of CDS based on product market and capital market in a general equilibrium model could mix cross effects of both market together and provide a direction for pricing of derivative.

    Optimal reinsurance-investment strategies for an insurance company with real estate investment 
    CHEN Shumin, HAO Zhifeng
    2018, 22(1):  129-141.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.011
    Asbtract ( 1041 )   PDF (2524KB) ( 341 )  
    Related Articles | Metrics

    Standing at the viewpoint of the decision maker of an insurance company, this paper investigates the reinsurance-investment strategies for an insurance
    company with option of real estate investment. We assume that the insurance company has the possibility of investing in one real project, which will cost the insurance company a fixed amount of wealth and will bring in a fixed income rate as return. The insurance company may also invest its wealth in a Black-Scholes financial market with one risk-free asset (bond, or bank account) and one risky asset (stock), and may reduce its risk exposure or increase its premium using proportional reinsurance contract. The insurance company's main objective is the minimal ruin probability and the corresponding optimal strategy (including the timing of real investment, proportion of reinsurance and the amount of money invested in risky asset). With methodology of combined stochastic
    control and optimal stopping, we obtain the value function and the optimal strategy explicitly. Finally, we analyze the optimal strategy numerically to illustrate our results. It is shown that: (a) The investment threshold of real project is mainly affected by the project's return; its connection with the cost of the real investment is vague. A higher real ivestment return leads to a lower investment threshold. (b) The real investment threshold is lower in a bear market than that in a bull market.

    Minimum general sum-connectivity index of tricyclic graphs
    QIN Qiannan, SHAO Yanling
    2018, 22(1):  142-150.  doi:10.15960/j.cnki.issn.1007-6093.2018.01.012
    Asbtract ( 890 )   PDF (4192KB) ( 332 )  
    Related Articles | Metrics

     As a new class of molecular topological index, the general sum-connectivity index of graphs is of great value in QSPR/QSAR. The extremal problems of
    trees, unicyclic graphs and bicyclic graphs has got many results, and the research in tricyclic graphs is more complicated. In this paper, by limiting  - 1 \leqslant \alpha  < 0, we study the general sum-connectivity index of tricyclic graphs. Based on the analysis of tricyclic graphs, one kind of graphic transformations is
    constructed. It is pointed out that minimum general sum-connectivity index of tricyclic graphs must be obtained from the seven kinds of graphs. Then, by means of the transformation of the pendent edges, we obtain minimum general sum-connectivity index of tricyclic graphs and characterize the unique extremal graphs.