Table of Content

15 June 2013, Volume 17 Issue 2

Previous Issue    Next Issue

Original Articles

Facility location problem with submodular penalties and stochastic demands

WANG Xing, XU Dachuan

2013, 17(2):  1-9. 

Asbtract ( 1968 )   PDF (633KB) ( 1270 )  

References | Related Articles | Metrics

In this paper, we consider the facility location problem with submodular penalties and stochastic demands. The objective is to open a subset of facilities,  to connect a subset of clients to open facilities, and  to penalize the remaining  clients such that the total cost of opening cost, connection cost, inventory cost, handling cost and penalty cost is minimized. Based on the special structure of the problem, we propose a primal-dual 3-approximation algorithm. In the algorithm, we construct a dual feasible solution in the first step followed by constructing the corresponding  primal integer feasible solution in the second step. This  primal integer feasible solution indicates the final opening facility set and penalty client set. We prove that the proposed algorithm can be implemented in polynomial time and the cost of the incurred primal integer feasible solution is no more than 3 times of the optimal value.

On the crossing numbers of W₆*S_n

ZHOU Zhidong,WANG Jing

2013, 17(2):  10-18. 

Asbtract ( 1556 )   PDF (912KB) ( 818 )  

References | Related Articles | Metrics

In the early 1950s, Zarankiewicz conjectured that the crossing number of the complete partite graph K_{m,n}(m\leq n) is \lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor (for any real number x, \lfloor x\rfloor denotes the maximum integer that is no more than x). At present, the truth of this conjecture has been proved for the case m\leq6. This paper determines the crossing number of the Cartesian product W_{6}  with S_{n} is cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor, provided that Zarankiewicz's conjecture holds for the case m=7.

A quantum-inspired ant colony algorithm for graph coloring problem

HE Xiaofeng,MA Liang

2013, 17(2):  19-26. 

Asbtract ( 1918 )   PDF (611KB) ( 1009 )  

References | Related Articles | Metrics

A quantum-inspired ant colony algorithm (QACA) for the classic graph coloring problem is proposed based upon the combination of ant colony optimization and quantum computing. The quantum bits and quantum logic gates are introduced to the ant colony algorithm (ACA), and the disadvantage of getting into the local optimum can be effectively avoided. The computational speed of the algorithm is therefore significantly improved. Series of simulation instances of the graph coloring problem are tested. And the results show that the QACA is a feasible, effective and versatile method for solving the graph coloring problem.

The study of design optimization about single-processor scheduling algorithm in real-time system

DUAN Yuan

2013, 17(2):  27-34. 

Asbtract ( 1484 )   PDF (608KB) ( 638 )  

References | Related Articles | Metrics

The study of modelling and scheduling problem in real-time system is research focus of operations research and control theory.  This paper studies a scheduling algorithm of single-processor in real-time system, especially Rate Monotonic (RM) and Earliest Deadline First (EDF), and show that RM is a typical static scheduling algorithm and EDF is a typical dynamic scheduling algorithm.  Moreover, the paper prove that RM is the best in static priority scheduling algorithm of single-processor and EDF is the best dynamic priority one's.  At last, in order to make the modelling and scheduling better for real-time system, a new abstracting means of task processing action is put forward: Time and Local remaining Execution-Time plane (T-LET plane).  Based on this method, the paper set up single-processor flow model and BLREF scheduling algorithm, and point out their background of geometry.

The bound of clique-transversal numbers in claw-free graphs

LIANG Zuosong,SHAN Erfang,GUAN Mei

2013, 17(2):  35-40. 

Asbtract ( 1499 )   PDF (546KB) ( 702 )  

References | Related Articles | Metrics

A  clique-transversal set $S$ of a graph $G=(V, E)$ is a subset of vertices of $G$ such that $S$ meets all cliques of $G$, where a clique is defined as a complete subgraph  maximal under inclusion and having at least two vertices. The  clique-transversal number, of $G$ denoted by $\tau_C(G)$,  is the minimum cardinality of a clique-transversal set in $G$.  In this paper we discuss the bound of clique-transversal numbers in several subclasses of claw-free graphs.

A simulated annealing algorithm for the hybrid flow shop  scheduling to minimize the number of tardy jobs

SHUAI Tianping,YU Jinguo,SUN Ling

2013, 17(2):  41-47. 

Asbtract ( 1435 )   PDF (532KB) ( 1248 )  

References | Related Articles | Metrics

This paper considers the scheduling problem of hybrid flow shop scheduling which the involves total number of tardy jobs. An improved simulated annealing algorithm is proposed for its solution. The initial seed solution is obtained by a heuristic algorithm, then optimizes the solution by the simulated annealing algorithm. New schedule can be obtained by selecting two jobs randomly and interchanging them. In conjunction with the first come first service  rule and first available machine rule to construct a schedule for the overall stages. Numerical results indicate the algorithm is feasible and efficient.

Some properties of approximate solutions for multiobjective optimization problems with respect to polyhedral set

GAO Ying

2013, 17(2):  48-52. 

Asbtract ( 1512 )   PDF (493KB) ( 889 )  

References | Related Articles | Metrics

In this paper, we consider approximate solutions for multiobjective optimization problems. First, we prove polyhedral set is co-radiant set, and present some properties for this special co-radiant set. And then, we present some properties for approximate solutions with respect to polyhedral set.

Pricing and hedging in the incomplete finance market

REN Fengying,LI Xingsi

2013, 17(2):  53-69.  doi:O225

Asbtract ( 2194 )   PDF (640KB) ( 982 )  

References | Related Articles | Metrics

In the classical complete finance market, we can provide the unique price for option according to arbitrage-free principle and we can also hedge risk perfectly. With such a hypothesis, we can manage the risk of derivatives efficiently and easily. But in the realistic finance market, many poor risk management cases happen frequently. And the current finance crisis show that the realistic finance market is very complicated and incomplete. In incomplete market, the risk can not be hedged away perfectly, and pricing and hedging problems are intractable. There is no consistent acceptable theory. In this paper, we survey various methods of pricing and hedging in incomplete market for promoting further investigation. We focus on the basic ideas and basic models, and explore the advantages and drawbacks of these methods and the relationship between them. We emphasise the key role that the optimization theory and methods will play and in the meanwhile we also analyse some problems and the gaps in methods that need to make further investigation.

Smoothed square-root penalty function for nonlinear constrained optimization

MENG Zhiqing,GAO Song

2013, 17(2):  70-80. 

Asbtract ( 1532 )   PDF (477KB) ( 1371 )  

References | Related Articles | Metrics

In this paper, we introduce a nonsmoothed square-root penalty function for nonlinear constrained optimization. We propose a smoothing function for the nonsmooth penalty function and define the corresponding smoothed penalty problem and obtain some error estimations among their optimal objective function values for the smoothed penalty problem and the original optimization problem. We develop an algorithm based on the smoothed penalty function and prove the convergence of the algorithm. Numerical examples show that the proposed algorithm is efficient for solving some nonlinear constrained optimization problems.

The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected

YU Guidong,FAN Yizheng

2013, 17(2):  81-88. 

Asbtract ( 1827 )   PDF (439KB) ( 1055 )  

References | Related Articles | Metrics

The least eigenvalue of a graph is defined as the least eigenvalue of the 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 2-vertex connected or 2-edge connected, and present a lower bound for the least eigenvalue of such graphs.

Affine scaling interior Levenberg-Marquardt method for KKT systems

WANG Yunjuan,ZHU Detong

2013, 17(2):  89-106. 

Asbtract ( 1729 )   PDF (492KB) ( 1045 )  

References | Related Articles | Metrics

We develop and analyze a new affine scaling Levenberg-Marquardt method with nonmonotonic interior backtracking line search technique for solving Karush-Kuhn-Tucker (KKT) system. By transforming the KKT system into an equivalent minimization problem with nonnegativity constraints on some of the variables, we establish the Levenberg-Marquardt equation based on this reformulation. Theoretical analysis are given which prove that the proposed algorithm is globally convergent and has a local superlinear convergent rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.

Dual forms of super efficiency for vector equilibrium problems

GONG Shu,GONG Xunhua

2013, 17(2):  107-123. 

Asbtract ( 1377 )   PDF (467KB) ( 865 )  

References | Related Articles | Metrics

The paper introduces the concepts of strongly superefficient solution, C-strongly superefficient solution, weakly superefficient solution, C-weakly superefficient solution, homogeneously superefficient solution and C-homogeneously superefficient solution for vector equilibrium problems, and discusses the dual forms of  C-weakly superefficient solution, C-superefficient solution, C-homogeneously superefficient solution, C-strongly superefficient solution, respectively for vector equilibrium problems in locally convex space with the aid of polar theory. The equivalence of the above kinds of superefficiencies in the normed space was studied, and their dual forms for vector equilibrium problems in the normed space with a normal cone were discussed. As an application, the dual forms of various superefficiencies are given for vector optimization problems.

A generalized gradient projection filter method for arbitrary initial point

GAO Jing,WANG Wei

2013, 17(2):  124-130. 

Asbtract ( 1469 )   PDF (413KB) ( 923 )  

References | Related Articles | Metrics

In this paper, a new generalized gradient projection filter method for arbitrary initial point is proposed. It can decrease the scale of computation and avoid the defect of penalty function. Another merit of the algorithm is that it avoids the filter method converging to a feasible but non-optimal point or occurring cycling. Moreover, it has no demand on the initial point and under some mild assumptions it has global convergence.