Operations Research Transactions

Research report on the development of operations research in China

The Operational Research Society of China

2012, 16(3): 1-48.

Asbtract ( 4177 )

PDF (1123KB) ( 2912 )

References | Related Articles | Metrics

Operations Research (OR) is an interdisciplinary subject emerged in the 1930s. It mainly studies how to make optimal or satisfactory solutions through mathematical and computational theories and methods for social and engineering systems. In order to promote the research and application of OR in China, we invite a dozen of experts in OR and related areas to complete this report making reference to the review of OR development by many top experts in representative areas in OR. In this report, we first summarize the features and methodology of OR and make a brief review on the development of OR with analysis on successful experiences in OR study. Then, we survey the status of some main directions of this discipline along with some its typical open problems. In the end of the survey we prospect for the trend of OR in the future. We hope that this report could motivate readers to reflect upon what is the essence of OR and how OR has grown up and will develop in next decades, and in such a way advance OR development in China.

Introduction to compressive sensing and sparse optimization

WEN Zaiwen YIN Wotao LIU Xin ZHANG Yin

2012, 16(3): 49-64.

Asbtract ( 9037 )

PDF (669KB) ( 3496 )

References | Related Articles | Metrics

We briefly introduce the basic principle and theory of compressive sensing and sparse optimization. Compressive sensing is a new paradigm of signal acquisition, which senses a sparse signal by taking a set of incomplete measurements and recovers the signal by solving an optimization problem. This article first illustrates the compressive sensing paradigm through a synthetic example. Then we describe two sufficient conditions, the null space property and restricted isometry principle, for l₁ convex minimization to give the sparsest solution. Finally, we summarize a few typical algorithms for solving the optimization models arising from compressive sensing.

A survey on probabilistically constrained optimization problems

SUN Xiaoling, BAI Xiaodi, ZHENG Xiaojin

2012, 16(3): 65-74.

Asbtract ( 3810 )

PDF (382KB) ( 1710 )

References | Related Articles | Metrics

We give a brief review on the probabilistically constrained optimization problem which is an important class of stochastic programming with wide applications in finance, management and engineering planning. We introduce the modeling of probabilistic constraints and summarize some important solution methods including convex approximation, DC approach, scenario approach and integer programming approach. We also discuss some future research perspectives of the probabilistically constrained optimization problem.

Characterization of solution sets of E-convex programming problems

JIANG Gen, LIU Xuewen, WANG Gang, CHEN Lin

2012, 16(3): 75-83.

Asbtract ( 2305 )

PDF (275KB) ( 1256 )

References | Related Articles | Metrics

In this paper, an important class of generalized convex programming problems, E-convex program, was considered. We defined the E-Gateaux differential of E-convex function on the E-convex set, and got some characteristic theorems of the E-Gateaux differential of E-convex function, proposed the equivalent characterizations of the solution sets of E-convex programming problems by using the characteristic theorems. For an E-convex program in a normed vector space with the objective function admitting the E-Gateaux differential at an optimal solution, we showed that the solution set consists of the feasible points lying in the hyperplane whose normal vector equals the E-Gateaux differential.

A partial cooperation model for bilevel programming problems with finite reactions follower

LIU Bingbing, WAN Zhongping

2012, 16(3): 84-92.

Asbtract ( 2371 )

PDF (336KB) ( 1500 )

References | Related Articles | Metrics

Bilevel programming problem provide a framework to deal with decision processes involving two decision makers with a hierarchical structure. The leader at the upper level of the hierarchy and the follower at the lower level seek to optimize their individual objective functions and control their own set of decision variables. Bilevel programming problem involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. Bilevel programming problem is frequently encountered with in the fields of economy, industry, transportation, military, and so on. In this paper, we investigate the partial cooperation model for the bilevel programming problem in which the optimal reactions of the lower level problem is discrete and finite. We develop a general method for ascertaining the cooperation ratio in the partial cooperation model when the cooperation degree of the follower depends on the decision variables of the leader. Furthermore, we develop a new partial cooperation model of which the optimal is better than of the pessimistic model under suitable conditions. Then we derive some meaningful results based the proposed partial cooperation model. Finally, we show that the proposed partial cooperation model is feasible by two numerical examples.

k-partitioning problem with items' type restriction

REN Qingjuan, XU Baoguang

2012, 16(3): 93-99.

Asbtract ( 1758 )

PDF (343KB) ( 1306 )

References | Related Articles | Metrics

We consider a k-partitioning problem with items' type restriction. Items' type restriction means each set containing k distinct types' items. This problem is in fact an extended k-partitioning problem, and has a wide application in the industry where one person can hold multi-skill licenses. For solving it we propose a greedy algorithm and obtain the following conclusions: k≤2, greedy algorithm get an optimal solution; k>2, the performance ratio is 2-m^-1.

The convergence of Broyden algorithms without convexity and exact line search

PU Dingguo, SHANG Youlin, FANG Aifen, SUN Zhenyang

2012, 16(3): 100-108.

Asbtract ( 2332 )

PDF (150KB) ( 1269 )

References | Related Articles | Metrics

In this paper we discuss the convergence of the Broyden algorithms without convexity and exact line search assumptions. We prove that if the algorithm produces a convergence point sequence, then the limit point of the sequence is a critical point of the objective function.

Characterizations of the solution set for a class of nonsmooth optimization problems

ZHAO Kequan, YANG Xinmin

2012, 16(3): 109-118.

Asbtract ( 1906 )

PDF (179KB) ( 1264 )

References | Related Articles | Metrics

In this paper, a class of nonsmooth optimization problems with inequality constraints is considered. Characterizations of the solution set are obtained in terms of Clarke subdifferentials and Lagrange multipliers. An example is given to illustrate the main results. The resluts improve and extend some previously known results.

Optimal dividend payments of the two-dimensional compound Poisson risk model with capital injection

ZHANG Shuaiqi, LIU Guoxin

2012, 16(3): 119-131.

Asbtract ( 1833 )

PDF (202KB) ( 1322 )

References | Related Articles | Metrics

This paper deals with the optimal dividend payment and capital injection problem for a two-dimensional compound Poisson risk model which constructs correlation among the two claims. The objective of the corporation is to maximize the discounted dividend payments minus the penalized discounted capital injections. The problem is formulated as a stochastic control problem. By solving the corresponding Hamilton-Jacobi-Bellman (HJB) equation, we obtain the optimal dividend strategy of the problem. We solve this problem explicitly in the case of exponential claim amount distributions.

Subgraph with orthogonal (0,f)-factorization in (0, mf-k+1)-graph

XIAO Lan, LIU Yan

2012, 16(3): 132-138.

Asbtract ( 1809 )

PDF (141KB) ( 1052 )

References | Related Articles | Metrics

Let G be a simple graph, f be a non-negative integer-valued function defined on V(G), m≥2 and be an integer. In this paper, we investigate the orthogonal factorization of (0,mf-k+1)-graph and prove that, for any integer 1≤ k≤m, every (0,mf-k+1)-graph G has a subgraph R such that, R has a (0,f)-factorization orthogonal to any k subgraph H of G.

NP-completeness for two generalized domination problems

ZHAO Weiliang, ZHAO Yancai, LIANG Zuosong

2012, 16(3): 139-144.

Asbtract ( 1882 )

PDF (148KB) ( 1317 )

References | Related Articles | Metrics

We study the complexity of two classes of generalized domination problems: k-step domination problem and k-distance domination problem. We prove that the decision version of k-step domination problem is NP-complete when instances are restricted to chordal graphs or planar bipartite graphs. As corollaries to the results, we obtain new proofs of the NP-completeness of k-distance domination problem for chordal graphs and bipartite graphs, and also prove that this problem remains NP-complete even when restricted to planar bipartite graphs.

Table of Content