Most Read

Published in last 1 year |  In last 2 years |  In last 3 years |  All Please wait a minute... For Selected: Download Citations EndNote Ris BibTeX Toggle Thumbnails Select The Multi-visits Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery Service Si Zhang, Lu Li Journal of the Operations Research Society of China    2024, 12 (4): 965-995.   DOI: 10.1007/s40305-023-00471-7 Abstract （1058）      PDF       Knowledge map    Save The development of convergent technology makes the drone expected to become a commercial delivery method for terminal logistics distribution. Although the industry has begun to experiment with the coordinated transportation of drones and vehicles, some limited assumptions have been made to reduce the complexity of synchronization. This paper studies the mathematical formulations and efficient solution methodologies for the multi-visits drone-vehicle routing problem with simultaneous pickup and delivery service (MDVRPSPD), whose objective is to minimize the distance traveled by drones and vehicles and the total number of drones used. To solve the MDVRPSPD problem, a three-stage solution method is designed. Firstly, the scalable K-means++ algorithm is used to determine the vehicle’s parking location, and we optimize the vehicle’s driving route by traveling salesman problem (TSP) modeling; then, the classic tabu search algorithm is extended to arrange the schedule of drones which consider multi-visits and simultaneous pickup and delivery service. Meanwhile, a set of extensive computational experiments are conducted to demonstrate the efficiency of developed heuristics and the superiority of drone-vehicle delivery system on delivery issues. Reference | Related Articles | Metrics | Comments（0） Select Disjoint Cycles and Degree Sum Condition in a Graph Chun-Jiao Song, Yun Wang, Jin Yan Journal of the Operations Research Society of China    2024, 12 (4): 1072-1087.   DOI: 10.1007/s40305-023-00473-5 Abstract （924）      PDF       Knowledge map    Save For an integer t, where t ≥ 2, let σt(G) denote the minimum degree sum of an independent set with t vertices in a graph G. We prove that for two integers k, t with k ≥ 3, t ≥ 4, every graph G with |V(G)| ≥ kt + 1.5k + t and σt(G) ≥ 2kt -t +1 contains k disjoint cycles. This result improves the theorem of Ma and Yan by optimizing the lower bound of |V(G)|. In addition, we also improve the theorem of Gould et al. for t = 4 and k ≥ 2. Reference | Related Articles | Metrics | Comments（0） Select A General Framework for Nonconvex Sparse Mean-CVaR Portfolio Optimization Via ADMM Ke-Xin Sun, Zhong-Ming Wu, Neng Wan Journal of the Operations Research Society of China    2024, 12 (4): 1022-1047.   DOI: 10.1007/s40305-024-00551-2 Abstract （892）      PDF       Knowledge map    Save This paper presents a general framework for addressing sparse portfolio optimization problems using the mean-CVaR (Conditional Value-at-Risk) model and regularization techniques. The framework incorporates a non-negative constraint to prevent the portfolio from being too heavily weighted in certain assets. We propose a specific ADMM (alternating directional multiplier method) for solving themodel and provide a subsequential convergence analysis for theoretical integrity. To demonstrate the effectiveness of our framework, we consider the $\ell$1 and SCAD (smoothly clipped absolute deviation) penalties as notable instances within our unified framework. Additionally, we introduce a novel synthesis of the CVaR-based model with $\ell$1/$\ell$2 regularization. We explore the subproblems of ADMM associated with CVaR and the presented regularization functions, employing the gradient descent method to solve the subproblem related to CVaR and the proximal operator to evaluate the subproblems with respect to penalty functions. Finally, we evaluate the proposed framework through a series of parametric and out-of-sample experiments, which shows that the proposed framework can achieve favorable out-of-sample performance. We also compare the performance of the proposed nonconvex penalties with that of convex ones, highlighting the advantages of nonconvex penalties such as improved sparsity and better risk control. Reference | Related Articles | Metrics | Comments（0） Select Single-Machine Scheduling with Step-Deteriorating Jobs and Rejection Fan-Yu Kong, Cui-Xia Miao, Yu-Jia Huo, Jia-Xin Song, Yu-Zhong Zhang Journal of the Operations Research Society of China    2024, 12 (4): 1088-1102.   DOI: 10.1007/s40305-023-00481-5 Abstract （859）      PDF       Knowledge map    Save In this paper, we consider the single-machine scheduling with step-deteriorating jobs and rejection. Each job is either rejected by paying a rejection penalty, or accepted and processed on the single machine, and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date. The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. For the case of common deteriorating penalty, we first show that the problem is NP-hard in the ordinary sense. Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm. Furthermore, we propose a fully polynomial time approximation scheme. For the case of common normal processing time, we present two pseudo-polynomial time algorithms, a 2-approximation algorithm and a fully polynomial time approximation scheme. Reference | Related Articles | Metrics | Comments（0） Select An Accelerated Stochastic Mirror Descent Method Bo-Ou Jiang, Ya-Xiang Yuan Journal of the Operations Research Society of China    2024, 12 (3): 549-571.   DOI: 10.1007/s40305-023-00492-2 Abstract （858）      PDF       Knowledge map    Save Driven by large-scale optimization problems arising from machine learning, the development of stochastic optimization methods has witnessed a huge growth. Numerous types of methods have been developed based on vanilla stochastic gradient descent method. However, for most algorithms, convergence rate in stochastic setting cannot simply match that in deterministic setting. Better understanding the gap between deterministic and stochastic optimization is the main goal of this paper. Specifically, we are interested in Nesterov acceleration of gradient-based approaches. In our study, we focus on acceleration of stochastic mirror descent method with implicit regularization property. Assuming that the problem objective is smooth and convex or strongly convex, our analysis prescribes the method parameters which ensure fast convergence of the estimation error and satisfied numerical performance. Reference | Related Articles | Metrics | Comments（0） Select Competitive Resource Allocation Among Urban Congestion Areas in a Modern Big City Alexander Krylatov, Anastasiya Raevskaya Journal of the Operations Research Society of China    2024, 12 (1): 133-153.   DOI: 10.1007/s40305-023-00530-z Abstract （857）      PDF       Knowledge map    Save The continuing growth of modern big cities leads to their spatial expansion and the emergence of new road connections and urban areas. Areas where large transportation flows of pedestrians, passengers, and drivers come together create demand points, which attract business companies that strive to allocate their resources in the most sought-after places. However, the law of supply and demand restrains companies from allocating all their resources solely in the most popular congestion areas since the more valuable an urban area, the higher the cost to be paid for a resource unit allocation there. As a result, companies act in a non-cooperative manner and try to minimize their own overall costs when allocating resources across available commercial areas in a big city. Non-cooperative behavior of companies leads to the problem of Nash equilibrium search in the game of competing entrepreneurs. In this paper, we study the corresponding resource allocation game under affine cost functions and obtain Nash equilibrium strategies in explicit form. These findings allow us to develop a simple procedure for computing Nash equilibria in the game of companies allocating their resources among urban congestion areas. The computational study demonstrates the dependence of the average price for resource allocation on the number of players and their resource volumes. The outcome of the paper contributes to flow theory and seems to be fresh and useful for managers. Reference | Related Articles | Metrics | Comments（0） Select A Note on R-Linear Convergence of Nonmonotone Gradient Methods Xin-Rui Li, Ya-Kui Huang Journal of the Operations Research Society of China    2025, 13 (1): 313-325.   DOI: 10.1007/s40305-023-00468-2 Abstract （841）      PDF       Knowledge map    Save Nonmonotone gradient methods generally perform better than their monotone counterparts especially on unconstrained quadratic optimization. However, the known convergence rate of the monotone method is often much better than its nonmonotone variant. With the aim of shrinking the gap between theory and practice of nonmonotone gradient methods, we introduce a property for convergence analysis of a large collection of gradient methods. We prove that any gradient method using stepsizes satisfying the property will converge R-linearly at a rate of 1-λ1/M1, where λ1 is the smallest eigenvalue of Hessian matrix and M1 is the upper bound of the inverse stepsize. Our results indicate that the existing convergence rates of many nonmonotone methods can be improved to 1-1/κ with κ being the associated condition number. Reference | Related Articles | Metrics | Comments（0） Select The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang Journal of the Operations Research Society of China    2023, 11 (4): 735-758.   DOI: 10.1007/s40305-022-00425-5 Abstract （840）      PDF       Knowledge map    Save We present an orthogonal matrix outer product decomposition for the fourth-order conjugate partial-symmetric (CPS) tensor and show that the greedy successive rank-one approximation (SROA) algorithm can recover this decomposition exactly. Based on this matrix decomposition, the CP rank of CPS tensor can be bounded by the matrix rank, which can be applied to low-rank tensor completion. Additionally, we give the rank-one equivalence property for the CPS tensor based on the SVD of matrix, which can be applied to the rank-one approximation for CPS tensors. Reference | Related Articles | Metrics | Comments（0） Select Polar Decomposition-based Algorithms on the Product of Stiefel Manifolds with Applications in Tensor Approximation Jian-Ze Li, Shu-Zhong Zhang Journal of the Operations Research Society of China    2024, 12 (4): 874-920.   DOI: 10.1007/s40305-023-00462-8 Abstract （839）      PDF       Knowledge map    Save In this paper, we propose a general algorithmic framework to solve a class of optimization problems on the product of complex Stiefel manifolds based on the matrix polar decomposition. We establish the weak convergence, global convergence and linear convergence properties, respectively, of this general algorithmic approach using the Łojasiewicz gradient inequality and the Morse-Bott property. This general algorithmic approach and its convergence results are applied to the simultaneous approximate tensor diagonalization problem and the simultaneous approximate tensor compression problem, which include as special cases the low rank orthogonal approximation, best rank-1 approximation and low multilinear rank approximation for higher order complex tensors. We also present a variant of this general algorithmic framework to solve a symmetric version of this class of optimization models, which essentially optimizes over a single Stiefel manifold. We establish its weak convergence, global convergence and linear convergence properties in a similar way. This symmetric variant and its convergence results are applied to the simultaneous approximate symmetric tensor diagonalization, which includes as special cases the low rank symmetric orthogonal approximation and best symmetric rank-1 approximation for higher order complex symmetric tensors. It turns out that well-known algorithms such as LROAT, S-LROAT, HOPM and S-HOPM are all special cases of this general algorithmic framework and its symmetric variant, and our convergence results subsume the results found in the literature designed for those special cases. All the algorithms and convergence results in this paper are straightforwardly applicable to the real case. Reference | Related Articles | Metrics | Comments（0） Select Expected Residual Minimization Method for Stochastic Tensor Variational Inequalities Tong-Tong Shang, Guo-Ji Tang Journal of the Operations Research Society of China    2024, 12 (4): 1048-1071.   DOI: 10.1007/s40305-022-00450-4 Abstract （827）      PDF       Knowledge map    Save The goal of this paper is to introduce and investigate a model called the stochastic tensor variational inequality (denoted by STVI), which is a natural extension of the stochastic linear complementarity problem and the stochastic affine variational inequality. Firstly, the STVI is transformed into an expected residual minimization (ERM) problem involved the regularized gap function. Then, the properties of the ERM problem are investigated. Finally, a discrete approximation of ERM problem is obtained by quasi-Monte Carlo method. The convergence of optimal solutions and stationary points of the approximation problem are analyzed as well. Reference | Related Articles | Metrics | Comments（0） Select MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound Meng-Yu Huang, Ling-Ying Huang, Yu-Xing Zhong, Hui-Wen Yang, Xiao-Meng Chen, Wei Huo, Jia-Zheng Wang, Fan Zhang, Bo Bai, Ling Shi Journal of the Operations Research Society of China    2025, 13 (1): 1-55.   DOI: 10.1007/s40305-023-00493-1 Abstract （826）      PDF       Knowledge map    Save Mixed integer linear programming (MILP) is an NP-hard problem, which can be solved by the branch and bound algorithm by dividing the original problem into several subproblems andforming a search tree. For each subproblem, linear programming(LP) relaxation can be solved to find the boundformaking thefollowing decisions. Recently, with the increasing dimension of MILPs in different applications, how to accelerate the solution process becomes a huge challenge. In this survey, we summarize techniques and trends to speed up MILP solving from two perspectives. First, we present different approaches in simplex initialization, which can help to accelerate the solution of LP relaxation for each subproblem. Second, we introduce the learning-based technologies in branch and bound algorithms to improve decision making in tree search. We also propose several potential directions and extensions to further enhance the efficiency of solving different MILP problems. Reference | Related Articles | Metrics | Comments（0） Select Existence of α-Cores for Games Without Compact Assumptions Hai-Qun Zhang Journal of the Operations Research Society of China    2024, 12 (2): 520-527.   DOI: 10.1007/s40305-022-00420-w Abstract （815）      PDF       Knowledge map    Save Following the representation of Kajii (J Econ Theory 56:194–205, 1992), we provide some existence theorems of α-cores for games without ordered preferences and compact assumptions. As applications, we obtain some existence results of the α-core for normal-form games without compact assumptions. Reference | Related Articles | Metrics | Comments（0） Select The Single-Machine Preemptive or Resumable Scheduling with Maintenance Intervals Ru-Yan He, Jin-Jiang Yuan, Yuan Zhang Journal of the Operations Research Society of China    2025, 13 (2): 590-602.   DOI: 10.1007/s40305-023-00495-z Abstract （814）      PDF       Knowledge map    Save We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern, respectively, to minimize the total weighted late work and the weighted number of tardy jobs, respectively, where each job has a release date and a due date. According to the different combinations of the two scheduling patterns and the two scheduling criteria, six scheduling problems (including two Pareto-scheduling problems) are studied in this paper. We show that by modifying the release dates and the due dates, the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time. As a consequence, complexity results of our problems can be directly obtained from the known results in the literature. In particular, for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time 0, an \begin{document}$ O(m{n^2}{P}) $\end{document}-time algorithm was presented in the literature, where m is the number of maintenance intervals, n is the number of jobs, and P is the total processing time of the jobs; and our research shows that the same problem is solvable in \begin{document}$ O(n^{2}{P}+m\log m ) $\end{document} time, improving this known result. Reference | Related Articles | Metrics | Comments（0） Select Ramsey Numbers of Stripes Versus Trees and Unicyclic Graphs Si-Nan Hu, Yue-Jian Peng Journal of the Operations Research Society of China    2025, 13 (1): 297-312.   DOI: 10.1007/s40305-023-00494-0 Abstract （807）      PDF       Knowledge map    Save For graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any coloring of the edges of the complete graph KN in red or blue yields a red G or a blue H. Denote the union of t disjoint copies of a graph F by tF. We call tK2 a stripe. In this paper, we completely determine Ramsey numbers of stripes versus trees and unicyclic graphs. Our result also implies that a tree is tK2-good if and only if the independence number of this tree is no less than t. As an application, we improve the known Ramsey numbers of stars versus fan graphs. Moreover, we determine the bipartite Ramsey numbers of a connected bipartite graph versus stripes. Reference | Related Articles | Metrics | Comments（0） Select Turán Numbers of Expanded Intersecting Cliques in 3-graphs Yu-Cong Tang, Tong Li, Gui-Ying Yan Journal of the Operations Research Society of China    2024, 12 (4): 952-964.   DOI: 10.1007/s40305-022-00451-3 Abstract （784）      PDF       Knowledge map    Save Let $\ell$ > r ≥ 3. Given a 2-graph F, the expansion F(r) of F is an r-graph obtained from F by adding r - 2 new vertices into each edge. When F is a clique of order $\ell$, the Turán number ex(n, F(r)) was first asymptotically determined by Mubayi (J Comb Theory Ser B 96:122-134, 2006) and exactly computed by Pikhurko (J Comb Theory Ser B 103:220-225, 2013). Let Fk,$\ell$ be the 2-graph on ($\ell$-1)k + 1 vertices consisting of k cliques of order $\ell$ intersecting at exactly one vertex. We determine the exact Turán number ex(n, Fk,$\ell$(3)) for all $\ell$ > 3, k ≥ 1 and sufficiently large n, as well as the corresponding extremal graphs. Reference | Related Articles | Metrics | Comments（0） Select Gallai's Conjecture on Path Decompositions Geng-Hua Fan, Jian-Feng Hou, Chui-Xiang Zhou Journal of the Operations Research Society of China    2023, 11 (3): 439-449.   DOI: 10.1007/s40305-022-00435-3 Abstract （768）      PDF       Knowledge map    Save Gallai's conjecture asserts that every connected graph on n vertices can be decomposed into at most $\frac{{n + 1}}{2}$ paths. The E-subgraph of a graph G, denoted by $ G_e $, is the subgraph induced by the vertices of even degree in G. A triangle pair is a graph consisting of two triangles with exactly one vertex in common. In this paper, it is proved that Gallai's conjecture is true for graphs G in which $ G_e $ contains no triangle pair and each block of $ G_e $ has maximum degree at most 3. Reference | Related Articles | Metrics | Comments（0） Select Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times Man Xiao, Yu-Fei Du, Wei-Dong Li, Jin-Hua Yang Journal of the Operations Research Society of China    2024, 12 (4): 1126-1138.   DOI: 10.1007/s40305-023-00477-1 Abstract （766）      PDF       Knowledge map    Save In this paper, we consider the problem of semi-online machine covering on three machines with two hierarchies, whose objective is to maximize the minimum machine load. Since there is no online algorithm with bounded competitive ratio for the online machine covering problem, we consider the semi-online case where the processing times of all jobs lie in [1, α]. When there are one machine of hierarchy 1 and two machines of hierarchy 2, we design an optimal online algorithm with a competitive ratio of 1 + α. When there are two machines of hierarchy 1 and one machine of hierarchy 2, we give an optimal online algorithm with a competitive ratio of 1 + 2α. Reference | Related Articles | Metrics | Comments（0） 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 （762）      PDF       Knowledge map    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 Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R2 Using Stock Pieces of Materials with Fixed Length Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng Journal of the Operations Research Society of China    2024, 12 (4): 996-1021.   DOI: 10.1007/s40305-022-00443-3 Abstract （758）      PDF       Knowledge map    Save In this paper, we address the problem of constructing a Steiner tree in the Euclidean plane $\mathbb{R}^2$ using stock pieces of materials with fixed length, which is modelled as follows. Given a set X = {r1,r2, …,rn} of n terminals in $\mathbb{R}^2$ and some stock pieces of materials with fixed length L, we are asked to construct a Steiner tree T interconnecting all terminals in X, and each edge in T must be constructed by a part of that stock piece of material. The objective is to minimize the cost of constructing such a Steiner tree T, where the cost includes three components, (1) The cost of Steiner points needed in T; (2) The construction cost of constructing all edges in T and (3) The cost of stock pieces of such materials used to construct all edges in T. We can obtain two main results. (1) Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem, we present a simple 4-approximation algorithm in time O(nlogn) to solve this new problem; (2) Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the binpacking problem, we design a 3-approximation algorithm in time O(n3) to resolve this new problem. Reference | Related Articles | Metrics | Comments（0） Select Low Rank Tensor Decompositions and Approximations Jiawang Nie, Li Wang, Zequn Zheng Journal of the Operations Research Society of China    2024, 12 (4): 847-873.   DOI: 10.1007/s40305-023-00455-7 Abstract （743）      PDF       Knowledge map    Save There exist linear relations among tensor entries of low rank tensors. These linear relations can be expressed by multi-linear polynomials, which are called generating polynomials. We use generating polynomials to compute tensor rank decompositions and low rank tensor approximations. We prove that this gives a quasi-optimal low rank tensor approximation if the given tensor is sufficiently close to a low rank one. Reference | Related Articles | Metrics | Comments（0）