Table of Content

15 December 2020, Volume 24 Issue 4

Previous Issue    Next Issue

Some advances in theory and algorithms for sparse optimization

ZHAO Chen, LUO Ziyan, XIU Naihua

2020, 24(4):  1-24.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.001

Asbtract ( 5711 )   PDF (949KB) ( 1132 )  

References | Related Articles | Metrics

Sparse optimization is an important class of nonconvex and discountinuous optimization problems due to the involved ℓ₀ norm regularization or the sparsity constraint. It has wide applications arising in many fields including signal and image processing, machine learning, economics and statistics. Over the past ten years, sparse optimization has attracted much attention and has become a hot research topic, with an accumulation of fruitful research achievements. In order to further promote the research in this direction, we mainly summarize and review the research results in theory and in algorithms during the last five years, along with some related important references, so as to dedicate to the readers.

Optimality conditions of generalized convex interval valued optimization problems

LI Jun, CHEN Jiawei, DENG Guangju

2020, 24(4):  25-38.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.002

Asbtract ( 649 )   PDF (663KB) ( 177 )  

References | Related Articles | Metrics

A new interval CW-order relation is introduced in this paper. By the CW-order relation, the interval valued pre-invex, pseudo-invex and quasi-invex functions are introduced, then we established the relationships among these kinds of functions. Finally, under the interval value invexity, the optimal condition of the interval valued optimization problem is established by using the scalarization method.

The synthesis technology and efficiency analysis of multi-level complex index system

CAO Li, MA Zhanxin, MA Shengyun

2020, 24(4):  39-50.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.003

Asbtract ( 684 )   PDF (1133KB) ( 160 )  

References | Related Articles | Metrics

DEA method often leads to multiple units being effective and makes the evaluation results meaningless when evaluating the efficiency of complex systems. It is difficult to find the projection of the original index when these indexes are synthesized into several main indexes. In order to solve the above problems, a DEA model for efficiency evaluation of output-oriented complex systems is presented in this paper. The meanings of DEA validity, model properties and solving methods of the model are discussed. Finally, this method is used to analyze the comprehensive operation efficiency of 14 grade 3A hospitals in Inner Mongolia Autonomous Region.

Research on the quadratic programming model and solution algorithm of critical nodes in metro network

GUO Xiaoling, ZHUANG Yuanxin, LIU Yifan

2020, 24(4):  51-62.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.004

Asbtract ( 607 )   PDF (4630KB) ( 235 )  

References | Related Articles | Metrics

Critical nodes in the metro network have an important impact on their connectivity. Under limited manpower and material resources, it is very important to find out the critical nodes for enhanced management to reduce the damage caused by random failures to the entire network. Comprehensively considering the impact of node removal on the overall structure and function of the weighted network, this paper presents a new measure of computing network connectivity-one-step and two-step connections based on the quadratic constrained quadratic programming model. An genetic algorithm is then designed according to the characteristics of the model. Finally, the Beijing metro network is taken as an example to solve the problem. The results show the effectiveness and superiority of the proposed method.

Non-parameter filled function method for nonlinear integer programming

ZHAO Dan, GAO Yuelin

2020, 24(4):  63-73.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.005

Asbtract ( 511 )   PDF (665KB) ( 169 )  

References | Related Articles | Metrics

In this paper, we proposed a new non-parameter filled function method to solve unconstrained nonlinear integer programming. The filled function we constructed has the same local minimizer with the original objective function, so the computation cost is greatly reduced and the efficiency is improved. In this paper, the numerical experiments of six test functions are carried out, and the results show that the algorithm is effective and feasible.

An axiomatization of the weighted Solidarity value and its program implementation

YANG Hui, XU Genjiu, WANG Wenna

2020, 24(4):  74-82.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.006

Asbtract ( 505 )   PDF (675KB) ( 141 )  

References | Related Articles | Metrics

A new recursive definition of the weighted Solidarity value is provided based on the normalization weight system. The weighted Solidarity value not only supports the vulnerable players in payoff allocation problems, but also evaluates the difference of players and adjusts the degree of protection for the vulnerable participants flexibly applying the weight coefficient. Through defining the weighted symmetry for the expected variation, a new axiomatization for the weighted Solidarity value is proposed in the point of the view of algebra. Ultimately, we design the recursive algorithm to implement the weighted Solidarity value. The rationality of the weighted Solidarity is analyzed through comparing with other classical solutions in an actual case.

Sensitivity for the second-order S-derivative of the perturbation map in set-valued optimization

TANG Wei, YANG Yun

2020, 24(4):  83-92.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.007

Asbtract ( 659 )   PDF (571KB) ( 74 )  

References | Related Articles | Metrics

In this paper, a new kind of second-order contingent derivative is introduced, termed second-order S-derivative. Some properties of second-order S-derivative and the relationship to second-order contingent derivative are discussed. Then, with the help of second-order S-derivative, relationships are established between the minimum of contingent derivative of set-valued maps and contingent derivative of perturbation maps.

Parallel machine scheduling with deteriorating installation times in the MapReduce system

HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming

2020, 24(4):  93-106.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.008

Asbtract ( 551 )   PDF (3069KB) ( 115 )  

References | Related Articles | Metrics

The parallel machine scheduling problem in the MapReduce system with deteriorating effect of installation time and step deteriorating effect of processing time is considered. Each job consists of one map task and one reduce task. The map task can be split and processed on several machines simultaneously, while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed. The processing of reduce task can't be interrupted. We consider the workpiece installation with linear deteriorating effect and processing time with step deteriorating effect on parallel identical machines in the MapReduce system, aiming at minimizing the makespan. We formulate the problem as a mixed integer linear programming model, and give a lower bound of the problem. An improved grey wolf algorithm which uses the simplex difference disturbance mechanism, are proposed to solve the model. Numerical experiments are carried out to demonstrate the efficiency of the MILP and the proposed algorithms, comparing the results of the improved grey wolf algorithm, greedy algorithm and genetic algorithm with the lower bounds of the problem.

Scheduling with tree-hierarchical processing set restrictions

ZHANG Yuzhong, LI Shuguang

2020, 24(4):  107-112.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.009

Asbtract ( 472 )   PDF (606KB) ( 106 )  

References | Related Articles | Metrics

The problem of scheduling with release times, delivery times and treehierarchical processing set restrictions is considered. Each job cannot begin processing before its release time, and its delivery begins immediately after processing has been completed. The machines form a tree hierarchical structure:any job requesting a certain machine may be assigned to any of its ancestors in the tree, and the set of these machines is the job's processing set. The objective is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. A polynomial time approximation scheme (PTAS) is presented when the jobs have both unequal release times and unequal delivery times.

The allocation scheme based on the T-coalition Shapley value

YU Xiaohui, DU Zhiping, ZHANG Qiang, PANG Jinhui

2020, 24(4):  113-127.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.010

Asbtract ( 486 )   PDF (701KB) ( 160 )  

References | Related Articles | Metrics

From the viewpoint of coalition payoff allocation, the definition of Tcoalition is employed. The axioms of T-coalition Shapley value have been proposed. The explicit form of T-coalition Shapley value has also been given, which can be served as the payoff of the whole coalition. The fair axioms of T-coalition are an extension of crisp axioms, and the explicit form of T-coalition Shapley value is also an extension of crisp Shapley value. The properties of the T-coalition Shapley function are discussed. The condition that the cooperative game accepts the partnership is also proposed. This allocation method allows the players to participate the grand allocation in partnership form. Hence, the T-coalition Shapley function can help players to choose cooperative form. Finally, an illustrative example has been given in order to show the decision process based on T-coalition Shapley function.

The second maximum (Laplacian) separator of unicyclic graphs

YU Guidong, RUAN Zheng, SHU Axiu, YU Tao

2020, 24(4):  128-134.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.011

Asbtract ( 500 )   PDF (896KB) ( 138 )  

References | Related Articles | Metrics

Let G be a unicyclic graph of order n, λ₁(G) and λ₂(G) be the largest eigenvalue and second largest eigenvalue of the adjacent matrix of G, μ₁(G) and μ₂(G) be the largest eigenvalue and second largest eigenvalue of the Laplacian matrix of G, respectively. The separator of G is defined as S_A(G)=λ₁(G) -λ₂(G). The Laplacian separator of G is defined as S_L(G)=μ₁(G) -μ₂(G). In this paper, we study the (Laplacian) separator of unicyclic graphs, and give the extremal graphs which attain the second maximum separator and second maximum Laplacian separator respectively.

Cacti with larger Randić index

WANG Yajing, GAO Yubin

2020, 24(4):  135-144.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.012

Asbtract ( 416 )   PDF (2450KB) ( 168 )  

References | Related Articles | Metrics

The Randić index was one of the most important molecular topological indices, and became a popular topic of research in mathematics and mathematical chemistry. The sharp upper and lower bounds of Randić index of trees, unicyclic graphs and bicyclic graphs have been obtained. Furthermore, the minimal graphs of trees, unicyclic graphs and bicyclic graphs on Randić index have been characterized. In addition, the lower bounds of cacti on Randić index and corresponding extremal graphs have been described. In this paper, we analyzed the degrees of vertices of the edges in cacti, defined the symmetric edges and the asymmetric edges, and characterized some transformations. Based on these definitions, we discussed in terms of maximum degree of vertices. In the end, the extremal graphs have been characterized by the asymmetric edges in cacti of n-vertex given the number of circles with the first, the second, the third, the fourth and the fifth maximum Randić index.

The restricted edge-connectivity and λ'-optimality of hypergraphs

TONG Linken, SHAN Erfang

2020, 24(4):  145-152.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.013

Asbtract ( 721 )   PDF (1203KB) ( 138 )  

References | Related Articles | Metrics

Let H=(V, E) be a connected hypergraph consisting of a vertex set V and an edge set E. For S ⊆ E(H), S is a restricted edge-cut, if H\S is disconnected and there are no isolated vertices in H\S. The restricted edge-connectivity, denoted by λ'(H), is defined as the minimum cardinality over all restricted edge-cuts. The edgedegree d_H(e) of an edge e ∈ E(H) is defined as the number of edges adjacent to e, and the minimum edge-degree of H is denoted by ξ(H). The hypergraph H is called λ'-optimal, if λ'(H)=ξ(H). In this paper, we consider the restricted edge-connectivity and λ'-optimality of hypergraphs and generalize some results on the restricted edge-connectivity and λ'-optimality of graphs to hypergraphs.

Optimality characterization of the minimum stretch spanning tree problem for interval graphs

LIN Hao, LIN Lan

2020, 24(4):  153-158.  doi:10.15960/j.cnki.issn.1007-6093.2020.04.014

Asbtract ( 538 )   PDF (772KB) ( 87 )  

References | Related Articles | Metrics

The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adjacent vertices is minimized. This minimum value is called the tree-stretch of G, denoted σ(G). The problem has been proved NP-hard and several upper bounds have been obtained for special graph classes. For example, σ(G) ≤ 3 is known for interval graphs. This paper presents a characterization of interval graphs with σ(G)=k for k=1, 2, 3.