Operations Research Transactions

Simulation of Levy-driven models and its application in finance

CHEN Ruidi, PENG Yijie, HU Jianqiang

2013, 17(1): 1-9.

Asbtract ( 3059 )

PDF (566KB) ( 1880 )

References | Related Articles | Metrics

Levy processes have been widely used to model financial assets since the 1990s. The reason of their widespread applications is mainly due to the fact that they provide more realistic models that capture discontinuous behaviors and stylized empirical statistical characteristics of time series data in economy and finance. However, when applied to derivative pricing, very few analytical results are available except for European options. Therefore, one usually has to resort to numerical methods such as Monte Carlo simulation method. The simulation method is so attractive that it is very general and can also handle high dimensional problems very well. In this short survey paper, we first provide an overview on Levy processes. We then introduce Monte Carlo simulation method for Levy processes. Finally, we discuss the two main simulation based gradient estimation methods: perturbation analysis and likelihood ratio method.

The development of military operations research

SHAO Guopei, XU Xuewen, LIU Qizhi, HE Jun

2013, 17(1): 10-16.

Asbtract ( 2485 )

PDF (459KB) ( 1068 )

References | Related Articles | Metrics

Military operations research (MOR) is an interdisciplinary subject emerged in the beginning of the 1900s. It mainly studies the theories and methods for military systems with quantitative analysis and decision optimization. This paper reviews the development history of MOR and it's development in China. This paper gives an overview of the main theoretical approaches and research content of MOR, looks forward to the future development of MOR.

Chinese postman problem over 50 years

GAO Jingzhen, GAO Bo

2013, 17(1): 17-28.

Asbtract ( 3865 )

PDF (712KB) ( 1565 )

References | Related Articles | Metrics

We introduce the general postman problem firstly, involving issues such as serving and traversing cost, sides of serving, turn cost and serving hierarchy and so on. We then survey briefly the research on the Chinese postman problem, the Chinese postman problem on directed graphs, postman problems on mixed graphs, on graphs with wind and on rural districts, focusing on their linear programming formulations and the structures of the corresponding polyhedra, addressing the models of problems, exact algorithms and their time complexities, and the approximation approaches and their performance.

Asymptotic analysis of the tails of queue length retrial queue with batch arrival

WANG Yingli, LIU Weiqi, LI Jihong

2013, 17(1): 29-37.

Asbtract ( 1905 )

PDF (596KB) ( 1291 )

References | Related Articles | Metrics

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue which is batch arrived and have subexponential service time by using stochastic decomposition. Then we obtain the correlation between the stationary queue length tail distribution of an M/G/1 retrial queue with batch arrival and the stationary queue length tail distribution in the corresponding standard M/G/1 queue with batch arrival. Our results for subexponential tails also can be applied to regularly varying tails. Therefore, we get the regularly varying tail asymptotics for the stationary queue length.

An improved algorithm for scheduling two identical machines with batch delivery consideration

WANG Leiyang, LIU Zhaohui

2013, 17(1): 38-43.

Asbtract ( 2029 )

PDF (476KB) ( 886 )

References | Related Articles | Metrics

In this paper we consider the scheduling problem on two identical (parallel) machines in which the finished jobs need to be delivered to a customer in batches by single vehicle. The goal is to minimize the makespan, i.e., the time by which the vehicle has delivered the last job and returned to the machines. We assume that the jobs have different sizes, and give an approximation algorithm with the worst-case performance ratio(14/9+ε).

Direct algorithm for continuous separable Knapsack problem

ZHU Tingting, CHEN Wei, CHEN Juanjuan, SUN Wenhao

2013, 17(1): 44-58.

Asbtract ( 2102 )

PDF (633KB) ( 1069 )

References | Related Articles | Metrics

The quadratic Knapsack problem is NP-hard. In this paper, a direct algorithm is proposed for an ordinary continuous separable quadratic Knapsack problem with a single linear constraint and box constrains. According to the special structure model, the optimal value of all the variables can be fixed gradually by adjusting the range of the Lagrangian multiplier for the linear constrain and by judging whether the variables of the first power in the objective function satisfy the box constraints. Finally the feasibility and efficiency of the algorithm are illustrated through the comparison of experimental results.

Risk aversion in inventory management with Bayesian information updating

LUO Chunlin

2013, 17(1): 59-68.

Asbtract ( 1822 )

PDF (588KB) ( 1290 )

References | Related Articles | Metrics

A well-known result in the Bayesian inventory management research is: if lost sales are not observed, the Bayesian optimal inventory level is larger than the myopic inventory level. The underlying reason behind the fact is that the decision maker needs to stock more to learn about the demand distribution. These researches are based on the assumption that the decision maker is risk neutral. However, in reality, different decision makers often have different degree of risk aversion. In this paper, a multi-period newsvendor problem with risk aversion and partially observed demand is considered. The decision maker uses the Bayesian rule to update the information of the demand distribution, and the utility is characterized by the sum of the intraperiod utility functions which satisfy the additive independence axiom. Our research, by using the interesting concept of unnormalized probability, shows that as the decision maker is risk averse and the utility function is the negative exponential function with a constant coefficient of absolute risk aversion, the Bayesian optimal inventory level is also larger than the myopic inventory level. The unnormalized probability greatly simplifies the dynamic programming equation and facilitates the technical proof of the result.

Optimal (s,d,S) policy for a production-inventory system with pricing and setup cost

YANG Baimei, XU Yifan

2013, 17(1): 69-85.

Asbtract ( 1974 )

PDF (608KB) ( 1422 )

References | Related Articles | Metrics

We consider a continuous review production-inventory system with finite capacity and setup cost, which is controlled by an (s,d,S) policy. Unsatisfied demand is lost. When the machine is off, the inventory on hand can be sold at two different selling prices. While the machine is on, the inventory only can be sold at the high price. We show the method to find the optimal (s,d,S) control policy for this system and develop efficient algorithms to compute the optimal control parameters.

Linear conic optimization models for robust credit risk optimization

ZHANG Hongjie, BAI Yanqin, FANG Chunliang

2013, 17(1): 86-97.

Asbtract ( 1977 )

PDF (472KB) ( 1558 )

References | Related Articles | Metrics

In this paper we deal with the credit risk optimization problem. We present a model based on the worst-case Conditional Value-at-Risk (CVaR) risk measure and the uncertainty for the credit risk loss distribution. Under the box uncertainty, we reformulate the model into a linear optimization problem. Furthermore, under the ellipsoidal uncertainty, we reformulate the model into a seconde-order cone optimization problem. Finally, we show a numerical example to demonstrate the effective of our models.

Single-machine group scheduling problems with the sum-of-processing-time based on learning effect

ZHANG Xingong

2013, 17(1): 98-105.

Asbtract ( 1868 )

PDF (421KB) ( 1168 )

References | Related Articles | Metrics

This paper investigates a new group scheduling problem with sum-of-processing-time based learning effect. The learning effect of a job is assumed to be a function of total processing times of jobs scheduled in front of it, the learning effect of group is assumed to a function of its position in the sequence. The goal is to minimize makespan and the total completion times under the proposed model, respectively. Some optimal properties and optimal polynomial time algorithms to solve these problems are also provided.

QP-free infeasible method without a penalty function and a filter

2013, 17(1): 106-116.

Asbtract ( 2305 )

PDF (458KB) ( 976 )

References | Related Articles | Metrics

In this paper, we propose a QP-free infeasible method without a penalty function and a filter for constrained nonlinear optimization problems. This iterative method is based on the solution of nonsmooth equations which are obtained by the multipliers and the piecewise linear relationship NCP function for the KKT first-order optimality conditions. Locally, each iteration of this method can be viewed as a perturbation of the mixed Newton-quasi Newton iteration on both primal and dual variables for the solution of KKT optimality conditions. We do not use a penalty function and a filter on line searches. This method is implementable and globally convergent. Without the second order correction we prove that the method has superlinear convergence rate under some mild conditions.

Bicriteria approximation algorithms for the lower-bounded facility location problem with penalties and soft-capacity

LI Gaidi, WANG Zhen, WU Yulin

2013, 17(1): 117-126.

Asbtract ( 1914 )

PDF (461KB) ( 1462 )

References | Related Articles | Metrics

We study the lower-bounded facility location problem with penalties (LBFLP) and the soft-capacity LBFLP. For the LBFLP, we present an updated bicriteria approximation algorithm which maintains the same performance factor ρ(1+α)/(1-α) as that for the problem without penalties in Hierarchical placement and network design problems(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)and Building steiner trees with incomplete global knowledge(Karger D R, Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329). We further extend this result to the soft-capacitated LBFLP and achieve a performance factor twice as much as that for LBFLP.

Table of Content