Journal of the Operations Research Society of China

Select

HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems

Jian-Feng Liu, Zi-Hao Wang, Wei Zhang, Chao-Rui Zhang, Jian-Feng Hou, Bo Bai, Gong Zhang

Journal of the Operations Research Society of China 2025, 13 (4): 1083-1107. DOI: 10.1007/s40305-023-00507-y

Abstract （754）

PDF

Save

Recently, learned heuristics have been widely applied to solve combinatorial optimization problems (e.g., traveling salesman problem (TSP)). However, the scalability of these learning-based methods hinders the applications in practical scenarios. Specifically, models pre-trained on the small-scale data generalize poorly to large-scale problems. Moreover, learning the heuristics directly for large-scale problems costs tremendous time and space. To extend the scalability of learned heuristics on TSP, we propose a Hierarchical neural framework for solving large-scale traveling salesman problems (HiTSPs) based on a divide-and-conquer strategy. In particular, the HiTSP framework first divides the large-scale problem into small-scale subproblems by node clustering. Each subproblem is conquered by a modified pointer network learned from reinforcement learning. The tour of the original TSP is constructed by linking solutions of subproblems and optimized by a novel segmented local search algorithm. Notably, the segmented local search algorithm leverages the node clustering information to prune many unnecessary operations and significantly reduces the complexity in theory. Extensive experiments show that HiTSP outperforms state-of-the-art learning-based methods and Google OR-Tools in large-scale cases. Moreover, compared to the best heuristic algorithms, HiTSP has a significant advantage in efficiency for large-scale TSP problems.

Reference | Related Articles | Metrics | Comments（0）

Select

Convexification for a Class of Global Optimization Problems with C^1,1 Functions

Qian Yan, Xin-Min Yang, Zhi-You Wu

Journal of the Operations Research Society of China 2025, 13 (4): 900-918. DOI: 10.1007/s40305-023-00521-0

Abstract （573）

PDF

Save

A general convexification method via domain transformation scheme is presented for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems with C^1,1 functions can be converted into equivalent convex optimization problems by using the proposed convexification method. Finally, an example is shown to illustrate how a monotone non-convex optimization problem can be transformed into an equivalent convex minimization problem.

Reference | Related Articles | Metrics | Comments（0）

Select

Exact Vertex Migration Model of Graph Partitioning Based on Mixed 0-1 Linear Programming and Iteration Algorithm

Zheng-Xi Yang, Zhi-Peng Jiang, Wen-Guo Yang, Sui-Xiang Gao

Journal of the Operations Research Society of China 2025, 13 (4): 919-945. DOI: 10.1007/s40305-023-00534-9

Abstract （565）

PDF

Save

Graph partitioning problem is a classical NP-hard problem. The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning. The goal of graph partitioning is getting a partition with the least number of cut edges, while also satisfying the capacity limit of the partition. In this paper, an optimization model for vertex migration is proposed, considering the influence between neighboring vertices, so that the objective function value of the model is exactly equal to the amount of cut edge variation. The model is converted into a mixed 0–1 linear programming by introducing variables. Then, a heuristic iterative algorithm is designed, in which the mixed 0–1 linear programming model is transformed into a series of small-scale models that contain less integer variables. In the experiment, the method in this paper is simulated and compared with balanced label propagation methods and their related methods. The improvement effect of these methods based on three different initialization methods is analyzed. Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.

Reference | Related Articles | Metrics | Comments（0）

Select

Analyze Accelerated Mirror Descent via High-Resolution ODEs

Ya-Xiang Yuan, Yi Zhang

Journal of the Operations Research Society of China 2025, 13 (4): 873-899. DOI: 10.1007/s40305-024-00542-3

Abstract （514）

PDF

Save

Mirror descent, which can be seen as generalization of gradient descent for solving constrained optimization problem, has found a variety applications in many fields. As growing demand of solving high-dimensional constrained optimization problem, accelerated form of mirror descent has been proposed, along with its corresponding low-resolution ordinary differential equations (ODEs) framework has been studied. However, The low-resolution ODEs are unable to distinguish between Polyak’s heavy-ball method and Nesterov’s accelerated gradient method. This problem also arises with the low-resolution ODEs for accelerated mirror descent. To address this issue, we derive the high-resolution ODEs for accelerated mirror descent and propose a general Lyapunov function framework to analyze its convergence rates in both continuous time and discrete time. Furthermore, we demonstrate that the accelerated mirror descent can minimize the squared gradient norm at an inverse cubic rate by using the high-resolution ODEs framework. In the end, we extend the high-resolution ODEs framework for the accelerated mirror descent method to analyze the accelerated higher-order mirror descent and obtain finer convergence results.

Reference | Related Articles | Metrics | Comments（0）

Select

Scheduling Games with Potential Penalties on the Move of Jobs

Zhu-Yi-Nan Wang, Chen Zhang, Zhi-Yi Tan

Journal of the Operations Research Society of China 2025, 13 (4): 1157-1180. DOI: 10.1007/s40305-023-00501-4

Abstract （483）

PDF

Save

This paper studies scheduling games with potential penalties on the move of jobs. There are a set of machines and a set of jobs. Each job could choose one machine and be processed by the chosen one. Jobs that try to change their original choice will incur additional costs, which is proportional to its processing time with proportional parameter $\delta \geqslant 0$. A schedule is a $\delta$-NE if no job has the incentive to change its choice unilaterally. The $\delta$-NE is a generation of Nash equilibrium, and its inefficiency can be measured by the $\delta$-PoA, which is also a generalization of the Price of Anarchy. For the game with the social cost of minimizing the makespan, the exact $\delta$-PoA for any number of machines and any $\delta \geqslant 0$ is obtained. For the game with the social cost of maximizing the minimum machine load, an upper bound on the $\delta$-PoA is presented, and tight bounds are given for $2 \leqslant m \leqslant 11$ and any $\delta \geqslant 0$, where $m$ is the number of machines.

Reference | Related Articles | Metrics | Comments（0）

Select

Optimal Investment Strategies for DC Pension Plan with Administrative Fees and Return of Premiums Clauses Under the Heston Model

Jian Pan, Xiang-Ying Zhou

Journal of the Operations Research Society of China 2025, 13 (4): 1018-1047. DOI: 10.1007/s40305-023-00505-0

Abstract （442）

PDF

Save

In this paper, we study an optimal investment problem for a defined contribution (DC) pension plan with two administrative fees during the accumulation phase. In our model, the pension fund member contributes a predetermined amount of money as a premium and then the pension fund administrator invests the premium in a financial market to increase the value of the accumulation, where the financial market consists of a risk-free asset and a risky asset satisfied the Heston model. Besides, to protect the rights of pension fund members who die before retirement, we introduce a return of premiums clauses and use the Abraham De Moivre model to characterize the force of mortality. With the help of actuarial theory and Taylor expansion theorem, we formalize the problem as a continuous-time portfolio optimization problem. By applying the stochastic control method and variable change techniques, we derive closed-form expressions of optimal investment strategies and corresponding value functions under the power utility function and exponential utility function. Based on the closed-form expressions, we determine the equivalent administrative charges by equating the maximum terminal certainty equivalent that can be achieved under the two types of administrative charges and find out some relationships between the two charges under the same utility function. Finally, we provide numerical experiments to analyze the effects of some parameters on the optimal investment strategy, the value function and the relationship between the two equivalent administrative charges.

Reference | Related Articles | Metrics | Comments（0）

Select

Properties Related with Conditional Expectation for a Non-homogeneous Poisson Process

Yu Wu, Bo Zeng

Journal of the Operations Research Society of China 2025, 13 (4): 1066-1082. DOI: 10.1007/s40305-023-00527-8

Abstract （441）

PDF

Save

In this paper, we study a non-homogeneous Poisson Process that generalizes the well-known Jelinski-Moranda (J-M) model, originally proposed as a predictive model for software failures. The process under investigation consists of a fixed number of identical independent Poisson arrival processes, each operating from a common starting point until its first arrival occurs. While numerous studies in the field of software reliability are built upon the J-M model, there is a dearth of existing literature that examines the properties of this generalized version beyond software reliability. Considering this process is very common in real-world scenarios situated within stochastic environments, our study focuses solely on its theoretical exploration of general mathematical properties. First we formally define it in two ways, and clarify its relationships with established models such as continuous-time Markov Chain, Markov process and Markov Arrival Process by constructing it as a special case. Then, within the framework of Poisson process, we delve into an analysis of specific properties related to conditional expectations, with our primary contribution being in the computation of expected conditional arrival times.

Reference | Related Articles | Metrics | Comments（0）

Select

Computation over t-Product Based Tensor Stiefel Manifold: A Preliminary Study

Xian-Peng Mao, Ying Wang, Yu-Ning Yang

Journal of the Operations Research Society of China 2025, 13 (4): 1108-1156. DOI: 10.1007/s40305-023-00522-z

Abstract （430）

PDF

Save

Let $*$ denote the t -product between two third-order tensors proposed by Kilmer and Martin (Linear Algebra Appl 435(3): 641-658, 2011). The purpose of this work is to study fundamental computation over the set $\operatorname{St}(n, p, l):=\left\{\mathcal{X} \in \mathbb{R}^{n \times p \times l} \mid \mathcal{X}^{\top} * \mathcal{X}=\right. \mathcal{I}\}$, where $\mathcal{X}$ is a third-order tensor of size $n \times p \times l(n \geqslant p)$ and $\mathcal{I}$ is the identity tensor. It is first verified that St ( $n, p, l$) endowed with the Euclidean metric forms a Riemannian manifold, which is termed as the (third-order) tensor Stiefel manifold in this work. We then derive the tangent space, Riemannian gradient, and Riemannian Hessian on St ($n, p, l$). In addition, formulas of various retractions based on t-QR, t-polar decomposition, t-Cayley transform, and t-exponential, as well as vector transports, are presented. It is expected that analogous to their matrix counterparts, the derived formulas may serve as building blocks for analyzing optimization problems over the tensor Stiefel manifold and designing Riemannian algorithms.

Reference | Related Articles | Metrics | Comments（0）

Select

On the Existence of Solutions for Weak Nonlinear Bilevel Optimization Problems

Houda Keraoui, Fatima-Ezzahra Saissi, Abdelmalek Aboussoror

Journal of the Operations Research Society of China 2025, 13 (4): 1048-1065. DOI: 10.1007/s40305-023-00515-y

Abstract （419）

PDF

Save

In this paper,we are concernedwith aweak(pessimistic) nonlinear bilevel optimization problem. In a sequential setting, for such a problem, we provide sufficient conditions ensuring the existence of solutions via a regularization and the notion of variational convergence. Unlike the approaches adopted by Aboussoror and Loridan (J Math Anal Appl 254: 348-357, 2001) and Aboussoror (Adv Math Res 1: 83-92, 2002), our approach does not require convexity assumptions and gives an extension from the finite dimensional case to a general topological one. Moreover, it gives an improvement of the result given by Loridan and Morgan (in: Buhler et al. (ed) Operations Research Proceedings of the international Conference on Operations Research 90 in Vienna, Springer Verlag, Berlin 1992).

Reference | Related Articles | Metrics | Comments（0）

Select

Revisit the Coloring Problem of Gallai Graphs

Qiu-Lan Zhao, Jin-Jiang Yuan

Journal of the Operations Research Society of China 2025, 13 (4): 1216-1225. DOI: 10.1007/s40305-023-00510-3

Abstract （419）

PDF

Save

Given a graph $G=(V, E)$, the Gallai graph of $G$, denoted by $\Gamma(G)$, is the graph with vertex set $E$ in which two edges $e$ and $f$ of $G$ are adjacent in $\Gamma(G)$ iff $e$ and $f$ are adjacent in $G$ but do not span a triangle in $G$. The Gallai chromatic number of $G$, denoted by $\chi^{\Gamma}(G)$, is defined to be the chromatic number of $\Gamma(G)$. It is known that the problem for determining $\chi^{\Gamma}(G)$ is NP-complete for a general graph $G$. In this paper, we study the Gallai chromatic number of graphs and relate our research with some parameters about edge coloring of graphs, such as PC number, SPC number, as well as chromatic index. For the $(k, r)$-star, we determine its PC number, SPC number, Gallai chromatic number, and chromatic index, and show that these parameters differ considerably in a sense. Then we show that the problem for determining $\chi^{\Gamma}(G)$ is still NP-complete even when $G$ is a 3-regular graph, a near-complete graph or a chordal graph of diameter 5 . Our result also implies that the problem for determining the SPC number of a graph $G$ is NP-complete when $G$ is a chordal graph of diameter 5.

Reference | Related Articles | Metrics | Comments（0）

Select

On Forcibly k-Connected Uniform Hypergraphic Sequences

Xue-Mei Liu, Ji-Xiang Meng, Ying-Zhi Tian

Journal of the Operations Research Society of China 2025, 13 (4): 1205-1215. DOI: 10.1007/s40305-023-00509-w

Abstract （409）

PDF

Save

For two nondecreasing sequences $d=\left(d_1, d_2, \cdots, d_n\right)$ and $d^{\prime}=\left(d_1^{\prime}, d_2^{\prime}, \cdots, d_n^{\prime}\right)$ of nonnegative integers, we say that $d^{\prime}$ majorizes $d$, denoted by $d^{\prime} \geqslant d$, if $d_i^{\prime} \geqslant d_i$ for $1 \leqslant i \leqslant n$. An $r$-uniform hypergraphic sequence $d=\left(d_1, d_2, \cdots, d_n\right)$ is forcibly $k$-connected if every $r$-uniform hypergraph with degree sequence $d$ is $k$-connected. In this paper, we give a sufficient condition for an $r$-uniform hypergraphic sequence to be forcibly $k$-connected and observe that if an $r$-uniform hypergraphic sequence $d$ satisfies the condition (which implies $d$ is forcibly $k$-connected); then, any $r$-uniform hypergraphic sequence $d^{\prime} \geqslant d$ also satisfies the condition. As a corollary, we obtain the condition of Bondy for forcibly $k$-connected graphic sequences.

Reference | Related Articles | Metrics | Comments（0）

Select

Some Properties of the Solution of the Extended Vertical Tensor Complementarity Problem

Li-Ming Li, Shi-Liang Wu, Cui-Xia Li

Journal of the Operations Research Society of China 2025, 13 (4): 946-965. DOI: 10.1007/s40305-023-00531-y

Abstract （367）

PDF

Save

In this paper, we introduce the extended vertical tensor complementarity problem and investigate the existence and uniqueness of its solution. We introduce several sets of special tensors and demonstrate their properties. We leverage the structure of tensors to obtain some properties of the solution of the extended vertical tensor complementarity problem. Furthermore, we use degree theory and the equivalent form of the minimum function to establish sufficient conditions for the existence and uniqueness of the solution of the extended vertical tensor complementarity problem, respectively.

Reference | Related Articles | Metrics | Comments（0）

Select

Stability Analysis of a Car-Following Model with Effect of Driver’s Memory Delay in Connected Vehicle Environment

Wen-Ju Du, Yin-Zhen Li, Jian-Gang Zhang

Journal of the Operations Research Society of China 2025, 13 (4): 1181-1204. DOI: 10.1007/s40305-023-00508-x

Abstract （352）

PDF

Save

The paper investigated the stability of a car-following model with the effect of driver’s memory delay on the basis of synchronization theory of complex network with time delay in connected vehicle environment. By using the Lyapunov stability theory and designing the appropriate controller, the car-following model with the effect of driver’s memory delay is quickly stabilized and the stability condition of the model is obtained. Besides, based on the adaptive H_∞ synchronization theory for complex networks with time delay, the stability of car-followingmodel with the effect of driver’smemory delay is studied when the vehicles are subjected to random external disturbance. Finally, the numerical simulation is carried out by using MATLAB simulation technology; the results show that the car-following model with the effect of driver’s memory delay is rapidly stabilizing and congestion phenomenon is effectively alleviated under the controller designed.

Reference | Related Articles | Metrics | Comments（0）

Select

Review of Large-Scale Simulation Optimization

Wei-Wei Fan, L. Jeff Hong, Guang-Xin Jiang, Jun Luo

Journal of the Operations Research Society of China 2025, 13 (3): 688-722. DOI: 10.1007/s40305-025-00599-8

Abstract （349）

PDF

Save

Large-scale simulation optimization (SO) problems encompass both large-scale ranking-and-selection problems and high-dimensional discrete or continuous SO problems, presenting significant challenges to existing SO theories and algorithms. This paper begins by providing illustrative examples that highlight the differences between large-scale SO problems and those of a more moderate scale. Subsequently, it reviews several widely employed techniques for addressing large-scale SO problems, such as divide-and-conquer, dimension reduction, and gradient-based algorithms. Additionally, the paper examines parallelization techniques leveraging widely accessible parallel computing environments to facilitate the resolution of large-scale SO problems.

Reference | Related Articles | Metrics | Comments（0）

Select

On the Metric Resolvent: Nonexpansiveness, Convergence Rates and Applications

Feng Xue

Journal of the Operations Research Society of China 2025, 13 (4): 966-988. DOI: 10.1007/s40305-023-00518-9

Abstract （331）

PDF

Save

In this paper, we study the nonexpansive properties of metric resolvent and present the convergence analysis for the associated fixed-point iterations of both Banach-Picard and Krasnosel’ski$\breve{1}$–Mann types. A by-product of our expositions also extends the proximity operator and Moreau’s decomposition identity to arbitrary metric. It is further shown that many classes of the first-order operator splitting algorithms, including the alternating direction methods of multipliers, primal–dual hybrid gradient and Bregman iterations, can be expressed by the fixed-point iterations of a simple metric resolvent, and thus, the convergence can be easily obtained within this unified framework.

Reference | Related Articles | Metrics | Comments（0）

Select

A Second-Order Cone Relaxation-Based Branch-and-Bound Algorithm for Complex Quadratic Programs on Acyclic Graphs

Yang-He Liu, Ying-Zhe Xu, Cheng Lu, Zhi-Bin Deng

Journal of the Operations Research Society of China 2025, 13 (4): 989-1017. DOI: 10.1007/s40305-023-00506-z

Abstract （328）

PDF

Save

Complex quadratically constrained quadratic programs (QCQPs) with underlying acyclic graph structures have special interests in some important practical applications. In this paper, we propose a new second-order cone relaxation for complex QCQPs, and prove some sufficient conditions under which the proposed relaxation is tight. Then, based on the proposed second-order cone relaxation, a branch-and-bound algorithm is developed. The main feature of the proposed branch-and-bound algorithm is that some complex variables are selected with their bounds on modules or phase angles partitioned in the branching procedure. Numerical results indicate that the proposed branch-and-bound algorithm runs faster than Baron on randomly generated test instances, and is also effective in solving some publicly available test instances of optimal power flow problems.

Reference | Related Articles | Metrics | Comments（0）

Select

Global Optimization for the Portfolio Selection Model with High-Order Moments

Liu Yang, Yi Yang, Su-Han Zhong

Journal of the Operations Research Society of China 2025, 13 (4): 1226-1247. DOI: 10.1007/s40305-023-00519-8

Abstract （328）

PDF

Save

In this paper, we study the global optimality of polynomial portfolio optimization (PPO). The PPO is a kind of portfolio selection model with high-order moments and flexible risk preference parameters. We introduce a perturbation sample average approximation method, which can give a robust approximation of the PPO in form of linear conic optimization. The approximated problem can be solved globally with Moment-SOS relaxations. We summarize a semidefinite algorithm, which can be used to find reliable approximations of the optimal value and optimizer set of the PPO. Numerical examples are given to show the efficiency of the algorithm.

Reference | Related Articles | Metrics | Comments（0）

Select

Black-Box Rare-Event Simulation for Safety Testing of AI Agents: An Overview

Yuan-Lu Bai, Zhi-Yuan Huang, Henry Lam, Ding Zhao

Journal of the Operations Research Society of China 2025, 13 (3): 750-774. DOI: 10.1007/s40305-025-00585-0

Abstract （308）

PDF

Save

This paper provides an overview of black-box rare-event simulation methods applicable to the safety testing of artificial intelligence agents. We explore the challenges and efficiency criteria in black-box simulation, especially emphasizing the subtle occurrence and control of underestimation errors. The paper reviews various adaptive methods, such as the cross-entropy method and adaptive multilevel splitting, highlighting both their empirical effectiveness and theoretical limitations. Additionally, it offers a comparative analysis of different confidence interval constructions for crude Monte Carlo methods, aiming to mitigate underestimation errors through effective uncertainty quantification. The paper concludes with a certifiable deep importance sampling approach, using deep neural networks to develop conservative estimators that address underestimation issues.

Reference | Related Articles | Metrics | Comments（0）

Select

Blackbox Simulation Optimization

Hao Cao, Jian-Qiang Hu, Teng Lian

Journal of the Operations Research Society of China 2025, 13 (3): 723-749. DOI: 10.1007/s40305-024-00549-w

Abstract （298）

PDF

Save

Simulation optimization is a widely used tool in the analysis and optimization of complex stochastic systems. The majority of the previous works on simulation optimization rely heavily on detailed system information, such as the distributions of input variables and the system dynamics. However, it is usually costly and even unrealistic to obtain such detailed information in practice. To overcome this difficulty, new methods are needed to solve stochastic optimization problems based on simulation outputs or real-world data and fairly limited knowledge of the underlying system, i.e., in a blackbox setting. In this paper, we provide an up-to-date overview of the subject of blackbox simulation optimization, which has only been attracting attention from the simulation community in recent years. We discuss some of the new stochastic approximation algorithms developed recently for blackbox stochastic optimization. We also discuss challenges and potential future research opportunities.

Reference | Related Articles | Metrics | Comments（0）

Select

Simulation Budget Allocation for Improving Scheduling and Routing of Automated Guided Vehicles in Warehouse Management

Gong-Bo Zhang, Hao-Bin Li, Xiao-Tian Liu, Yi-Jie Peng

Journal of the Operations Research Society of China 2025, 13 (3): 775-809. DOI: 10.1007/s40305-024-00553-0

Abstract （269）

PDF

Save

Simulation budget allocation is a widely used technique for evaluating and optimizing dynamic discrete event stochastic system via efficient sampling. In warehouse management, the scheduling and routing algorithms of automated guided vehicles aim to optimize order assignments and travel paths under certain constraints to achieve specific objectives. However, these algorithms often rely on deterministic optimization methods, neglecting the dynamic and stochastic nature of warehouse management systems. In this work, we propose an efficient method that integrates simulation budget allocation methods with deterministic scheduling and routing algorithms to enhance overall system performance. The proposed method leverages the benefits of both simulation optimization and deterministic optimization techniques, accounting for the inherent uncertainty of the system. We adopt a discrete event simulation model used in the Case Study Competition of the 2022 Winter Simulation Conference, where the objective is to minimize the adjusted average order cycle time (ACT) in a given warehouse simulation scenario. Numerical examples demonstrate that the use of simulation budget allocation methods can significantly further reduce the ACT, thereby highlighting the effectiveness of our proposed method.

Reference | Related Articles | Metrics | Comments（0）

Most Read