Table of Content

15 September 2021, Volume 25 Issue 3

Previous Issue    Next Issue

Discussion on second-order analysis in augmented Lagrange method

ZHANG Liwei

2021, 25(3):  1-14.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.001

Asbtract ( 2461 )   HTML ( 61)   PDF (793KB) ( 303 )  

References | Related Articles | Metrics

From the point of view of maximizing the dual function based on augmented Lagrange function, the update of multiplier of augmented Lagrange method can be interpreted as a constant step gradient method. The effectiveness of augmented Lagrange method can be obtained by analyzing the second-order differential of dual function. In this paper, the second-order differentials of dual function for equality constrained optimization problem and general constrained nonlinear programming problem are estimated, which explains why the gradient method with constant step size has fast rate of convergence.

Optimization models and algorithms for placement of very large scale integrated circuits

HUANG Zhipeng, LI Xingquan, ZHU Wenxing

2021, 25(3):  15-36.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.002

Asbtract ( 3050 )   HTML ( 58)   PDF (1145KB) ( 665 )  

References | Related Articles | Metrics

Placement is one of the critical stages in the physical design of very large scale integrated circuits (VLSI), which has significant impact on the performance of integrated circuits, such as routability, delay, power consumption, circuit reliability, etc. Placement determines the specific positions of cells of a chip, by optimizing some performance metrics under the constraint of cells non-overlapping, which is an NP-hard combinatorial optimization problem. Modern placement algorithms need to deal with large-scale designs with millions of cells, heterogeneous modules with different sizes, and various complex placement constraints. Modern placement algorithms usually consist of three steps:global placement, legalization, and detailed placement. Based on the recent research progress of VLSI placement algorithms, this paper surveys related optimization models and algorithms for VLSI global placement, legalization and detailed placement, and discusses possible research directions.

Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics

CHEN Feng

2021, 25(3):  37-73.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.003

Asbtract ( 2870 )   HTML ( 43)   PDF (25909KB) ( 614 )  

References | Related Articles | Metrics

This paper discusses both the applied path of operations research on intelligence and the practice driven academic path, based on the development, implementation and maintenance of a referred decision support system that has been successfully deployed to automobile outbound logistics. The system is so far a pioneering intelligent dispatching system for automobile logistics company in China, and the corresponding thoughts, theories, methodologies and technologies demonstrate the key value of the discipline of operations research in the promotion of intelligent applications and the significance of practice in stimulating academic development, and so forth provide referred systematic approach for tackling bottleneck problems. This paper proposes a "Three Stages and Seven Steps" framework for the application of operations research on intelligent research and development. Under the framework, the paper firstly addresses the characteristics of intelligent application related to operational research, and particularly addresses intelligent scheduling decision requirements of automotive logistics and its developing trends and bottlenecks. Secondly, the paper discusses the roles of systematic model and related model building methods, and further identifying the scientific problems occurring in automotive outbound logistics by analyzing its decisional factors, objectives and constraints. Moreover, the new scientific problems so called "pattern constrained bin-packing" are proposed with computational intractability, solvability and key scientific properties. Furthermore, the paper establishes mixed integer linear programming models for practical and theoretical problems, respectively, and develops branching and bound algorithm. In addition, the paper also addresses the technologies and methodologies for time-space decomposition and rolling solutions of large-scale problems, and further proposes the production testing based on real data and stress testing method for the applications of operations research, and shows the results and testing analysis for outbound automobile logistics scheduling. In addition, this paper proposes a distributed, multi-view, multi-system integration intelligent scheduling decision support system, which is deeply integrated with automobile transportation management system and warehouse management system, driven by optimization algorithm engine. Finally, we introduce detail system implementations with deployment, promotions and maintenance, and briefly address related practice-driven scientific research outputs and future directions.

Optimization algorithms and their complexity analysis for non-convex minimax problems

XU Zi, ZHANG Huiling

2021, 25(3):  74-86.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.004

Asbtract ( 2821 )   HTML ( 47)   PDF (957KB) ( 404 )  

References | Related Articles | Metrics

The non-convex minimax problem is an important research front and hot spot in the cross-fields of optimization, machine learning, signal processing, etc. Some key scientific issues in frontier research directions such as adversarial learning, reinforcement learning, and distributed non-convex optimization, all belong to this type of problem. Internationally, the research on convex-concave minimax problems has achieved good results. However, the non-convex minimax problem is different from the convex-concave minimax problem, and it is a non-convex and non-smooth optimization problem with its own structure, for which, the theoretical analysis and the algorithm design are more challenging than that of the convex-concave minimax problem, and it is generally NPhard. This paper focuses on the latest developments in optimization algorithms and complexity analysis for non-convex minimax problems.

On the first order approach for bilevel programming: moral hazard case

KE Rongzhu, ZHANG Jin

2021, 25(3):  87-104.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.005

Asbtract ( 2388 )   HTML ( 5)   PDF (1028KB) ( 208 )  

References | Related Articles | Metrics

We revisit the first-order approach (FOA) in a classical setting of moral hazard model with multi-dimensional signal. After providing formal justification of Lagrangian duality, we reformulate the issue of validiting the FOA as an issue of the existence of a fixed point of the agent's best reaction to the principal's targeted effort level. Therefore, it is unnecessary to show the validity based on the global concavity of the agent's expected under a subclass of monotone contract. The new method allows the relaxation of several requirements of previous approaches. We generalize some results of Sinclair-Desgagne (1994) and Conlon (2009a) to validate the FOA for either the mixture probability model without the likelihood ratio order, or certain exponential family distributions with a bounded likelihood ratio.

Research status and challenges of inventory control problems with nonlinear ordering cost

YAO Dacheng

2021, 25(3):  105-118.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.006

Asbtract ( 2179 )   HTML ( 6)   PDF (867KB) ( 140 )  

References | Related Articles | Metrics

Inventory management is one subject based on Operations Research, and has been one of the most popular topics in the area of Operations Research and Management Science in the last few decades. Ordering cost is one class of essential costs in inventory systems, and it includes product cost, shipping cost, loading/unloading cost, etc. The ordering cost is often a nonlinear function of order quantity. This paper will introduce several well-known nonlinear ordering cost functions, such as quantitydependent fixed/setup cost, incremental quantity discount, all-unit quantity discount, truckload discount, convex ordering cost, etc. We review the literature of inventory models with nonlinear ordering cost based on periodic-review and continuous-review models, respectively. Although the inventory models with nonlinear ordering cost functions have been studied in recent decades, the optimal policies of many models haven't been fully characterized due to their complexity. This paper tries to discuss the challenges and chances in this topic, by reviewing related works.

A brief review on gradient method

SUN Cong, ZHANG Ya

2021, 25(3):  119-132.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.007

Asbtract ( 2951 )   HTML ( 17)   PDF (914KB) ( 414 )  

References | Related Articles | Metrics

Gradient method is a kind of first order optimization method. It is widely used for large scale problems, due to its simplicity and low complexity. This paper is a review on gradient method. Gradient methods for smooth unconstrained problems are introduced, with details of algorithm framework and theories. The crucial factor in gradient method is the stepsize, which determines the convergence property of the method. This paper reviews the stepsize update strategies and the corresponding convergence results from four aspects:line search, approximation technique, stochastic technique, alternating and constant stepsizes. Other related topics like gradient method for nonsmooth and constrained optimization problems, acceleration technique and stochastic gradient method are also mentioned.

Robust portfolio selection based on cross-sectional regression and Fama-Macbeth estimator

JIANG Bo, ZHU Xihua

2021, 25(3):  133-146.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.008

Asbtract ( 2187 )   HTML ( 10)   PDF (866KB) ( 142 )  

References | Related Articles | Metrics

This paper considers a factor model different from Goldfarb and Iyengar (2003) and the uncertainty set for the mean profit vector and covariance matrix of the assets in the robust problems are constructed by the cross-sectional regression and Fama-MacBeth estimator. Based on the robust portfolio selection problems under the Markowitz mean-variance model and these uncertainty sets, we prosed multiple robust portfolio selection problems and prove that these problems can be re-written as Semidefinite programmings which are computationally tractable.

Taylor expansion method for queueing systems

HU Jianqiang, DAI Weimin

2021, 25(3):  147-159.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.009

Asbtract ( 2164 )   HTML ( 8)   PDF (822KB) ( 159 )  

References | Related Articles | Metrics

In this paper, we give an overview on the Taylor expansion method developed in 1990s by Gong and Hu for the study of queueing systems, which have recently been found some new promising applications. We first use the GI/GI/1 queue to illustrate how the method works, then discuss how it can be applied to correlated queues, to analyzing the departure processes of queueing systems, and to developing high-order approximations for queueing networks. We also discuss several possible future research directions in this area.

Low rank support tensor machine based on L_0/1 soft-margin loss function

WANG Shuangyue, LUO Ziyan

2021, 25(3):  160-172.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.010

Asbtract ( 2248 )   HTML ( 8)   PDF (1546KB) ( 289 )  

References | Related Articles | Metrics

As a traditional classification method, support vector machine (SVM) has limitations for high order tensorial data, since direct vectorization will lead to the loss of intrinsic spatial structures in tensors, and the small sample size problem as well. As a higher-order extension of SVM, support tensor machine (STM), which targets at tensorial data classification, has attracted more and more attention of many scholars, with wide applications in remote sensing imaging, video processing, finance, fault diagnosis, etc. Analogous to SVM, the involved loss functions in most of the existing STM models are surrogates of the L_0/1 function. In this paper, the original L_0/1 loss is employed, based on which, a low rank STM model is proposed for the binary classification problem, with consideration of the intrinsic low-rankness of tensorial data. The resulting nonconvex discontinuous tensor optimization problem is solved by an alternating direction method of multipliers. Numerical experiments are conducted on synthetic data and real data sets to demonstrate the effectiveness of the proposed approach.

Some advances in gene regulatory network inference

LIU Zhiping

2021, 25(3):  173-182.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.011

Asbtract ( 2692 )   HTML ( 32)   PDF (813KB) ( 363 )  

References | Related Articles | Metrics

With the development of high-throughput technology, more and more biomedical data need to be processed and analyzed. Bioinformatics is one of the fundamental ways to effectively analyze high-dimensional biomedical data. This paper is to provide a brief review of our recent works in gene regulatory network inference. According to different types of transcriptomic data and research purposes, the corresponding network inference methods were established, including the establishment of a priori gene regulatory network database, causal network inference based on conditional mutual information, dynamic gene regulation network inference based on differential equations, transcriptional regulation and post-transcriptional regulation inference, and the evaluation of gene regulatory network activity. At the same time, the important research directions in gene regulatory network inference are prospected.

Cost allocation for multiple pairs of shortest paths recovery game on disrupted networks

XUAN Hongwei, LI Zhendong, SHENG Zhoushan, LIU Lindong

2021, 25(3):  183-199.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.012

Asbtract ( 2245 )   HTML ( 15)   PDF (1327KB) ( 219 )  

References | Related Articles | Metrics

When the scale of disrupted transportation networks is large, the optimal cost allocation problem for multiple pairs of shortest paths recovery game is often intractable. In this paper, we propose a cost allocation algorithm based on Lagrangian relaxation method, which decomposes the multiple pairs of shortest paths recovery game into two subgames approximatively. We then find some properties for these two subgames which can help to solve their optimal cost allocations efficiently. According to the optimal cost allocations of the subgames, we are able to develop a near-optimal stable cost allocation for the original game. In the end, we conduct some computational experiments by checking the performance of our cost allocation algorithm on both simulated networks and the disrupted transportation network of Yushu after earthquake. The results show that our algorithm is both efficient and effective in solve optimal cost allocation problem for multiple pairs of shortest paths recovery game.

Planar Turán number and planar anti-Ramsey number of graphs

LAN Yongxin, SHI Yongtang, SONG Zixia

2021, 25(3):  200-216.  doi:10.15960/j.cnki.issn.1007-6093.2021.03.013

Asbtract ( 2359 )   HTML ( 10)   PDF (1215KB) ( 317 )  

References | Related Articles | Metrics

The planar Turán number of a graph $G$, denoted $ex_{_\mathcal{P}}(n,G)$, is the maximum number of edges in a planar graph on $n$ vertices without containing $G$ as a subgraph. Given a positive integer $n$ and a plane graph $H$, let $\mathcal{T}_n(H)$ be the family of all plane triangulations $T$ on $n$ vertices such that $T$ contains $H$ as a subgraph. The planar anti-Ramsey number of $H$, denoted $ar_{_\mathcal{P}}(n, H)$, is the maximum number $k$ such that no edge-coloring of any plane triangulation in $\mathcal{T}_n(H)$ with $k$ colors contains a rainbow copy of $H$. The study of these two topics was initiated around 2015, and has attracted extensive attention. This paper surveys results about planar Turán number and planar anti-Ramsey number of graphs. The goal is to give a unified and comprehensive presentation of the major results, as well as to highlight some open problems.