2019 Vol.23

Please wait a minute...


For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails

Select

Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization CHEN Xinbei, ZHU Mingkang, CHEN Jianli Operations Research Transactions    2019, 23 (1): 1-14.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.001 Abstract （756）      PDF（pc） （5439KB）（526）       Knowledge map    Save The gradient hard threshold pursuit algorithm is considered as one of the most effective algorithms for solving sparse optimization problems. Since greedy projection operator affects the performance of the algorithm, it is desirable to propose a better projection algorithm besides the greedy strategies. In this paper, we first formulate the projection problem as an integer programming subproblem. Then, by iteratively solving the subproblem, we obtain a better support set of the sparse optimization problem, thus the original problem is solved to improve the performance of the gradient hard threshold pursuit algorithm. Finally, the convergence of the improved algorithm is proved, and the effectiveness of the algorithm is verified by numerical experiments. Reference | Related Articles | Metrics | Comments（0）

Select

Cross entropy algorithm with multiple important sample level estimation for global optimization problems ZHOU Xinyi, WANG Ke, WU Donghua, WANG Chen Operations Research Transactions    2019, 23 (1): 15-27.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.002 Abstract （1068）      PDF（pc） （668KB）（295）       Knowledge map    Save This paper studies a kind of bounded closed box-constrained global optimization problem. In this paper, we utilize the equivalence relation between the maximum root of the generalized variance function equation and the global minimum value, and the cross-entropy to design the integral level value estimation algorithm for the global optimization. To improve the algorithm, we divide the function values generated by the important sampling techniques into clusters in each iteration according to certain rules. Based on the cross-entropy method to update important samples in each cluster, a new algorithm for global searching with multiple important samples is proposed. One of the advantages of the algorithm is that the preferable function values are selected to achieve a random search for better function value information in each iteration. Meanwhile, multiple important samples make for excavating more and better global information. A series of numerical experiment results show that the algorithm is effective. Reference | Related Articles | Metrics | Comments（0）

Select

Filled function method for solving non-smooth box constrained global optimization problems WANG Weixiang, SHANG Youlin, WANG Duo Operations Research Transactions    2019, 23 (1): 28-34.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.003 Abstract （1080）      PDF（pc） （553KB）（264）       Knowledge map    Save This paper introduces a new filled function method for solving non-smooth box constrained global optimization problems. The constructed filled function contains only one parameter, which could be adjusted readily during the process of the iterations. The theoretical properties of the filled function are analyzed, and a filled function algorithm is designed. Finally, the effectiveness of the proposed algorithm is verified by some numerical calculations. Reference | Related Articles | Metrics | Comments（0）

Select

The optimality conditions of approximate solutions for quasiconvex multiobjective optimization problem CHEN Ruiting, XU Zhihui, GAO Ying Operations Research Transactions    2019, 23 (1): 35-44.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.004 Abstract （860）      PDF（pc） （626KB）（443）       Knowledge map    Save In this paper, we study the optimality conditions of approximate weak efficient solutions and approximate efficient solutions for quasiconvex multiobjective optimization problems. We introduce four concepts of approximate subdifferentials based on the existing subdifferentials of quasiconvex function, and give the relationship among them. And then, we apply these concepts to the quasiconvex multiobjective optimization problems, derive the sufficient conditions and necessary conditions for the approximate weak efficient solutions and the approximate efficient solution, and give some examples to illustrate the main results. Reference | Related Articles | Metrics | Comments（0）

Select

Second-order characterizations for local weakly nondominated points with variable ordering structure XU Yihong, MEI Fang Operations Research Transactions    2019, 23 (1): 45-52.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.005 Abstract （697）      PDF（pc） （437KB）（1834）       Knowledge map    Save A kind of second-order tangent derivatives is introduced, with which a second-order necessary optimality condition is established for set-valued optimization with variable ordering structure in the sense of local weakly nondominated points. Under special circumstances, a first-order necessary optimality condition is obtained. The relationship to second-order contingent tangent derivatives for the sum of two set-valued maps is given under some constraint qualification indued by modified Dubovitskij-Miljutin tangent cones. Further more, a necessary optimality condition is obtained where the objective and constraining functions are considered separately with respect to second-order contingent tangent derivatives. Reference | Related Articles | Metrics | Comments（0）

Select

The best rank-one approximation of the symmetric tensor based on the block circulant matrix XU Jiaojiao, YANG Zhixia, JIANG Yaolin Operations Research Transactions    2019, 23 (1): 53-60.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.006 Abstract （1044）      PDF（pc） （517KB）（217）       Knowledge map    Save In this paper we mainly study the best rank-one approximation problem of a symmetric tensor. This problem plays an important role in our investigation of the tensor. Firstly, we propose a new method to solve the best rank-one approximation problem of a symmetric tensor, which is based on the block circulant matrix of a third-order tensor. Secondly, sufficient and necessary conditions and an estimation of error upper bound are provided for the best rank-one approximation method. Finally, the numerical example is presented to illustrate the feasibility of our approach and the correctness of the error upper bound. Reference | Related Articles | Metrics | Comments（0）

Select

Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine CHEN Qiuhong, ZHANG Xingong Operations Research Transactions    2019, 23 (1): 61-71.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.007 Abstract （725）      PDF（pc） （550KB）（242）       Knowledge map    Save This paper considers two agent scheduling problems with fixed time windows on a single machine. The jobs of the first agent might be preemptive. There exists agreeable condition with release time and due data. The objective function is to minimize the total tardiness. The focus is to find an optimal sequence that minimizes the objective of the first agent, while keeping all jobs of the second agent schedule within fixed time windows. By block principle, we present a pseudo-polynomial time dynamic programming algorithm when fixed time window equals the processing time. If the fixed time windows is larger than the processing time, we give the time complexity of the proposed problem. Reference | Related Articles | Metrics | Comments（0）

Select

Laplacian spectral characterizations of new unicyclic graphs H(p,tK1,m) SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao Operations Research Transactions    2019, 23 (1): 72-80.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.008 Abstract （1002）      PDF（pc） （559KB）（1249）       Knowledge map    Save Let H(p,tK1,m) denote an unicyclic graph with p+mt vertices obtained from Cp by attaching the center of star K1,m to each one of t mutual adjacent vertices of the cycle Cp, respectively. In this paper, we show that the unicyclic graphs H(p,p K1,5) and H((p,(p-1)K1,4) are determined by their Laplacian spectra, and if p is an even number, then the unicyclic graphs H(p, 2K1,4), H(p,(p-2)K1,4) and H(p,(p-3)K1,4) are also determined by their Laplacian spectra. Reference | Related Articles | Metrics | Comments（0）

Select

On the signless Laplacian spectral radius of tricyclic graphs CHEN Yuanyuan, WANG Guoping Operations Research Transactions    2019, 23 (1): 81-89.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.009 Abstract （1262）      PDF（pc） （867KB）（298）       Knowledge map    Save Suppose that the vertex set of a graph G is V(G)={v1,v2,…,vn}. Then we denote by dvi(G) the degree of vi in G. Let A(G) be the adjacent matrix of G and D(G) be the n×n diagonal matrix with its (i,i)-entry equal to dvi(G). Then Q(G)=D(G)+A(G) is the signless Laplacian matrix of G. The signless Laplacian spectral radius of G is the largest eigenvalue of Q(G). In this paper we determine the extremal graph with maximum signless Laplacian spectral radius among all tricyclic graphs of order n. Reference | Related Articles | Metrics | Comments（0）

Select

The least eignvalue of the graphs whose complements are connected and have pendant vertices YU Guidong, SUN Wei, LU Xingting Operations Research Transactions    2019, 23 (1): 90-96.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.010 Abstract （687）      PDF（pc） （1051KB）（233）       Knowledge map    Save The least eigenvalue of the graph is defined as the smallest eigenvalue of adjacency matrix of the graph, which is an important algebraic parameter on characterizing structural property of graphs. In this paper, we characterize the unique graph with the minimum least eigenvalue among all graphs of fixed order whose complements are connected and have pendent vertices, and present the lower bound of the least eigenvalue of such classes of graphs. Reference | Related Articles | Metrics | Comments（0）

Select

The 1-good-neighbor diagnosability of the Cayley graphs UGn generated by unicyclic graphs under the PMC model and the MM* model REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU Operations Research Transactions    2019, 23 (1): 97-103.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.011 Abstract （828）      PDF（pc） （628KB）（259）       Knowledge map    Save Diagnosability of a multiprocessor system is an important study topic. A new measure for fault diagnosis of the system is called g-good-neighbor diagnosability that restrains every fault-free node containing at least g fault-free neighbors. As a famous topology structure of interconnection networks, the Cayley graph UGn generated by unicyclic graphs has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of the Cayley graph UGn generated by unicyclic graphs is 2n-1 under the PMC model for n ≥ 4; the 1-good-neighbor diagnosability of the Cayley graph UGn generated by unicyclic graphs is 2n-1 under the MM* model for n ≥ 5. Reference | Related Articles | Metrics | Comments（0）

Select

An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles CHEN Hongyu, TAN Xiang Operations Research Transactions    2019, 23 (1): 104-110.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.012 Abstract （910）      PDF（pc） （541KB）（287）       Knowledge map    Save An edge-partition of a graph G is a decomposition of G into subgraphs G1, G2,…, Gm such that E(G)=E(G1)∪ E(G2)∪…∪ E(Gm) and E(Gi)∩ E(Gj)=∅ for i≠j. A linear k-forest is a graph in which each component is a path of length at most k. The linear k-arboricity lak(G) of a graph G is the least integer m such that G can be edge-partitioned into m linear k-forests. For extremities, la1(G) is the edge chromatic number χ'(G) of G; la∞(G) representing the case when component paths have unlimited lengths is the ordinary linear arboricity la(G) of G. In this paper, we use the discharging method to study the linear 2-arboricity la2(G) of planar graphs. Let G be a planar graph with neither 5-cycles nor adjacent 4-cycles. We prove that if G is connected and δ(G) ≥ 2, then G contains an edge xy with d(x)+d(y) ≤ 8 or a 2-alternating cycle. By this result, we obtain the upper bound of the linear 2-arboricity of G is ?△/2?+4. Reference | Related Articles | Metrics | Comments（0）

Select

Online batch scheduling problem on uniform machines with agreeable processing times PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei Operations Research Transactions    2019, 23 (1): 111-118.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.013 Abstract （853）      PDF（pc） （590KB）（308）       Knowledge map    Save We study the online batch scheduling problem on two uniform machines, where the batch capacity is unbounded. When the arrival times and the processing times of jobs are agreeable, two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q2|ri < rj⇒ pi ≤ pj, B=∞, on-line|Cmax and Q2|ri < rj⇒ pi ≥ pj, B=∞, on-line|Fmax. Without loss of generality, the speeds of the two machines are assumed to be 1 and s,s ≥ 1. We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+α and 1+1/α, respectively, where α is the positive root of α2+sα-1=0. Moreover, for the former scheduling model, we prove that the competitive ratio of the algorithm is not more than 1.618, when s=1. Reference | Related Articles | Metrics | Comments（0）

Select

The theory and application of nondeterministic selfish routing model DIAO Zhuo Operations Research Transactions    2019, 23 (1): 119-126.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.014 Abstract （588）      PDF（pc） （668KB）（271）       Knowledge map    Save In order to describe the traffic condition in daily life more precisely, based on the classical deterministic selfish routing model, we consider the nondeterministic selfish routing model by introducing uncertainty to each edge's cost function. For the nondeterministic selfish routing model, we take three cost measurement criterions:the risk-averse type (conservatism),the risk-neutral type (rationality) and the risk-seeking type (optimism) which correspond to three different ways of thinking in daily life. Under three different cost measurement criterions, we define the stable strategy (Nash equilibrium strategy). Firstly, we prove that for each instance, the Nash equilibrium strategy always exists and is unique in essence. Secondly, we compare the three different cost measurement criterions, and find a counterintuitive phenomenon:in some instances, the cost under the risk-averse type (conservatism) is smaller than the cost under the risk-seeking type (optimism), which means high risk, low revenue and low risk, high revenue. This is on the contrary to the normal principle of high-risk-high-revenue and low-risk-low-revenue in economics. Based on this phenomenon, we define a paradox called nondeterministic paradox, and prove this paradox is actually a generalization of Braess's Paradox. Finally, we characterize the network which is paradox-free, and prove a single commodity network is nondeterministic-paradox-free if and only if it is series-parallel network. Reference | Related Articles | Metrics | Comments（0）

Select

M/G/1 queueing system with Min(N,D,V)- policy control LUO Le, TANG Yinghui Operations Research Transactions    2019, 23 (2): 1-16.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.001 Abstract （961）      PDF（pc） （2405KB）（184）       Knowledge map    Save In this paper, we consider the M/G/1 queueing system with multiple server vacations and Min(N,D,V) -policy. By using the total probability decomposition technique and the Laplace transformation tool, the transient queue-length distribution and the steady queue-length distribution are discussed. Both the expressions of the Laplace transformation of the transient queue-length distribution and the recursive expressions of the steady queue-length distribution are obtained. Meanwhile, we present the stochastic decomposition result of the steady queue length and the explicit expression of the additional queue length distribution. Furthermore, some special cases are discussed when N→1, D→1, p{V=∞}=1 or p{V=0}=1. Finally, the explicit expression of the long-run expected cost rate is derived under a given cost structure. And by through numerical calculation, we determine the optimal control policy (N*; D*) for minimizing the long-run expected cost per unit time as well as compare with the single optimal N*-policy and the single optimal D*-policy. Reference | Related Articles | Metrics | Comments（0）

Select

A cubic regularization method for solving nonsmooth equations MIAO Xiaonan, GU Jian, XIAO Xiantao Operations Research Transactions    2019, 23 (2): 17-30.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.002 Abstract （1140）      PDF（pc） （583KB）（202）       Knowledge map    Save A cubic regularization method and its convergence for solving a nonsmooth system of equations are studied in this paper. By applying the classical trust region technique, the proposed method is ensured to be globally convergent. When BDregular condition is satisfied and the subproblem is inexactly solved, we analyze the local convergence rate of the nonsmooth cubic regularization method. Finally, the efficiency of our method is verified by numerical results. Reference | Related Articles | Metrics | Comments（0）

Select

Contraction graph method for the interval edge-colorings of graphs TAO Yanliang, HUANG Qiongxiang, CHEN Lin Operations Research Transactions    2019, 23 (2): 31-43.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.003 Abstract （1076）      PDF（pc） （1678KB）（140）       Knowledge map    Save An edge-coloring of a graph G with colors 1, 2,…, t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integer. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. For a graph G∈N, the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W (G), respectively. In this paper, we introduce a contraction graph method for the interval edge-colorings of graphs. By using this method, we show that w(G)=△(G) or △(G) + 1 for any bicyclic graph G∈N. Moreover, we completely determine bicyclic graphs with w(G)=△(G) and w(G)=△(G) + 1, respectively. Reference | Related Articles | Metrics | Comments（0）

Select

Optimal investment strategy for the DC pension fund with Stein-Stein volatility and dynamic VaR constraint SUN Jingyun, TIAN Lina, CHEN Zheng Operations Research Transactions    2019, 23 (2): 44-56.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.004 Abstract （924）      PDF（pc） （2552KB）（159）       Knowledge map    Save In this paper, we consider the optimal asset allocation problem for the defined contribution pension plan on the phase of accumulation before retirement. We assume that the pension fund can be invested into a financial market consisting of a risk-free asset and a risky asset who's price process satisfies Stein-Stein stochastic volatility model. By using the method of stochastic optimal control, we obtain the optimal investment strategy of the pension fund without or with dynamic value at risk constraint aiming to maximize the expected utility of relative wealth at retirement time, and derive the corresponding analytic expression of the optimal value function. Finally, a numerical example is provided to verify the related theoretical results and the sensitivity of the optimal investment strategy on some parameters is analyzed. Reference | Related Articles | Metrics | Comments（0）

Select

Fluid models driven by a working vacation-queue with PH-service time distribution WANG Huining, XU Xiuli Operations Research Transactions    2019, 23 (2): 57-66.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.005 Abstract （1203）      PDF（pc） （939KB）（120）       Knowledge map    Save This paper is concerned with the fluid model which is driven by a PHservice time and single-server queue with server working vacation. To analyze the fluid model, we first establish the stationary distribution of the queue length process. Based on the steady-state distribution, then the matrix-type ordinary differential equation is obtained for the joint distribution characterizing the fluid model dynamics. With the help of the Laplace transform (LT) and the Laplace-Stieltjes transform (LST), as usual, the probability for the system empty and the average fluid level are given. An application of these obtained results to the mobile Ad Hoc networks is provided. The sensitivities about the system primitive parameters to the performance measures such as the average fluid level are discussed by some numerical experiments. Reference | Related Articles | Metrics | Comments（0）

Select

Scheduling with sub-jobs' due dates ZHONG Weiya, YANG Ruoyao Operations Research Transactions    2019, 23 (2): 67-74.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.006 Abstract （1067）      PDF（pc） （500KB）（137）       Knowledge map    Save In this paper, we study a single machine scheduling problem in which sub-jobs have due dates. Given a set of jobs, each job is divided into several sub-jobs and each sub-job has a due date. A job is completed on time only if all its sub-jobs are completed before their due dates. We prove that even if each job has two sub-jobs, this problem is NP-hard and there is no FPTAS for this special case. Furthermore, we propose two heuristics for this model and a heuristic to get an upper bound and carry out numerical experiments to compare their performances. Reference | Related Articles | Metrics | Comments（0）

Select

Algorithm design and the fair incentive mechanism in Chinese college admissions matching market LI Jianrong Operations Research Transactions    2019, 23 (2): 75-85.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.007 Abstract （1143）      PDF（pc） （575KB）（2030）       Knowledge map    Save This paper, using matching game theoretic methods, studies the algorithm design and the fair incentive mechanism in Chinese college admissions market. Based on the admissions procedure, we design the Chinese college admissions algorithm, which we proved is feasible. We prove that every stable allocation can be produced by a Nash equilibrium, but not vice versa. We demonstrate the relationship between fairness and stability, and prove that stability implies fairness but not vice versa. Then we construct a (Gale and Shapley) deferred-acceptance algorithm in our market and show that it is both stable and strategy-proof. Therefore, it is a fair incentive mechanism. Reference | Related Articles | Metrics | Comments（0）

Select

A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem LIANG Renli, BAI Yanqin Operations Research Transactions    2019, 23 (2): 86-94.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.008 Abstract （749）      PDF（pc） （873KB）（165）       Knowledge map    Save Logistic regression is a promising method that has been used widely in many applications of data mining, machine learning, computer vision. In this paper, we study on the l0 sparse logistic regression problem. This problem has been proposed as a promising method for feature selection in classification problems, and it is in general NP-hard. In order to solve this problem, we develop a splitting augmented Lagrange method with embedding BB (Barzilai and Borwein) method (SALM-BB). At each iteration, SALM-BB solves an unconstrained convex subproblem and a quadratic programming with l0 constraint. We use BB method to solve the unconstrained convex subproblem. For the quadratic programming subproblem, we obtain its exact optimal solution directly. Furthermore, we prove the convergence of SALM-BB, under certain assumptions. Finally, we implement SALM-BB on the l0 sparse logistic regression problem based on the simulation data and the data of University of California, Irvine, Machine Learning Repository. Numerical results show that SALM-BB outperforms the well-known first-order solver SLEP in terms of lower average logistic loss and lower misclassification error rate. Reference | Related Articles | Metrics | Comments（0）

Select

A class of generalized mond-weir type duality theory for mathematical programs with equilibrium constraints GAO Leifu, YAN Tingting Operations Research Transactions    2019, 23 (2): 95-103.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.009 Abstract （854）      PDF（pc） （483KB）（152）       Knowledge map    Save In this paper, considering the mathematical programs with equilibrium constraints is difficult to meet the constrained qualification and difficult to solve, we establish a class of generalized Mond-Weir type duality of equilibrium constrained optimization problem. Using the S-stability, we propose the duality theory, which is based on the dual form of standard nonlinear programming proposed by Mond and Weir. The theory provides a new method for solving the problem of equilibrium constraint optimization. Under the condition of Hanson-Mond generalized convexity, the weak duality, strong duality and strict inverse duality theorems are proposed by using the sublinear function, and the corresponding proofs are given. The generalization of the dual method provides a theoretical basis for studying the solution of the mathematical programs with equilibrium constraints. Reference | Related Articles | Metrics | Comments（0）

Select

Path-transformation graph of maximum matchings LIU Yan, LEI Mengxia, HUANG Xiaoxian Operations Research Transactions    2019, 23 (2): 104-112.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.010 Abstract （490）      PDF（pc） （860KB）（177）       Knowledge map    Save The path-transformation graph of maximum matchings of a graph G, denoted by NM(G), is a graph where vertices are maximum matchings of G and two maximum matchings M1 and M2 are adjacent in NM(G) if the symmetric difference of M1 and M2 induces a path (there is no limit for the length of the path). In the paper, we study the connectivity of the transformation graph, and obtain the necessary and sufficient condition that the transformation graph is a complete graph or a tree or a cycle, respectively. Reference | Related Articles | Metrics | Comments（0）

Select

The linear aboricity of planar graphs with 6-cycles containing at most one chord LUO Zhaoyang, SUN Lin Operations Research Transactions    2019, 23 (2): 113-119.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.011 Abstract （502）      PDF（pc） （599KB）（111）       Knowledge map    Save The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, using the discharging method, it is proved that for a planar graph G, la(G)=「△(G)/2」 if △(G) > 7 and every 6-cycle of G contains at most one chord. Reference | Related Articles | Metrics | Comments（0）

Select

Two sufficient conditions for maximally restricted-edge-connected hypergraphs PEI Jianfeng, LIN Shangwei Operations Research Transactions    2019, 23 (2): 120-126.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.02.012 Abstract （1836）      PDF（pc） （622KB）（142）       Knowledge map    Save The restricted edge-connectivity of a graph is a generalization of the classical edge-connectivity, and can be used to accurately measure the fault tolerance of networks. Maximally restricted-edge-connected graphs are a class of graphs with optimal restricted edge-connectivity. In this paper, we first extend the concepts of the restricted edge-connectivity and the minimum edge degree to r-uniform and linear hypergraphs H, prove that the minimum edge degree ξ(H) of H is an upper bound on its restricted edge-connectivity λ'(H) if its minimum degree δ(H) ≥ r + 1, and call the hypergraph H with ξ(H)=λ'(H) a maximally restricted-edge-connected hypergraph. Next, we show that an r-uniform and linear hypergraph H with order n and minimum degree δ(H)≥n-1/2(r-1) + (r-1) is maximally restricted-edge-connected. Finally, we prove that an r-uniform and linear hypergraph H with diameter 2 and girth at least 4 is maximally restricted-edge-connected. These results are generalizations of corresponding results in graphs. Reference | Related Articles | Metrics | Comments（0）

Select

The load balancing problem ZHANG Guochuan, CHEN Lin Operations Research Transactions    2019, 23 (3): 1-14.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.001 Abstract （1800）      PDF（pc） （668KB）（640）       Knowledge map    Save Since the seminal paper on load balancing by Ron Graham in 1960's, parallel machine scheduling, served as the very first problem in approximation algorithms of combinatorial optimization, has attracted a great attention. The improvement on load balancing has also witnessed the birth and grow of the research field. In this paper we will present a brief state-of-art of this fundamental problem. In particularly we will introduce several achievements made by our group, which offer some insights on the approximability and hardness from different angles. A couple of potentially interesting questions will be posed as well. Reference | Related Articles | Metrics | Comments（0）

Select

Linear relaxation solution based heuristics for a class of multi-product facility location problems YANG Muming, HUANG Yakui, DAI Yuhong Operations Research Transactions    2019, 23 (3): 15-26.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.002 Abstract （1857）      PDF（pc） （4129KB）（802）       Knowledge map    Save The multi-product facility location problem is an important but difficult class in facility location problems, which allows that customers have demand for different products. When solving large scale problems, commercial solvers hardly achieve high quality solutions in a reasonable time. In this paper, the general form of the uncapacitated single-source multi-product facility location problem is studied and two heuristic methods are proposed for this problem. Based on the linear relaxation optimal solution of the original problem, the two methods can provide a feasible upper bound via solving a compact problem and local search techniques, respectively. Through the theoretical analysis, it is guaranteed that these two methods can be implemented on any feasible instances. Numerical results show that the heuristic methods can significantly improve the performance of the commercial solver for solving this kind of problem. Reference | Related Articles | Metrics | Comments（0）

Select

Selective maintenance optimization: research advances and challenges CHEN Yiming, JIANG Tao, LIU Yu Operations Research Transactions    2019, 23 (3): 27-46.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.003 Abstract （1602）      PDF（pc） （2853KB）（367）       Knowledge map    Save In many industrial and military environments, systems are required to execute a sequence of missions with a finite break between every two adjacent missions. During a break, failed or aged components can be repaired to ensure the success of the subsequent missions. However, due to limited maintenance resources, such as budget, time, manpower, and repair facilities, it is usually impossible to perform all the desirable maintenance actions in each break. Under such a circumstance, selective maintenance, as a particular maintenance strategy, can be implemented to identify a subset of feasible maintenance actions among all the feasible maintenance actions to ensure the success of the subsequent missions. In this paper, the definition and basic model of selective maintenance are presented. Diverse selective maintenance strategies from various perspectives are summarized. The challenges and prospective directions for further research are also discussed. Reference | Related Articles | Metrics | Comments（0）

Select

Two optimization problems in wireless communication system design and related optimization methods LIU Yafeng Operations Research Transactions    2019, 23 (3): 47-62.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.004 Abstract （1152）      PDF（pc） （1384KB）（382）       Knowledge map    Save Many problems arising from wireless communication system design can be formulated as optimization problems. On the one hand, these optimization problems are often non-convex and highly nonlinear and thus are difficult to solve; on the other hand, these problems have their own special structures such as (hidden) convexity and separability. Recently applying mathematical optimization methods to solve/deal with these problems while judiciously taking care of their special structures is a hot research topic. This (survey) paper aims to introduce two optimization problems in wireless communication system design, max-min fairness linear transceiver design problem and MIMO detection problem, and related optimization methods. This paper will focus on the above two problems and overview recent advances of applying mathematical optimization techniques to solve/deal with them by exploiting their special structures. Reference | Related Articles | Metrics | Comments（0）

Select

Introduction to high-order optimization methods ZHU Xihua, CHANG Qingqing, JIANG Bo Operations Research Transactions    2019, 23 (3): 63-76.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.005 Abstract （1215）      PDF（pc） （638KB）（292）       Knowledge map    Save High-order methods are the recently developed optimization algorithms of using high-order information in the process of iteration. The high-order methods often have lower iteration complexity yet a harder subproblem to solve comparing to first-order methods. In this paper, we mainly surveyed three high-order methods including accelerated tensor method, the optimal tensor method, and the ARp method. The solution methods of the subproblems associated with those methods are discussed as well. Hopefully, the interested readers will pay more attention to this research topic by reading the recent advances of high-order methods summarized in this paper. Reference | Related Articles | Metrics | Comments（0）

Select

A survey on rainbow matchings in graphs and hypergraphs LI Tong, WANG Guanghui, ZHOU Wenling Operations Research Transactions    2019, 23 (3): 77-90.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.006 Abstract （1055）      PDF（pc） （732KB）（409）       Knowledge map    Save A hypergraph H=(V, E) is a two-tuple (V, E), where the element in the hyperedge set E is a non-empty subset of the vertex set V. Therefore, the graph is a special hypergraph, and the hypergraph can also be regarded as a generalization of the general graph. In particular, if the elements in the hyperedge set E are all a k-subset of the vertex set V, then the hypergraph is said to be k-uniform. Usually, for the sake of simplicity, we will also refer to the hyperedge as the edge. A matching in a graph (hypergraph) refers to a collection of mutually disjoint edges in a graph (hypergraph). There are two ways to define a rainbow matching:one is a collection of mutually disjoint edges with different colors in an edge-colored graph(hypergraph); the other one is a collection of mutually disjoint edges with different colors, where each edge is from different edge-colored graphs(hypergraphs). This paper mainly introduces the results related to rainbow matchings in graphs and hypergraphs. Reference | Related Articles | Metrics | Comments（0）

Select

Two-stage stochastic non-cooperative multi-vendor game under the transportation network-based on stochastic variational inequarity HOU Lina, SUN Hailin Operations Research Transactions    2019, 23 (3): 91-108.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.007 Abstract （1378）      PDF（pc） （2975KB）（344）       Knowledge map    Save In this paper, we discuss the two-stage stochastic non-cooperative game of manufacturers with production, transportation and sales under stochastic market environment. Firstly, we establish a model of the two-stage stochastic non-cooperative game, and then transform it into a two-stage stochastic variational inequality (SVI). Under mild assumptions, it is proved that there exists an equilibrium solution to the game problem, and it is solved by Progressive Hedging Method (PHM). Finally, the market behavior of manufacturers is analyzed and studied by changing the distribution of random variables and cost parameters in the model. Reference | Related Articles | Metrics | Comments（0）

Select

A review of optimal transport in image processing MA Litao, BIAN Wei Operations Research Transactions    2019, 23 (3): 109-125.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.008 Abstract （1879）      PDF（pc） （2991KB）（563）       Knowledge map    Save The optimal transport problem which has attracted wide attentions in many fields in recent years, is a special kind of optimization problem discussed in the probabilistic measure space. In order to overcome the disadvantages of traditional optimal transport models, such as complex computation and lack of regularity, many different kinds of improved optimal transport models and algorithms are proposed to deal with various practical problems. Firstly, this paper briefly describes the basic theory and methods of optimal transport, and further introduces the concept of Wasserstein distance and Wasserstein barycenters. And then, the discrete optimal transport model and the improved regularization models are discussed. Besides, a short summary of the algorithms to solve optimal transport problem is given. Then, from Wasserstein distance aspect, a review of applications in several areas of image processing is briefly discussed. At last, the further research work is prospected. Reference | Related Articles | Metrics | Comments（0）

Select

The risk-reward model of the online time series search problem ZHANG Wenming, CHENG Yongxi, RU Shaofeng Operations Research Transactions    2019, 23 (3): 126-134.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.009 Abstract （1117）      PDF（pc） （3268KB）（169）       Knowledge map    Save The risk-reward model of the time series search problem is promoted under the assumption that the future can be partially forecasted, where an optimal strategy is presented. Moreover, the variations of the reward function with the parameters are studied by numerical computation, which show that the reward first increases and then is convergent as the risk tolerance and the lower limit of the expectation interval rise, respectively, and increase as the expectation probability rises and the upper limit of the expectation interval declines, respectively. The results enrich the theory of online time series search and are valuable in application. Reference | Related Articles | Metrics | Comments（0）

Select

Some notes on the divergence example for multi-block alternating direction method of multipliers CHEN Caihua Operations Research Transactions    2019, 23 (3): 135-140.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.010 Abstract （1382）      PDF（pc） （469KB）（356）       Knowledge map    Save Recently, multi-block alternating direction method of multipliers (ADMM) has been widely used in signal processing, image processing, machine learning, engineering calculation and so on. However its convergence had been ambiguous for a long time. In 2016, Chen Caihua, et al. gave a counter-example constructed by a threedimensional linear equations to illustrate the possible convergence of multi-block ADMM. In this paper we discuss three related issues in the light of the results Chen's:1) is the divergence of the counter-example due to the initial point selection? 2) is the divergence of the counter-example due to its singleton feasible region? 3) Whether it is possible to introduce a problem-independent step-length in the dual update γ ∈ (0, 1] such that the small step-size ADMM variant converges? In theory, the paper gives negative answers to the first two questions, and we prove that when the initial point is randomly selected, there is an example where the feasible region is not a singleton such that the multi-block ADMM is divergent with probability of 1. The third problem is negated numerically and we show that even if the step-size is γ=10-8, the multi-block ADMM can still diverge. Reference | Related Articles | Metrics | Comments（0）

Select

From numerical optimization method to learning optimization method GUO Tiande, HAN Congying Operations Research Transactions    2019, 23 (4): 1-12.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.001 Abstract （6631）      PDF（pc） （802KB）（1515）       Knowledge map    Save 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. Reference | Related Articles | Metrics | Comments（0）

Select

The optimal reinsurance problem towards joint interests of the insurer and the reinsurer with dependent risks HUAGN Ya, WANG Jing, ZHOU Jieming, DENG Yingchun Operations Research Transactions    2019, 23 (4): 13-33.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.002 Abstract （925）      PDF（pc） （1728KB）（191）       Knowledge map    Save 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. Reference | Related Articles | Metrics | Comments（0）

Select

A structural heterogeneity DEA method with containment relationship for efficiency evaluation CHEN Lei, WANG Yingming Operations Research Transactions    2019, 23 (4): 34-44.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.003 Abstract （1089）      PDF（pc） （1009KB）（165）       Knowledge map    Save 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. Reference | Related Articles | Metrics | Comments（0）

Select

Two-person stochastic game model of data transmission based on slotted ALOHA protocol XUE Juan, GAO Hongwei, JIANG Hui, ZHOU Yunxun Operations Research Transactions    2019, 23 (4): 45-58.   DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.004 Abstract （956）      PDF（pc） （703KB）（128）       Knowledge map    Save 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. Reference | Related Articles | Metrics | Comments（0）

• page
• Page 1 of 2
• Total 51 records
• First page
• Prev page
• Next page
• Last page