Operations Research Transactions

Study on approximate solutions of vector optimization problems

YANG Xinmin, ZHAO Kequan

2017, 21(4): 1-18. doi:10.15960/j.cnki.issn.1007-6093.2017.04.001

Asbtract ( 840 )

PDF (693KB) ( 593 )

References | Related Articles | Metrics

Vector optimization is one of the important research aspects in the field of mathematical programming and some related fundamental theory and basic methods have great theoretical significance and applicable value. In recent years, study on the definitions and properties of approximate solutions has become one research hotspot in theory and methods of vector optimization. In this paper, we mainly review some important progress about some concepts of approximate solutions and unified solutions, and their development and some properties of various kinds of approximate solutions and unified solutions for a class of vector optimization problems by Chinese researchers and especially for our group. In the end, we also propose some open questions related to approximate solutions and unified solutions in vector optimization problems.

Optimization models and algorithms for large capacity fingerprint automatic identification system

GUO Tiande, HAN Congying, ZHAO Tong,

2017, 21(4): 19-33. doi:10.15960/j.cnki.issn.1007-6093.2017.04.002

Asbtract ( 892 )

PDF (5781KB) ( 366 )

Related Articles | Metrics

Biological studies have shown that fingerprints' ridge structure never changes throughout the life of an individual after they are fully formed at about 7 months of fetus development except due to accidents such as bruises and cuts on the fingertips. This characteristic makes fingerprints very attractive for biometric authentication. Automatic fingerprint identification system (AFIS) includes the acquisition and storage of fingerprint images, the representation and feature extraction, fingerprint classification and indexing, fingerprint matching and other modules. Aiming at some key technologies in each module for the large capacity of AFIS, we established optimization models, designed fast and accurate algorithms. Experimental results showed that our algorithms are robust and effective. AFIS embedded in our core algorithms has been applied to criminal investigation areas in some provinces and cities in China.

Design optimization in 3D printing

YANG Zhouwang, LIU Yuan

2017, 21(4): 34-56. doi:10.15960/j.cnki.issn.1007-6093.2017.04.003

Asbtract ( 901 )

PDF (6795KB) ( 432 )

Related Articles | Metrics

The rise of 3D printing technology has stimulated a lot of hot research points in a number of research fields. The project Optimal Design in 3D Printing Applications has systematically studied many related topics in geometry processing, including saving printing material and printing time by structural optimization of 3D geometric models, feature-preserving denoising and construction of surfaces, and sequential construction and spurious sheets removal of 3D models. Many of the problems involve optimization models with complicated constraints, sparse representation and compress sensing. In this paper, we briefly summary the methods used in these problems, and reinterpret the use of operations research theories and algorithms in the perspective of geometric optimization, which indicates the importance and effectiveness of operations research tools in the study of related fields.

First-order algorithms for optimization problems with orthogonality constraints

GAO Bin, LIU Xin, YUAN Yaxiang

2017, 21(4): 57-68. doi:10.15960/j.cnki.issn.1007-6093.2017.04.004

Asbtract ( 1830 )

PDF (773KB) ( 846 )

Related Articles | Metrics

Optimization problems with orthogonality constraints have a wide range of applications in the field of materials science, statistics and data science. Many optimization algorithms on manifold can be applied to this type of problems, since the feasible region of orthogonal constraint is known as Stiefel manifold.
In recent years, with the expansion of variable scale required by practical application, the limitations of existing methods on manifold are reflected in practice. On the other hand, some efficient approaches based on new concepts are proposed recently. In this paper, we briefly introduce the main classes of methods for optimization problems with orthogonality constraints including retraction based method, non-retraction based method and infeasible method respectively. We also discuss the main characteristics of these approaches, the scenarios in which these approaches are suitable and the possible directions for further development.

An algorithmic review for total variation regularized data fitting problems in image processing

YANG Junfeng

2017, 21(4): 69-83. doi:10.15960/j.cnki.issn.1007-6093.2017.04.005

Asbtract ( 1401 )

PDF (1352KB) ( 526 )

Related Articles | Metrics

Total variation regularized data fitting problems arise from a number of image processing tasks, such as denoising, deconvolution, inpainting, magnetic resonance imaging, and compressive image sensing, etc. Recently, fast and efficient algorithms for solving such problems have been developing very rapidly. In this paper, we focus on least squares and least absolute deviation data fitting and present a brief algorithmic overview for these problems. We also discuss the application of a total variation regularized nonconvex data fitting problem in image restoration with impulsive noise.

A survey on online learning methods: Thompson sampling and others

HE Simai, JIN Yujia, WANG Hua, GE Dongdong

2017, 21(4): 84-102. doi:10.15960/j.cnki.issn.1007-6093.2017.04.006

Asbtract ( 1591 )

PDF (941KB) ( 717 )

Related Articles | Metrics

The paper is a survey on the latest research results, major theories and algorithms in the field of online learning. The topic of online learning is a broad one, and we aim at introducing the principles of the basic algorithms and ideas to the readers. We start from the most standard models and algorithm design, and extend all the way to a more general presentation on the latest developments in the area.

To begin with, we take the standard online optimization model, the Multi-Armed Bandit Problem, as an example. Then we discuss Thompson Sampling algorithms and Upper Confidence Bound algorithms, analyzing and presenting the main idea and newest theoretical achievements, with further discussion about the extensions and applications of Thompson Sampling in some more complicated real-world online learning scenarios. Furthermore, the paper gives a brief introduction about online convex optimization, which serves as an effective and well-known framework in solving Multi-Armed Bandit problem and other application problems.

Preemptive online algorithms for scheduling

DING　Chao

2017, 21(4): 103-117. doi:10.15960/j.cnki.issn.1007-6093.2017.04.007

Asbtract ( 855 )

PDF (618KB) ( 423 )

Related Articles | Metrics

Matrix optimization problems (MOPs) have been recognized in recent years to be a powerful tool to model many important applications arising from emerging fields such as data science {within and beyond the optimization community}. Perturbation analysis of optimization problems play a fundamental and crucial role in optimization, which provided important theoretical foundation for algorithm designing and others. Science MOPs are non-polyhedral, the corresponding analysis is totally different from that of the classical polyhedral case (e.g., the nonlinear programming). Basing on results obtained in [1,2], we summary the recent progress on perturbation analysis of MOPs.

A survey of assortment optimization problems under logit-based discrete choice models

CHEN Rui, JIANG Hai

2017, 21(4): 118-134. doi:10.15960/j.cnki.issn.1007-6093.2017.04.008

Asbtract ( 1211 )

PDF (1481KB) ( 722 )

Related Articles | Metrics

The assortment optimization problem is a classical problem in revenue management. In this problem, the retailer has to determine the subset of products to offer from a much larger set, so as to maximize the expected revenue subject to operational constraints. The core of this problem is how to characterize customers' choice behavior among differentiated products, develop optimization models, and design efficient solution algorithms. In this paper, we review existing studies on assortment optimization problems under logit-based discrete choice models. We first introduce assortment optimization problem based on the multinomial logit model. Next, we cover two advanced variants: (1) The first variant is based on the two-leve or multi-level nested logit models, which are able to take into consideration the substitution effects among differentiated products; and (2) The second variant is based on the mixtures of multinomial logits model, which can capture the heterogeneity among customers. Then, we cover the data-driven assortment optimization problem under rank-based non-parametric model. Finally, we outline possible directions for future research.

The coloring of the class of 1-planar graphs and its subclasses

ZHANG Xin, LIU Weichan

2017, 21(4): 135-152. doi:10.15960/j.cnki.issn.1007-6093.2017.04.009

Asbtract ( 864 )

PDF (4082KB) ( 482 )

Related Articles | Metrics

A graph G is 1-planar if it can be embedded on a plane so that each edge is crossed by at most one other edge, and such a 1-planar embedding of G is a 1-plane graph. Since every crossing c in a 1-plane graph is generalized by one edge crossing the other edge, there is a mapping \theta from c to a set of four vertices of G that are the end-vertices of the two edges crossing at c. For any two distinct crossings c_1 and c_2 (if exist) of a 1-plane graph G, if |\theta(c_1)\cap \theta(c_2)|\leq 1, then G is an NIC-planar graph, and if |\theta(c_1)\cap \theta(c_2)|=0, that is, \theta(c_1)\cap \theta(c_2)=\varnothing, then G is an IC-planar graph. If a graph G can be embedded on a plane so that all vertices are on its outerface and each edge is crossed by at most one other edge, then G is an outer-1-planar graph, and such an embedding of G is an outer-1-plane graph. This paper surveys the results on the colorings of the above four classes of graphs.

Table of Content