Special Topics

Default Latest Most Read

Please wait a minute... For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails 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 （2060）      PDF（pc） （668KB）（688）       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 （2086）      PDF（pc） （4129KB）（862）       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 （1841）      PDF（pc） （2853KB）（432）       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 （1466）      PDF（pc） （1384KB）（449）       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 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 （1299）      PDF（pc） （732KB）（474）       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 （1603）      PDF（pc） （2975KB）（393）       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 （2572）      PDF（pc） （2991KB）（733）       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 （1308）      PDF（pc） （3268KB）（179）       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 （1600）      PDF（pc） （469KB）（409）       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 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 （1494）      PDF（pc） （638KB）（368）       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）