2016 Vol.20

    Please wait a minute...
    For Selected: Toggle Thumbnails
    Portfolio selection models with new negative exponential expected utilities
    FU Tianwen, TU Zhuozhuo, WEI Boyang
    Operations Research Transactions    2016, 20 (1): 1-18.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.001
    Abstract1036)      PDF(pc) (669KB)(612)       Save

    With an overview of the literatures on discussions about optimal investment decision problems, we propose a new class of negative exponential utility function satisfying the monotonicity and concavity. And reasonable explanations are also given from the viewpoints of mathematics and economics. The fat-tail phenomenon of the loss distribution is controlled efficiently by different kinds of weighted function and proper description to the tail. We use L-statistics to estimate the new expected utility and the rationality is also illustrated. Moreover, we construct a realistic portfolio selection model with multiple market frictions. With the real data from Chinese and American stock market, we carry out a series of empirical studies. Empirical results show the superiority and robustness of our new expected utility.

    Reference | Related Articles | Metrics | Comments0
    Optimal pension investment problem with stochastic salary
    杨鹏
    Operations Research Transactions    2016, 20 (1): 19-30.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.002
    Abstract841)      PDF(pc) (600KB)(529)       Save

    Under three kinds of objective function, optimal pension investment problem with stochastic salary is studied. The first objective function is mean-variance criterion. The second is stochastic differential game based on utility. The third is stochastic differential game based on mean-variance. During stochastic differential game, the both sides of game are the pension plan investors and financial markets, and financial market is a game of virtual hand. Under three kinds of objective function, closed-form solutions for the value function are obtained by applying linear quadratic control theory as well as the optimal strategies.

    Reference | Related Articles | Metrics | Comments0
    Three-echelon supply chain scheduling problem with learning effect
    LIU Ying, ZHANG Xingong
    Operations Research Transactions    2016, 20 (1): 31-42.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.003
    Abstract869)      PDF(pc) (620KB)(478)       Save

    This paper studies three-echelon supply chain scheduling problem with learning effect.  Multiple customers are distributed in different locations. And some orders of each customer will be processed in manufacturers. Manufacturers need to purchase the corresponding raw materials from different places to process the different orders of different customers.  Finally,  the processed orders need to be transported the corresponding customer by limited transportation vehicles.  The transportation vehicles will transport goods as possible as truck load.  We present the three dynamic programming to solve the problems of maximum flow time,  total flow time and maximum lateness.

    Reference | Related Articles | Metrics | Comments0
    Cited: Baidu(4)
    Path-following interior point algorithms based on wide neighborhoods and a new class of directions
    LIU Changhe, SHANG Youlin, LI Jinrui
    Operations Research Transactions    2016, 20 (1): 43-53.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.004
    Abstract885)      PDF(pc) (581KB)(556)       Save

    This paper presents a class of path-following interior point algorithms for the monotone linear complementarity problems based on wide neighborhoods and the new directions with a parameter \theta. When the parameter \theta=1, the new direction is exactly the classical Newton direction. The algorithms have O(nL) iteration complexity when the parameter \theta is independent of the dimension n, which coincides with the best known iteration complexity for the classical wide neighborhood algorithms. When \theta=\sqrt{n/\beta\tau}, the algorithm has O(\sqrt{n}L) iteration complexity, the best iteration complexity obtained so far by any interior point method for solving linear complementarity problems, where \beta and \tau are neighborhood parameters. To our knowledge this is the first time that a class of interior point algorithms including the classical wide neighborhood path-following algorithm is proposed and analyzed.

    Reference | Related Articles | Metrics | Comments0
    Weak S-efficient solution of vector optimization
    GUO Hui, BAI Yanqin
    Operations Research Transactions    2016, 20 (1): 54-60.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.005
    Abstract883)      PDF(pc) (480KB)(523)       Save

    In this paper, we introduce the concept of weak S-optimal solution and S-subconvexlikeness of vector optimization with set-valued maps and obtain an alternative theorem in a real locally Hausdorff topological vector space. Furthermore, under the assumption of S-subconvexlikeness, we establish scalarization theorem for weak S-efficient solution. We also give some examples to illustrate the main results.

    Reference | Related Articles | Metrics | Comments0
    Integration of mathematical programming with constraint programming for multi-objective planning and scheduling
    GONG Jing
    Operations Research Transactions    2016, 20 (1): 61-74.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.006
    Abstract1137)      PDF(pc) (876KB)(622)       Save

    Planning and scheduling, a NP-hard problem, can be viewed as a decision-making process of allocating limited resources to tasks over time with the goal of optimizing a certain objective. Neither mathematical programming nor constraint programming can solve it in the reasonable time. Minimum cost, minimum makespan and minimum tardiness are three classical objectives for this problem. The requirements from a real world application might be that several goals need to be achieved simultaneously. Based on Benders decomposition approach, this paper proposed an algorithm integrating  mathematical programming and constraint programming for solving multi-objective planning and scheduling.

    Reference | Related Articles | Metrics | Comments0
    Stability of optimal solution set and optimal value for minimax stochastic programming approximation problems
    HUO Yongliang
    Operations Research Transactions    2016, 20 (1): 75-83.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.007
    Abstract920)      PDF(pc) (530KB)(692)       Save

    In this paper, we research convergence of minimax approximation problems  of special class of bilevel stochastic programming. First, under regularity conditions of feasible set, we expand optimal solution set of lower level original stochastic programming to into non-singleton set. And we give continuity of optimal value and upper semi-convergence of the optimal solution  set on the upper level decision variables for lower level stochastic programming approximation problem. Furthermore, we feedback $\varepsilon$-optimal solution vector function provided by the lower level stochastic programming into the objective function of the upper level stochastic programming problems, and obtain the continuity of optimal value and the upper semi-convergence of optimal solution set with respect to the minimal information (m.i.) probability metric for upper level programming.

    Reference | Related Articles | Metrics | Comments0
    Online batch scheduling with known information in advance
    WANG Chengfei, ZHANG Yuzhong
    Operations Research Transactions    2016, 20 (1): 84-90.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.008
    Abstract1444)      PDF(pc) (495KB)(492)       Save

    We study a single online batch scheduling problem with known information in advance. The information arrives over time and the objective is to minimize the maximum completion time. The time between the information arrival of a job and its release time is constant $a$. The maximum of the processing times of all jobs $p_{{\rm max}}$ is known in advance too. A batch processing machine can handle up to $b$ jobs simultaneously. The processing time of a batch is given by the longest processing time of all jobs in the batch. When $b=\infty$, we provide an optimal online algorithm $\gamma H^\infty$ with a competitive ratio of $1+\gamma$, where $\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$.

    Reference | Related Articles | Metrics | Comments0
    Cited: Baidu(3)
    Optimal excess-of-loss reinsurance and investment strategy under state-dependent utility function
    GU Ailing, CHEN Shumin
    Operations Research Transactions    2016, 20 (1): 91-104.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.009
    Abstract1003)      PDF(pc) (1230KB)(516)       Save

    This paper studies an optimal excess-of-loss reinsurance and investment problem for an insurer, and aims to maximize the expected exponential utility from her terminal wealth with a state-dependent utility function. It is assumed that the surplus of the insurer and the financial market are modulated by an observable continuous-time Markov chain. By applying stochastic control theory, the explicit expression of  optimal reinsurance-investment strategy is obtained. Finally, the impact of some parameters on the optimal strategy and optimal value function is given.

    Reference | Related Articles | Metrics | Comments0
    Determining the discriminating domain for linear differential games based on viability theory
    HAN Yanli, GAO Yan
    Operations Research Transactions    2016, 20 (1): 105-111.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.010
    Abstract1062)      PDF(pc) (533KB)(458)       Save

    This paper studies a bounded discriminating domain for linear pursuit-evasion differential games using viability theory. Researching a bounded polyhedron who is a convex hull of finite points for the discriminating domain of linear differential games by viability theory, we just need to test whether the extreme points of the polyhedron meet the viability conditions. Then, using the relationship between viability and discriminating domain, we can determine whether the polyhedron is the discriminating domain of the differential games. It is easy to be used.

    Reference | Related Articles | Metrics | Comments0
    The Hamilton-connectivity with the degree sum of  non-adjacent subgraphs P_ 4 and K_1 in claw-free graphs
    ZHENG Wei, WANG Ligong
    Operations Research Transactions    2016, 20 (1): 112-117.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.011
    Abstract882)      PDF(pc) (480KB)(428)       Save
    This paper studies the relationship between the degree of subgraphs and Hamiltonicity of graphs. It is proven that every 3-connected claw-free graph $G$ of order $n$ with minimum degree $\delta(G)\geq4$ is Hamilton-connected if it satisfies $d(H_1)+d(H_2)\geq n$ for any two non-adjacent subgraphs $H_1$, $H_2$ which are isomorphic to $P_4$, $K_1$ respectively.
    Reference | Related Articles | Metrics | Comments0
    Continuity of the solution set map to parametric weak vector equilibrium problems
    LUO Guowang, PENG Yanfang, LIU Yanmin, HUANG Jianwen
    Operations Research Transactions    2016, 20 (1): 118-124.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.012
    Abstract928)      PDF(pc) (464KB)(442)       Save

    In this paper, using the nonlinear scalarization method, we obtain the upper semicontinuity and lower semicontinuity of the solution mappings to parametric weak vector equilibrium problems. Some examples are given to illustrate our results.

    Reference | Related Articles | Metrics | Comments0
    Some results on fractional k-factor-critical graphs and fractional k-extendable graphs
    HUANG Xiaoxian, LIU Yan, WU Bosi
    Operations Research Transactions    2016, 20 (1): 125-130.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.013
    Abstract1204)      PDF(pc) (556KB)(474)       Save

     A simple graph G is said to be fractional k-factor-critical if after deleting any k vertices, the remaining subgraph still has a fractional perfect matching. A graph G is called a fractional k-extendable graph if G has a fractional perfect matching containing M for any k-matching M. In this paper, a sufficient condition for a graph to be fractional k-factor-critical graph and fractional k-extendable graph is given, respectively. Besides, a sufficient and necessary condition for a graph to be fractional k-factor-critical graph is given.

    Reference | Related Articles | Metrics | Comments0
    Introduction of some algorithms for nonlinear semidefinite  programming
    LI Jianling, YANG Zhenping, JIAN Jinbao
    Operations Research Transactions    2016, 20 (2): 1-22.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.001
    Abstract950)      PDF(pc) (672KB)(670)       Save

    In this paper, some important and effective numerical methods developed in recent years for nonlinear semidefinite programming are introduced, which included augmented Lagrangian methods, sequential semidefinite programming algorithms, sequence of linear equations algorithms and alternating direction multiplier methods. At the end of this paper, some future research perspectives of algorithms for nonlinear semidefinite programming are discussed.

    Reference | Related Articles | Metrics | Comments0
    Queue length distribution and numerical calculation of queueing system with delay Min(N,D)-policy
    WEI Yingyuan, TANG Yinghui, YU Miaomiao
    Operations Research Transactions    2016, 20 (2): 23-37.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.002
    Abstract1086)      PDF(pc) (935KB)(466)       Save

    This paper considers the M/G/1 queueing system under the delay Min(N,D)-policy. By using the renewal process theory, the total probability decomposition technique and the Laplace transform tool, we study the transient and equilibrium properties of the queue length from the beginning of the any initial state, and obtain both the recursion expressions of the Laplace transformation of the transient queue length distribution and the recursion expressions of the steady state queue length distribution. Meanwhile, we present the explicit expression of the additional queue-length distribution. Furthermore, we discuss some special cases, such as N \to \infty, or D \to \infty, or N=1 and P{Y=0}=1 or P{Y=0}=1, respectively.  Finally, by numerical examples, we discuss the sensitivity of the steady state queue length distribution towards system parameters, and illustrate the important value of the expressions of the steady state queue length distribution in the system capacity optimum design.

    Reference | Related Articles | Metrics | Comments0
    On connected K_{n}-residual graph
    DUAN Huiming, LI Yonghong
    Operations Research Transactions    2016, 20 (2): 38-48.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.003
    Abstract804)      PDF(pc) (866KB)(603)       Save

    The definition of m-K_{n}-residual graph was raised by P. Erd\"{o}s, F. Harary and M. Klawe. When n\neq 1,2,3,4, they proved that K_{n+1}\times K_{2} is only connected to K_{n}-residual graph which has minimum order. In this paper, we have studied m-K_{n}-residual graph, and obtained some important properties. At the same time, we proved that  the connected K_{n}-residual graph of the minimum order and the extremal graph for n=1,2,3,4. When n=1,2, it is the only extremal graph. When n=3,4, we proved just two connected residual graph  non isomorphic with the minimum order, so as to thoroughly solve the connected K_{n}-residual graph of the minimum order and extremal graph's problems. Finally we prove that K_{n+1}\times K_{2} is only connected with the minimum order of K_{n}-residual graph, when n\neq 1,2,3,4.

    Reference | Related Articles | Metrics | Comments0
    Online hierarchical service scheduling on two identical machines with release times
    HOU Liying
    Operations Research Transactions    2016, 20 (2): 49-58.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.004
    Abstract1022)      PDF(pc) (599KB)(417)       Save

    This paper considers online scheduling problem on two identical machines under a grade of service, where jobs arrive online over time. The objective is to minimize the maximum completion time. We propose an online algorithm with competitive ratio \frac{7}{4}.

    Reference | Related Articles | Metrics | Comments0
    Laplacian spectral characterizations of some classes of multi-cyclic graphs
    ZHAI Ruonan, WANG Ligong, DONG Zhanpeng, WANG Zhanqing, MEI Ruoxing
    Operations Research Transactions    2016, 20 (2): 59-68.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.005
    Abstract1099)      PDF(pc) (725KB)(527)       Save

    Let G be a simple connected graph. A graph G is called to be determined by its Laplacian spectrum if any graph having the same Laplacian spectrum as G is isomorphic to G. In this paper, a bicyclic graph \theta_{n}(p_1,p_2,\cdots,p_t) and a m-cyclic graph H_n(m\cdot C_3;p_1,p_2,\cdots,p_t) are defined. It is proved that bicyclic graphs \theta_{n}(p), \theta_{n}(p,q), and tricyclic graphs H_n(3\cdot C_3;p),  H_n(3\cdot C_3;p,q) are determined by their Laplacian spectra.

    Reference | Related Articles | Metrics | Comments0
    Approximation algorithm for the fault-tolerant facility placement problem with penalties
    FANG Rui, LUO Wenchang
    Operations Research Transactions    2016, 20 (2): 69-78.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.006
    Abstract748)      PDF(pc) (542KB)(489)       Save

    In the fault-tolerant facility placement problem with penalties, we are given a set of customers and a set of sites, and connection costs between customers and sites. We assume that the connection costs satisfy the metric principle. Each customer has its service demands. We can open an unbounded number of different facilities at each site. Each customer can be either assigned to some different opened facilities in some sites to satisfy its demands or rejected by paying a penalty. The objective is to minimize the total cost of opening facilities and connecting those non-rejected customers to different open facilities, and the reject penalties. In this paper, we formulate the fault-tolerant facility placement problem with penalties as a linear integer programming and give its dual programming. Then we propose a 4-approximation algorithm  based on rounding its linear programming and dual programming.

    Reference | Related Articles | Metrics | Comments0
    Cited: Baidu(1)
    A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming
    YANG Yang, LUO Honglin, LUO Huilin
    Operations Research Transactions    2016, 20 (2): 79-87.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.007
    Abstract1080)      PDF(pc) (677KB)(778)       Save

    Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming. It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points.Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L).Numerical analysis are also presented in this paper.Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction.

    Reference | Related Articles | Metrics | Comments0
    Second-order characterizations on Benson proper efficient element of set-valued optimization
    XU Yihong, YANG Yun
    Operations Research Transactions    2016, 20 (2): 88-96.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.008
    Abstract704)      PDF(pc) (456KB)(576)       Save

    This paper introduced a new kind of second-order tangent cone, and related second-order tangent derivative, termed as second-order radial composed tangent derivative. Some properties of second-order radial composed tangent derivative and its relationship to second-order composed tangent derivative are discussed. Sufficient and necessary optimality conditions are established respectively for a Benson proper efficient element of set-valued optimization by second-order radial tangent derivative.

    Reference | Related Articles | Metrics | Comments0
    Total transversals in 5-uniform hypergraphs
    LIN Yi, NI Zhenyu, SHAN Erfang
    Operations Research Transactions    2016, 20 (2): 97-104.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.009
    Abstract1083)      PDF(pc) (533KB)(753)       Save

    Let H=(V,E) be a hypergraph with vertex set V and edge set E. The hypergraph H is k-uniform if every edge of H have size k. A transversal in H is a subset of vertices in H that has a nonempty intersection with every edge in H. A total transversal in H is a transversal T in H with the additional property that every vertex in T is adjacent to some other vertex of T. The total transversal number \tau_{t}(H) of H is the minimum cardinality of a total transversal in H. For k\geq 2, let b_{k}=\sup_{H\in {\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, where {\mathscr{H}}_{k} denotes the class of all k-uniform hypergraphs containing no isolated vertices or isolated edges or multiple edges. Recently, Bujt\'as and Henning et al. proved following results: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}. For k\geq 5, b_{k}\leq \frac{2}{7}. What's more, b_{6}\leq\frac{1}{4}, and for k\geq 7, b_{k}\leq \frac{2}{9}. In this paper, we show that b_{5}\leq\frac{4}{15} for 5-uniform hypergraphs and this improves the upper bound of b_{5}.

    Reference | Related Articles | Metrics | Comments0
    A kind of inexact parallel splitting method for solving the fairest core in cooperative game
    WANG Siqi, XIE Zheng, DAI Li
    Operations Research Transactions    2016, 20 (2): 105-112.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.010
    Abstract923)      PDF(pc) (757KB)(489)       Save

    In this paper, considering the characteristics of the core and the Shapley value in cooperative game, we transform the fairest core problem into a separable convex optimization problem with two variable. A kind of inexact parallel splitting method is proposed for solving the fairest core by introducing the operator splitting method framework of structured variational inequalities. Furthermore, the proposed method makes full use of the simple closed convexity of the feasible region in the solved problem, and all sub-problems are easy to be solved inexactly. Finally, some numerical results of a simple example indicate the convergence and validity of this method.

    Reference | Related Articles | Metrics | Comments0
    A hybrid bundle method for nonsmooth convex optimization
    ZHANG Qingye, GAO Yan
    Operations Research Transactions    2016, 20 (2): 113-120.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.011
    Abstract927)      PDF(pc) (515KB)(527)       Save

    A hybrid bundle method for nonsmooth convex optimization problems is proposed. In this method, the next iterate point is obtained by solving a subproblem which is formed by adding proximal term to the objective function and trust region constraint to the feasible region. The proposed algorithm combines proximal bundle method with trust region bundle method and switches between them automatically. Convergence analysis shows that the algorithm we proposed is global convergent. Finally, a numerical example is given to verify the validity of the method we proposed.

    Reference | Related Articles | Metrics | Comments0
    Scalarization of weakly C(\varepsilon)-efficient solutions via quasi interior in vector optimization
    ZHANG Wanli, XIA Yuanmei, ZHAO Kequan
    Operations Research Transactions    2016, 20 (2): 121-126.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.012
    Abstract1079)      PDF(pc) (503KB)(455)       Save

    In this paper, some characterizations of co-radiant sets via quasi interior  are obtained. Furthermore, under the nearly C(\varepsilon)-subconvexlikeness, an alternative theorem is established and a linear scalarization result of weakly C(\varepsilon)-efficient solutions via quasi interior is given for a class of vector optimization problems with set-valued maps.

    Reference | Related Articles | Metrics | Comments0
    The algorithm and model of pairwise stable networks
    ZHEN Mengke, GAO Hongwei, LIU Shuqing, JI Haiqiang
    Operations Research Transactions    2016, 20 (3): 1-10.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.001
    Abstract903)      PDF(pc) (1717KB)(642)       Save

    Firstly, by establishing equivalent condition of pairwise stability networks with Jackson-Wolinsky rules, this paper gives an complete algorithm to find pairwise stability network. Secondly, after the introduction of side payments, this paper proofs that the set of pairwise stability network allowing for side payments when adding links is the intersection of the set of pairwise stability network and the set of pairwise stability network allowing for side payments when adding and deleting links. Finally, two explicit pairwise stability network models are considered. Using the algorithm of pairwise stability networks, this paper systematically analyzes this two models’ pairwise stability.

    Related Articles | Metrics | Comments0
    Analysis for a preemptive priority queue with finite capacity
    ZHANG Hongbo, ZHOU Gaojun, FENG Pinghua
    Operations Research Transactions    2016, 20 (3): 11-20.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.002
    Abstract664)      PDF(pc) (791KB)(383)       Save

    This paper considers an M/M/1 queue that handles arrivals form 2 classes of customers on a preemptive priority basis,  where the lower-priority customers with finite buffering.  The queue model can be described in a quasi-birth-and-death (QBD) process with finitely many phases. By matrix-geometric method,  we get the formula of stationary queue length distribution,  and illustrate the effectiveness of the method by numerical examples.

    Related Articles | Metrics | Comments0
    Approximation algorithms for max cut and  max bisection problems using semi-definite programming relaxations
    SUN Ting, LI Gaidi, XU Wenqing
    Operations Research Transactions    2016, 20 (3): 21-32.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.003
    Abstract1252)      PDF(pc) (765KB)(478)       Save

    Given an undirected graph with nonnegative weight for each edge, the max cut problem is to partition its vertex set into two parts such that the total weight of crossing edges is maximized. When the optimal solution of its Service Design Package (SDP) relaxation lies in a two-dimension space, Goemans improved the approximation ratio from 0.87856... to 0.88456. Using the Gegenbauer polynomials rounding technique, we obtain an approximation curve depending on the ratio between the optimal value of the SDP relaxation and the total weight,  which has the lowest point 0.88456. We further improve the  approximation ratio curve when the ratio varies from 0.5 to 0.9044. Furthermore, we consider an important variant of the max cut problem, the max bisection problem, in which the equal cardinality constraint for the two parts in the partition is imposed. We also consider the case that the optimal solution of the SDP relaxation for the Max Bisection problem lies in a two-dimension space and obtain a 0.7091-approximation for this variant by using the aforementioned Gegenbauer polynomials rounding technique.

    Related Articles | Metrics | Comments0
    Combining time and position dependent effects on  a single machine subject to maintenance activities
    Gou Yan, Zhang Xingong
    Operations Research Transactions    2016, 20 (3): 33-44.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.004
    Abstract806)      PDF(pc) (541KB)(469)       Save

    In this paper, we consider combining time and position dependent effects on a single machine subject to deteriorating maintenance activities.  The actual processing time of the job is a function of its position.  We focus on minimizing two classical objectives: the makespan and the sum of the completion times. The proposed two problems can be solved in polynomial time by using the matching algorithm. Finally, the makespan problems can be solved by the group balance principle under some certain conditions.

    Related Articles | Metrics | Comments0
    Gradient-based adaptive quick cuckoo search algorithm
    LI Rongyu, LIU Yang
    Operations Research Transactions    2016, 20 (3): 45-56.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.005
    Abstract974)      PDF(pc) (1145KB)(497)       Save

     For the problems of the unbalanced capability between global search and local search of standard cuckoo search (CS) algorithm, a gradient-based adaptive quick cuckoo search (GBAQCS) is proposed. The direction of the step is determined based on the sign of the gradient of the function. On the one hand, the adaptive search strategy is used to balance the global search and local search capability. On the other hand, the current-guided search method is adopted to improve the convergence precision and rate. The simulation experiments show that GBAQCS fully utilizes and balances the global search and local search capability, and greatly improves the convergence speed and quality of solutions compared with other optimization algorithms.

    Related Articles | Metrics | Comments0
    A filled function method based on filter for global optimization with box constraints
    HU Quan, WANG Wei
    Operations Research Transactions    2016, 20 (3): 57-67.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.006
    Abstract1054)      PDF(pc) (554KB)(515)       Save

    This paper presents a filled function algorithm based on filter technique for the nonconvex global optimization problems with boxed constrains. The filled function method is one of effective methods for solving global optimization problems. And the filter technique is widely used in local optimization algorithm because of its good numerical results. In order to optimize the filled function method, we try to use the filter set to supervise the iteration. In the paper, a new filled function is formulated first and then its necessary characteristics are discussed. Based on that, the algorithm dominated by the filter is proposed and its properties are proved. The numerical results are list at last to show the effectiveness of the algorithm.

    Related Articles | Metrics | Comments0
    Cited: Baidu(2)
    The optimality conditions and duality theory for multiobjective semidefinite programming
    LI Yongling, YANG Yang, LUO Honglin
    Operations Research Transactions    2016, 20 (3): 68-78.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.007
    Abstract1129)      PDF(pc) (569KB)(466)       Save

    This paper aims at the optimality conditions, duality of multiobjective semidefinite programming problems and the optimality conditions for nonconvex  semidefinite programming.We first obtain a necessary and sufficient conditions of KKT condition for nonconvex semidefinite programming, based on this result, the optimality necessary conditions are presented.Furthermore, we discuss the optimality necessary or sufficient conditions for multiobjective semidefinite programming and construct Wolfe dual model for the corresponding problem.Finally, weak and strong duality theorems are established.

    Related Articles | Metrics | Comments0
    The continuity properties of optimal value function  of discrete optimization problems
    ZHANG Yuzhong, YANG Xiaoguang
    Operations Research Transactions    2016, 20 (3): 79-84.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.008
    Abstract1153)      PDF(pc) (516KB)(443)       Save

    It is undoubtedly significant to study the change rules of the optimal values  of optimization problems, when the set of feasible solutions changes follow some parameters, even if there is no way to get the optimal value generally. For continuous optimization, where the independent variables are numbers or vectors, the characteristics of the optimal value functions following the changing of the variables has been studied extensively, but for discrete optimization problems there is few literature. In this paper some important classical combinatorial optimization problems are considered. We mainly focus on the characteristics of the optimal value functions, here the independent variables are some plans or tours, may not be numbers nor vectors. Parallel scheduling problem, Knapsack problem, Traveling salesman problem are considered in the paper, focusing on  the characteristics of the optimal value functions of these problems if the inputs of parameters are change. Finally, we also consider the characteristics of objective function arised by some famous algorithms such as LPT to  minimize  the makespan of parallel machine schedule.

    Related Articles | Metrics | Comments0
    A class of nonlinear scalarization theorem of vector optimization problems
    TANG Liping, YANG Xinmin
    Operations Research Transactions    2016, 20 (3): 85-91.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.009
    Abstract1093)      PDF(pc) (478KB)(559)       Save

    In this paper, a class of nonlinear scalarization for vector optimization problem is investigated via Gertewitz functional. We mainly prove the fact that (C, \varepsilon)-weakly efficient solutions or (C, \varepsilon)-efficient solutions of vector optimization problem are equivalent to approximate solutions or strictly approximate solutions of scalar problem, and also  estimate the approximate solutions of this scalar problem.

    Related Articles | Metrics | Comments0
    The clique-coloring  problem in line graphs
    LIANG Zuosong
    Operations Research Transactions    2016, 20 (3): 92-98.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.010
    Abstract937)      PDF(pc) (546KB)(357)       Save

    A clique is defined as a complete subgraph  maximal under inclusion and having at least two vertices.   A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic.  If G has a  k-clique-coloring, we say that G  is k-clique-colorable. The clique-coloring number  \chi_{C}(G)  is the smallest  integer  k admitting a  k-clique-coloring of G.  In this paper,  we first point out a relation between the clique-coloring number of line graphs of complete graphs  and the generalized Ramsey number. Secondly, we give a polynomial time algorithm for the optimal clique-coloring problem in line graphs of maximum  degree at most 7.

    Related Articles | Metrics | Comments0
    Twin domination in generalized de Bruijn and Kautz digraphs
    DONG Yanxia, ZHANG Guang, SHAN Erfang
    Operations Research Transactions    2016, 20 (3): 99-106.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.011
    Abstract994)      PDF(pc) (704KB)(374)       Save

    Let G=(V, A) be a digraph with vertex set V and arc set A.  A set T of vertices of G is a twin dominating set of G if for every vertex v\in V(G)\setminus T, there exist u, w\in T (possibly u=w) such that arcs (u,v),(v,w)\in A(G). The twin domination number \gamma^{*}(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we present a new upper bound on the twin domination number of generalized de Bruijn digraphs G_B(n,d) and generalized Kautz digraphs G_K(n,d), which improves the known upper bound in previous literature. For special generalized de Bruijn and Kautz digraphs, we further improve the bounds on twin domination number by directly constructing their twin dominating sets.

    Related Articles | Metrics | Comments0
    Stability to bounded rationality for nonconvexity
    WANG Chun, QIU Xiaoling, WANG Nengfa, CHEN Pinbo
    Operations Research Transactions    2016, 20 (3): 107-120.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.012
    Abstract753)      PDF(pc) (616KB)(369)       Save

    In recent years, there are many articles about bounded rationality. However, most articles study the properties of bounded rationality under the condition of convexity, and this leads to the limited scope of its application. This paper uses Ekeland variational principle and weaks the assumptions of bounded rationality. Under the condition of nonconvex  we study the stability of bounded rationality model problem. And the solution's stability of the nonconvex Ky Fan point problem, the solution's stability of the nonconvex and noncompact Ky Fan point problem, the solution's stability of the nonconvex Vector-valued function Ky Fan point problem and the solution's stability of the nonconvex and noncompact Vector-valued function Ky Fan point problem are given. As an application, we also give the solution's stability of the nonconvex n-person noncooperative games' bounded rationality model and the solution's stability of the nonconvex multi-objective games' bounded rationality model.

    Related Articles | Metrics | Comments0
    An extended label correcting method for the SUM-MIN bi-criterion path problem in logistics transportation network
    HAN Shilian
    Operations Research Transactions    2016, 20 (3): 121-128.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.013
    Abstract677)      PDF(pc) (616KB)(389)       Save

    The paper concentrates on the SUM-MIN bi-criterion path problem in the logistics transportation network. An objective aggregation method based on the fuzzy compromise programming technique and an extended label correcting method to solve the aggregated objective are proposed. In the process of aggregating multiple objectives to a single one, the edge evaluation for each objective and the overall evaluation for all the objectives are considered. By assigning the weights to each objective, the decision maker's preference information can be integrated in this aggregation process, and the fuzzy compromise solution can be obtained with the generic aggregation method. Finally, a numerical example shows the solution process of the proposed approach.

    Related Articles | Metrics | Comments0
     Stability of solutions to parametric optimization problems under bounded rationality
    YANG Guanghui, YANG Hui, XIANG Shuwen
    Operations Research Transactions    2016, 20 (4): 1-10.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.001
    Abstract787)      PDF(pc) (536KB)(532)       Save

     Parametric optimization has been widely applied in game theory, control theory, economics and management, engineering technology, etc. Recently, the stability of solutions to parametric optimization has attracted increasing attention. This paper mainly studies the stability of solutions to parametric optimization problems under bounded rationality. By introducing an abstract rationality function, two rational models M are established with two types of perturbations: the perturbation of both objective functions and feasible sets, and the perturbation of objective functions, feasible sets and parameters simultaneously. For the two perturbations above, by the ``generic'' method, the rational model M is structurally stable and is robust to \varepsilon-equilibria (or solutions), respectively. That is, the solutions to most of parametric optimization problems are stable in the sense of Baire category. Finally, an example is illustrated.

    Reference | Related Articles | Metrics | Comments0
    An algorithm for elastic l_2-l_q regularization
    ZHANG Yong, YE Wanzhou
    Operations Research Transactions    2016, 20 (4): 11-20.   DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.002
    Abstract1217)      PDF(pc) (872KB)(454)       Save

    In this paper, we present an iteratively re-weighted l_{1} minimization (IRL1) algorithm for solving elastic l_{2}-l_{q} regularization. We prove that any sequence generated by the IRL1 algorithm is bounded and asymptotically regular. We further prove that the sequence is convergent based on an algebraic method for any rational q \in (0,1) and the limit is a stationary point of the elastic l_{2}-l_{q}(0<q<1) minimization problem. Numerical experiments on sparse signal recovery are presented to demonstrate the effectiveness of the proposed algorithm.

    Reference | Related Articles | Metrics | Comments0