Table of Content

15 December 2019, Volume 23 Issue 4

Previous Issue    Next Issue

From numerical optimization method to learning optimization method

GUO Tiande, HAN Congying

2019, 23(4):  1-12.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.001

Asbtract ( 6637 )   PDF (802KB) ( 1516 )  

References | Related Articles | Metrics

The traditional optimization method based on the gradient solver is mainly the numerical optimization method. It is an iterative solution method combining analytical and numerical calculation and is an optimization method based on fixed mode. The iterative process of the numerical optimization algorithm is essentially the process of nonlinear transformation of the iterative point, which is realized by a series of directions and steps. For every instance of optimization problem, the whole algorithm needs to be executed from the beginning to the end, and the computational complexity is fixed. Once the algorithm is programmed, the efficiency (accuracy and complexity) of the algorithm is fixed. With the development of artificial intelligence, especially deep learning, learning methods have made great success in some fields, such as image recognition (especially face recognition, license plate recognition, handwritting recognition, etc.), network attack prevention, natural language processing, automatic driving, finance, medical treatment, etc. This paper studies the traditional numerical optimization method and intelligent optimization method from a new perspective, analyzes their characteristics respectively. Then we not only propose the learning optimization method but also put forward the design idea of learning optimization method. Finally, we take combinatorial optimization as an example to explain the design principle of this kind of method.

The optimal reinsurance problem towards joint interests of the insurer and the reinsurer with dependent risks

HUAGN Ya, WANG Jing, ZHOU Jieming, DENG Yingchun

2019, 23(4):  13-33.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.002

Asbtract ( 927 )   PDF (1728KB) ( 193 )  

References | Related Articles | Metrics

In this paper, by considering the joint interests of the insurer and the reinsurer, we study the optimal reinsurance problem in a risk model with two dependent classes of insurance business. Assume that the reinsurance company adopts the variance premium principle. The surplus processes of the insurance company and the reinsurance company are both governed by the compound Poisson model as well as by the diffusion approximation model. Under the criterion of maximizing the expected utility, we prove the existence and uniqueness of the optimal reinsurance strategies. By solving the corresponding Hamilton-Jacobi-Bellman equations, closed-form expressions for the optimal reinsurance strategies and the value functions are derived for the two models. Moreover, we also present numerical examples and analysis.

A structural heterogeneity DEA method with containment relationship for efficiency evaluation

CHEN Lei, WANG Yingming

2019, 23(4):  34-44.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.003

Asbtract ( 1096 )   PDF (1009KB) ( 167 )  

References | Related Articles | Metrics

The homogeneity of the index structure is one of the basic assumptions for the data envelopment analysis (DEA) method. However, the complexity of the practical problems always makes this assumption difficult to be fully satisfied. Aiming at the heterogeneous problem of outputs structure with the containment relationship, this paper constructs a phased DEA efficiency evaluation method by analyzing the internal relationship of production structure between decision making units (DMUs). This method takes the subjective preferences of DMUs with different structures into consideration, and avoids the unfairness of traditional DEA method in the process of efficiency evaluation, which has the DMUs with structural heterogeneity. Subsequently, this method is extended to the context of the inputs structure heterogeneity and the multiple structural heterogeneities, respectively. Finally, two examples are used to illustrate the effectiveness and practicability of the method proposed by this paper.

Two-person stochastic game model of data transmission based on slotted ALOHA protocol

XUE Juan, GAO Hongwei, JIANG Hui, ZHOU Yunxun

2019, 23(4):  45-58.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.004

Asbtract ( 959 )   PDF (703KB) ( 129 )  

References | Related Articles | Metrics

Considering a stochastic game model of data transmission in a network of a given topology. Two players (source nodes) try to transmit packages to the destination node through a common node. These packages are divided into important packages and not important packages. Each player has a buffer of limited capacity to store packages. We define a system of cost and reward, and this dynamic conflict control process is modeled as stochastic game with a finite set of states. We study the non-cooperative and cooperative behaviors of players. We calculate the Nash equilibrium under the noncooperative situation. Shapley value is chosen as the solution of the cooperation game. We discuss the subgame consistency of Shapley value and propose a imputation distribution procedure.

Bilinear programming method to solve interval bimatrix games with constrained strategy

XIAO Yan, LI Dengfeng

2019, 23(4):  59-70.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.005

Asbtract ( 1246 )   PDF (562KB) ( 393 )  

References | Related Articles | Metrics

Traditional interval bimatrix game theory is used to study players. strategy selection problems with interval payoff; however, such a theory does not consider players.strategy selection which may be subjected to various constraints. The purpose of this paper is to develop a simple and an effective bilinear programming method to solve the bimatrix game in which players. strategy selection is constrained, and the payoffs are intervals, which is called the interval bimatrix game with constrained strategy. Firstly, the values of players are regarded as functions of the values in the payoff intervals, which are of monotonicity. Therefore, we construct a pair of auxiliary bilinear programming models, which are used to explicitly compute the upper and lower bounds of the interval values of players in any interval bimatrix game by respectively using the lower and upper bounds of the payoff intervals and corresponding optimal strategies. Finally, based on a case of enterprise and government in developing a low-carbon economy in the situation that their strategies are constrained. The effectiveness, advantages, and applicability of the models and methods proposed in this paper are illustrated by comparing these results with those without considering strategic constraints.

A generalized form of fuzzy cooperative game and its solution

YU Xiaohui, DU Zhiping, ZHANG Qiang, ZHOU Zhen, PANG Jinhui

2019, 23(4):  71-85.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.006

Asbtract ( 1018 )   PDF (877KB) ( 172 )  

References | Related Articles | Metrics

Firstly, the crisp cooperative game is extended, and a kind of generalized form for cooperative game with fuzzy coalition is proposed. Three main cooperative games with fuzzy coalition are all contained in this generalized form for cooperative game with fuzzy coalition, that is, the multilinear extension game, the fuzzy game with proportional value and fuzzy game with Choquet integral form. The fuzzy Shapley value for fuzzy game with proportional value and fuzzy game with Choquet integral form are also taken as a kind allocation scheme of cooperative game with fuzzy coalition. However, the fuzzy Shapley for multilinear game is never studied, so in this paper we proposed fuzzy Shapley value by the crisp Shapley value, which is seen as a kind of allocation strategies. Finally, the three cooperative games with fuzzy coalition are analyzed respectively based on an example, and the maximum income game and the optimal allocation strategy are analyzed. The research results in this paper may put a certain decision-making basis for strategic choice of collaborative problem in low-carbon supply chain under uncertainty.

Scheduling problem with time-and-position-dependent effect on two parallel machines environments

GOU Yan, DAI Qin, ZHANG Xingong

2019, 23(4):  86-94.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.007

Asbtract ( 919 )   PDF (562KB) ( 155 )  

References | Related Articles | Metrics

This paper studies parallel-machine scheduling problems with time-andposition effect and maintenance restrictions, which parallel-machine environments are only involved with the identical parallel machines and unrelated machines. The actual processing time of the job is the function of position and time, and machines need to be maintained. Objective function is consisted of total machine load, total completion time and total waiting time. Under unrelated machines, the proposed problem can be solved by transferring into assignment problem, which its time complexity is O(n^k+2/(k-1)!). Under identical parallel machines, the proposed problem can be solved by matching algorithm, which its time complexity is O((2n+m+n log n)n^k-1/(k-1)!).

An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time

LI Ganggang, LU Xiwen

2019, 23(4):  95-104.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.008

Asbtract ( 953 )   PDF (519KB) ( 167 )  

References | Related Articles | Metrics

The single-machine scheduling problem with a period of maintenance to minimize total delivery time has been studied. In this paper, we revisit the problem and propose an algorithm with time complexity of O(n³) to improve the worst-case ratio from 3/2 to 5/4.

On-line bounded-batching scheduling of unit-length jobs with two families

LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao

2019, 23(4):  105-110.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.009

Asbtract ( 1371 )   PDF (531KB) ( 271 )  

References | Related Articles | Metrics

We consider on-line scheduling on a parallel batching machine with two incompatible families of unit-length jobs, where the batch capacity is bounded. In this paper, online means that jobs arrive over time. The objective is to mininize the makespan. In bounded parallel batch scheduling, a finite capacity machine can process b jobs simultaneously as a batch, and the processing time of a batch is equal to 1. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio √17+3/4.

Analysis of a k/n(G) system with expert repairman's multiple vacations and replaceable repair facility

ZHANG Yuanyuan, WU Wenqing

2019, 23(4):  111-123.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.010

Asbtract ( 798 )   PDF (1993KB) ( 157 )  

References | Related Articles | Metrics

This paper studies a repairable k/n(G) system with expert repairman’s multiple vacations and replaceable repair facility. The expert repairman leaves for a vacation when there is no broken component. Once an operating component breaks down during his vacation period, it is repaired immediately by an ordinary repairman. The ordinary repairman becomes inactivated when there is no broken component or the expert returns from his vacation. By using the Markov process theory and the matrix solution method, we obtain the transient and the stationary of the system availability and the rate of occurrence of failures, the system reliability, the mean time to system failure, and the probability that the repair facility is being replaced. Further, we discuss the time-dependent behavior of these reliability measures under different initial states. Finally, special cases of the system are presented to show the correctness of our results.

Pricing of power european options based on Tsallis entropy under stochastic interest rate

WEI Qian, WANG Yongmao

2019, 23(4):  124-130.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.011

Asbtract ( 860 )   PDF (537KB) ( 231 )  

References | Related Articles | Metrics

The randomness of interest and characteristics of fat-tailed, long-term dependence of return distribution of asset prices are considered. Thus, the distribution of Tsallis entropy, which has the characteristics of long-term memory and statistical feedback, is selected to describe the law of the asset prices movement. By using the actuarial approach method under the Vasicek interest rate model, the pricing formulas of power European options are obtained. The formulas not only generalize the classical Black-Scholes conclusion, but also contain the conclusions in the other literature.

Equilibrium analysis in the M/M/1 queue with two types of breakdowns

ZHANG Songtai, XU Xiuli

2019, 23(4):  131-142.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.012

Asbtract ( 920 )   PDF (1849KB) ( 253 )  

References | Related Articles | Metrics

This paper considers the equilibrium behavior of customers in a Markovian queue with two types of breakdowns, where the normal server can get a breakdown at any time. The system does not admit a new arrival once a breakdown happens, and there may exist two independent types of breakdowns: (1) partial breakdown: the server continues to serve the customers on spot at a low rate and is repaired when the system is empty; (2) full breakdown: the server stagnates service and is repaired immediately. When the repair is over, new arrivals will be accepted. Assuming that all the customers have the option of joining or balking in order to maximize their own benefits and basing on a linear reward-cost structure, we analyze the equilibrium joining strategies of the customers and the average social benefits of the system in the fully observable case and the almost unobservable case, respectively. And on this basis, the effect of several parameters on customers’ strategic behavior is presented by some numerical examples.

Optimal production ordering policy for an integrated supply chain with time varying demand

SUN Guanglei, LI Xiaoshen, SHANG Youlin

2019, 23(4):  143-154.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.013

Asbtract ( 977 )   PDF (1192KB) ( 263 )  

References | Related Articles | Metrics

An integrated multi-stage supply chain problem with time varying demand, fixed interval orders and different production cycles over a finite planning horizon is considered in this paper. The objective is to find the retailer’s optimal order cycle and devise the manufacturer’s best production strategy to minimize the total operational cost of the supply chain system. The problem is formulated as a mixed integer nonlinear programming model. The model is solved in two steps: to obtain the optimal production strategy for an order cycle and to determine the optimal order cycle. The method of finding the shortest path in graph theory is used in the first step. Algorithms and programs for the two steps are proposed which are proved to be effective by experiments. The influence of each parameter on the optimal solution and the minimum cost is studied by the examples calculated to illustrate the model.

Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks

HUANG Peihuang, ZHU Wenxing

2019, 23(4):  155-164.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.014

Asbtract ( 826 )   PDF (1712KB) ( 260 )  

References | Related Articles | Metrics

Sweep coverage is an important covering technique in nowaday wireless sensor networks, which deploys mobile sensors to periodically monitor a set of points of interest (POIs), providing a more cost-efficient method to monitor POIs comparing to the traditional covering methods. This paper investigates the Max-Value Sweep Coverage problem on Path (MVSCP), which is to cover a set of POIs over a path using mobile sensors, such that the value sum of the covered POIs attains maximum. This paper first presents an approximation algorithm based on linear programming (LP) randomized rounding technique, in which the problem is first relaxed as a linear program whose fractional optimum solution is then rounded to a solution to MVSCP. The approximation algorithm is with a runtime O(mn^3.5L) and an approximation ratio1-1/e. Then, extending the greedy algorithm for Set Covering, the paper presents an algorithm with a runtime O(m²n²), based on the main idea of repeatly picking the sensor with maximum covered value per unit patrolling range. To reduce the runtime, this paper further improves the runtime of the algorithm to O(m log m+mn²)based on the problem structure of MVSCP. At last, the paper evaluates the practical performance of the proposed algorithms by simulation experiments. The results show that the LP-randomized rounding algorithm is with a much better runtime that is one percent of the exact algorithm based on integral linear programs, but only compromising with slightly lower practical performance. Although without a provably approximation ratio, the improved greedy algorithm has a practical performance as good as the LP-randomized algorithm, while it is with least runtime among all the three algorithms.

A characterization of the position value for hypernetwork situations

LI Siwen, ZHAO Jiagui, SHAN Erfang

2019, 23(4):  165-174.  doi:10.15960/j.cnki.issn.1007-6093.2019.04.015

Asbtract ( 834 )   PDF (602KB) ( 180 )  

References | Related Articles | Metrics

In graph games, Myerson assumed that only connected coalitions achieve fully the worth, but the structures of coalitions are ignored. In 1996, Jackson and Wolinsky generalized the Myerson’s model to “network situation”. The characteristic function is replaced by the value function to reflect the influence of the structures on benefits of feasible coalitions. In this paper we consider hypernetwork situations, which is a natural extension on network situations. It consists of a triple (N, H, v) where (N, H) is a hypernetwork and v is the value function to describe the possible gains from TU-games, whose cooperation is restricted by a hypernetwork. In 2012, van den Nouweland and Slikker characterized the position value axiomatically for network situations by using four axioms. By introducing a new axiom, called partial balanced conference contributions, and combining component efficiency, we propose an axiomatic characterization of the position value for hypernetwork situations. As an immediate corollary, we give a new characterization of the position value for network situations.