Table of Content

15 September 2019, Volume 23 Issue 3

Previous Issue    Next Issue

The load balancing problem

ZHANG Guochuan, CHEN Lin

2019, 23(3):  1-14.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.001

Asbtract ( 1810 )   PDF (668KB) ( 640 )  

References | Related Articles | Metrics

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.

Linear relaxation solution based heuristics for a class of multi-product facility location problems

YANG Muming, HUANG Yakui, DAI Yuhong

2019, 23(3):  15-26.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.002

Asbtract ( 1862 )   PDF (4129KB) ( 805 )  

References | Related Articles | Metrics

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.

Selective maintenance optimization: research advances and challenges

CHEN Yiming, JIANG Tao, LIU Yu

2019, 23(3):  27-46.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.003

Asbtract ( 1609 )   PDF (2853KB) ( 370 )  

References | Related Articles | Metrics

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.

Two optimization problems in wireless communication system design and related optimization methods

LIU Yafeng

2019, 23(3):  47-62.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.004

Asbtract ( 1158 )   PDF (1384KB) ( 383 )  

References | Related Articles | Metrics

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.

Introduction to high-order optimization methods

ZHU Xihua, CHANG Qingqing, JIANG Bo

2019, 23(3):  63-76.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.005

Asbtract ( 1221 )   PDF (638KB) ( 297 )  

References | Related Articles | Metrics

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.

A survey on rainbow matchings in graphs and hypergraphs

LI Tong, WANG Guanghui, ZHOU Wenling

2019, 23(3):  77-90.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.006

Asbtract ( 1057 )   PDF (732KB) ( 410 )  

References | Related Articles | Metrics

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.

Two-stage stochastic non-cooperative multi-vendor game under the transportation network-based on stochastic variational inequarity

HOU Lina, SUN Hailin

2019, 23(3):  91-108.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.007

Asbtract ( 1383 )   PDF (2975KB) ( 355 )  

References | Related Articles | Metrics

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.

A review of optimal transport in image processing

MA Litao, BIAN Wei

2019, 23(3):  109-125.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.008

Asbtract ( 1890 )   PDF (2991KB) ( 565 )  

References | Related Articles | Metrics

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.

The risk-reward model of the online time series search problem

ZHANG Wenming, CHENG Yongxi, RU Shaofeng

2019, 23(3):  126-134.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.009

Asbtract ( 1126 )   PDF (3268KB) ( 170 )  

References | Related Articles | Metrics

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.

Some notes on the divergence example for multi-block alternating direction method of multipliers

CHEN Caihua

2019, 23(3):  135-140.  doi:10.15960/j.cnki.issn.1007-6093.2019.03.010

Asbtract ( 1387 )   PDF (469KB) ( 356 )  

References | Related Articles | Metrics

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.