Table of Content

15 December 2015, Volume 19 Issue 4

Previous Issue    Next Issue

 An algorithm for a class of uncapacitated facility location problem based on branch-and-cut method

AN Bang,CHENG Peng

2015, 19(4):  1-13.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.001

Asbtract ( 843 )   PDF (1591KB) ( 846 )  

References | Related Articles | Metrics

The uncapacitated facility location problem is a classic combinatorial optimization problem with wide applications. However, this problem had been proven to be NP-hard and the traditional solving method based on branch-and-bound is slow. In this paper, we studies a class of UFLP problem aiming at maximizing the gap between total income and total investment cost, we transform this problem into a node packing problem and propose a new family of valid inequalities-axis inequalities based on graphic features of the model, which are stronger than the odd-hole inequalities after a strict proof. We also design a fast searching algorithm for cut inequalities and embed it in the branch-and-cut method. In the end, strong validity of axis inequalities are validated by experiments. The experimental results also showed that compared with the branch-and-bound method, the branch-and-cut method can reduce the number of branch nodes as
well as speed up the solving process.

An approximation algorithm for reliable facility location problem

YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi

2015, 19(4):  14-24.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.002

Asbtract ( 744 )   PDF (569KB) ( 552 )  

References | Related Articles | Metrics

 The research of facility location problem starts from 1960s, which mainly focuses on the locations of facilities and the assignments among cities to be connected by facilities, in order to minimize the total costs of the facility constructions and the city connections. In reality, facilities may fail from time to time due to natural disaster, labor strike, terrorist attacks or other factors. Such failures may lead to excessive transportation costs as cities must be served from facilities much further than their regularly assigned facilities. How to improve system reliability in relatively small costs becomes the emphasis for reliable facility location problem. However, current algorithms for reliable facility location problem are all based on Lagrangian relaxation and continuum approximation, which are costly in running time, even though they may be effective for some special cases. Besides, they don't have good theoretical approximation ratios. We redesigned a new algorithm with constant performance ratio by referring to greedy method, primal-dual and the idea of hierarchy mentioned in the Fault Tolerant Facility Location Problems. The advantage of our new algorithm is that it will achieve a theoretical approximation algorithm with numerical performance ratio if the number of assignment levels is fixed. It is a great improvement compared to the former reliable facility location problems which only have numerical experiment algorithms.

Parallel production systems efficiency evaluation based on DEA

WANG Yousen,XU Hao

2015, 19(4):  25-36.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.003

Asbtract ( 631 )   PDF (694KB) ( 426 )  

References | Related Articles | Metrics

Data envelopment analysis (DEA) is a linear programming approach for evaluating relative efficiency of peer decision making units (DMUs) that consume multiple inputs to produce multiple outputs. DMUs can have parallel independent sub-units, where inputs and outputs of each DMU are the sum of those its sub-units. This paper investigates the properties and relationships of the existing parallel DEA models, i.e., network, multi-component and relational DEA models, that address measuring the performance of parallel production systems. A major limitation of the existing DEA models is that efficiency optimization may produce multiple sets of efficiency scores for individual sub-units. The current paper proposes a new DEA approache through efficiency decomposition to deal with this problem. A case of Canadian bank branches is employed to illustrate these parallel DEA approach.

A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem

ZHANG Huizhen, WEI Xin, MA Liang

2015, 19(4):  37-47.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.004

Asbtract ( 1173 )   PDF (649KB) ( 533 )  

References | Related Articles | Metrics

The un-capacitated facility location (UFL) problem is a classical combinatorial optimization hard problem and has been applied in various fields. The semi-Lagrangian relaxation method is one of the exact solution methods to the UFL. In this paper, the mathematical nature of the SLR applied to solve the UFL is further studied. Based on this, the SLR applied to solve the UFL is improved from the theoretical point of view, and the approach is also discussed to enhance its
computational capability. The numerical results show that the improvement proposed in this paper is feasible and effective.

A feasible sequential systems of linear equations algorithm for inequality constrained optimization

MA Guodong, JIAN Jinbao

2015, 19(4):  48-58.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.005

Asbtract ( 929 )   PDF (571KB) ( 490 )  

References | Related Articles | Metrics

In this paper, a feasible sequential systems of linear equations algorithm for inequality constrained optimization is proposed. At each iteration, the proposed algorithm solves only two systems of linear equations with a same coefficient matrix to obtain the feasible descent direction. Furthermore, the sparsity of the coefficient matrix is good. Under some necessary assumptions, the algorithm possesses global and strong convergence. Finally, some preliminary numerical
experiments are reported to show that the algorithm is effective.

Measurement method of block compressed sensing based  on partial trigonometric function transform matrices

CHEN Jian, SU Kaixiong, PENG Zheng, SU Lichao

2015, 19(4):  59-71.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.006

Asbtract ( 982 )   PDF (4593KB) ( 391 )  

References | Related Articles | Metrics

To improve the measurement efficiency and reconstruction performance of the block compressed sensing (BCS), two measurement methods of compressed
sensing, based on partial discrete cosine transform in repeated block diagonal structure (abbreviated as PDCT-RBDS), and respectively, partial discrete sine transform in repeated block diagonal structure (abbreviated as PDST-RBDS), are proposed because of that the DCT (discrete cosine transform) and DST (discrete sine transform) have the property of collecting energy. The measurement matrices adopted are a structural deterministic matrix under the low complexity, and satisfy with the restricted isometry property (RIP). Moreover, by relating with sampling energy, the restricted isometry constant (RIC) and the lower bound of measurements for exact recovery are deduced. The experimental results, which compared with the partially random Gaussian matrices in repeated block diagonal structure (abbreviated as PRGS-RBDS) and partially Bernoulli matrices in repeated block diagonal structure (abbreviated as
PBNL-RBDS), indicate that, about 1---5 dB gain in the PSNR and 0.05 gain in the SSIM are observed, and the recovery time and storage space for measurement matrices are greatly reduced. The method is particularly suitable for the applications of image compressing in large scale and video data processing in real time.

Two results of the compact graph and its applications

Siqinbate, WANG Jingyu

2015, 19(4):  72-82.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.007

Asbtract ( 705 )   PDF (1484KB) ( 393 )  

References | Related Articles | Metrics

Doubly stochastic matrix has many important applications, the family of compact graphs can be seen as the generalization of the famous Birkhoff theorem which is about doubly stochastic matrix,  and is of important research value． Determine whether a graph is a compact graph is a difficult problem,  at present there are only few compact graphs known． This paper gives two important results: the graph constructed by any compact graph combining some isolated points is a
compact graph; the graph constructed by adding one pendant edge to each vertex of any compact graph is also a compact graph． By these two results,  we can construct an infinite number of compact graph family from already known compact graph．

A modification of Newton method with convergence  of order  2+\sqrt{6}

L\"{U} Wei, SUI Ruirui, FENG Enmin

2015, 19(4):  83-96.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.008

Asbtract ( 791 )   PDF (565KB) ( 497 )  

References | Related Articles | Metrics

 In this paper, a new modification of the standard Newton method for approximating the root of a univariate function is introduced. Two evaluations of function and two evaluations of its first derivative are required at a cost of one additional function and first derivative evaluations per iteration. The modified method converges faster with the order of convergence  2+\sqrt{6}  compared with 2 for the standard Newton method. Numerical examples demonstrate the new
algorithm has advantages in the iteration number, computation time and optimal value compared with the current algorithms. At last, the predictor-corrector improvement is generalized to multi-dimensional vector-valued functions, its convergence is proved using Taylor formula, and two two-dimensional examples are given to illustrate its convergence.

A non-empty condition and an axiomatization  for the core of multi-choice NTU games

TIAN Haiyan, ZHANG Gang

2015, 19(4):  97-106.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.009

Asbtract ( 1087 )   PDF (550KB) ( 394 )  

References | Related Articles | Metrics

This paper introduces the concept of \pi-balanced multi-choice NTU games and proves that any \pi-balanced multi-choice NTU game has a non-empty core. The definitions of non-leveled multi-choice NTU games and reduced games are introduced and the concepts of consistency and converse consistency are also given. An axiomatization for the core of non-leveled multi-choice NTU games is provided by using individual rationality, one-person rationality, consistency and converse consistency.

Some dual characterizations of free disposal sets in vector optimization

TANG Liping, YANG Yuhong

2015, 19(4):  107-113.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.010

Asbtract ( 846 )   PDF (485KB) ( 581 )  

References | Related Articles | Metrics

In this paper, we focus on some dual characterizations of free disposal sets in a separated locally convex space, in which, free disposal set means that its algebraic sum with a convex cone is still itself. Under the assumption that E_1 or E_2 is free disposal set, we proved some dual results, such as (E_1\cap E_2)^+=E_1^++ E_2^+, E_1^+ \capE_2^+=(E_1+ E_2)^+, etc.

Analytic relationship between Shapley and Winter values

HU Xunfeng, LI Dengfeng

2015, 19(4):  114-120.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.011

Asbtract ( 1018 )   PDF (484KB) ( 499 )  

References | Related Articles | Metrics

As both the Shapley and Winter values are averages of players' marginal contributions, this paper explores their analytic relationship. Specifically, the result that Shapley value is Winter value's expectation with respect to symmetric probability distributions on level structure set is proved. As a corollary, the argument that
Shapley value is Winter value's average with respect to any similar class in level structure set is also attested. Finally, the equivalence of this result and corollary is presented. The research results not only expand corresponding relationship between Shapley and Owen values, but also simplify the proofs of these correspondingrelationship enormously.

On-line algorithms for incompatible job families on parallel  machines scheduling with lookahead

LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang

2015, 19(4):  121-126.  doi:10.15960/j.cnki.issn.1007-6093.2015.04.012

Asbtract ( 876 )   PDF (509KB) ( 519 )  

References | Related Articles | Metrics

 We consider the on-line scheduling of incompatible unit-length job families  on unbounded parallel-batch machines with lookahead when the number of
job families is equal to the number of machines. In this paper online means that jobs arrive over time. The objective is to minimize the makespan. In the lookahead model, at a time instant  t , an on-line algorithm can foresee the information of all jobs arriving in the time segment  (t,t+\beta). By incompatible job
families, we  mean that jobs from different families cannot be assigned together in the same batch. When \beta \geq 1, we provide an optimal online algorithm; When 0\leq \beta < 1, we give a best possible online algorithm of competitive ratio 1+\alpha, where \alpha is the positive root of the equation \alpha^{2}+(1+\beta) \alpha+\beta-1=0.  We also provide a new lower bound on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.