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 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 （407）      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 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 （386）      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 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 （379）      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 Directional Derivative and Subgradient of Cone-Convex Set-Valued Mappings with Applications in Set Optimization Problems Yu Han Journal of the Operations Research Society of China    2024, 12 (4): 1103-1125.   DOI: 10.1007/s40305-023-00454-8 Abstract （366）      PDF       Knowledge map    Save In this paper, we introduce a new directional derivative and subgradient of set-valued mappings by using a nonlinear scalarizing function. We obtain some properties of directional derivative and subgradient for cone-convex set-valued mappings. As applications, we present necessary and sufficient optimality conditions for set optimization problems and show that the local weak l-minimal solutions of set optimization problems are the global weak l-minimal solutions of set optimization problems under the assumption that the objective mapping is cone-convex. Reference | Related Articles | Metrics | Comments（0） Select A New Class of Filled Functions with Two Parameters for Solving Unconstrained Global Optimization Problems Qiao Chen, Xin-Min Yang, Qian Yan Journal of the Operations Research Society of China    2024, 12 (4): 921-936.   DOI: 10.1007/s40305-024-00548-x Abstract （364）      PDF       Knowledge map    Save A new class of filled functions for escaping the current local minimizer of unconstrained global optimization is proposed. This kind of filled functions is continuously differentiable. And it has no exponential terms and logarithmic terms, which reduce the possibility of computation overflows. Theoretical properties of the proposed filled functions are studied, including discussing the specific conditions that the proposed functions must meet to qualify as a filled function. Then, a new solution algorithm is developed according to the theoretical analysis. Six benchmark problems are tested, and the performance of the new algorithm is compared with two filled function methods. The numerical results prove that the new algorithm is effective and reliable. 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 （358）      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 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 （355）      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） Select An Affine Scaling Algorithm for Biobjective Linear Programming Marco Antonio Figueiredo Menezes, Nelson Maculan Journal of the Operations Research Society of China    2024, 12 (4): 937-951.   DOI: 10.1007/s40305-023-00486-0 Abstract （348）      PDF       Knowledge map    Save Given a biobjective linear programming problem, we develop an affine scaling algorithm withmin-max direction and demonstrate its convergence for an efficient solution. We implement the algorithm for some minor issues in the literature. 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 （338）      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 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 （335）      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 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 （334）      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 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 （332）      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 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 （328）      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 Cyclic Gradient Methods for Unconstrained Optimization Ya Zhang, Cong Sun Journal of the Operations Research Society of China    2024, 12 (3): 809-828.   DOI: 10.1007/s40305-022-00432-6 Abstract （234）      PDF       Knowledge map    Save Gradient method is popular for solving large-scale problems. In this work, the cyclic gradient methods for quadratic function minimization are extended to general smooth unconstrained optimization problems. Combining with nonmonotonic line search, we prove its global convergence. Furthermore, the proposed algorithms have sublinear convergence rate for general convex functions, and R-linear convergence rate for strongly convex problems. Numerical experiments show that the proposed methods are effective compared to the state of the arts. 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 （227）      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 An Upper Bound for the Transversal Number of Connected k-Uniform Hypergraphs Zi-An Chen, Bin Chen Journal of the Operations Research Society of China    2024, 12 (3): 829-835.   DOI: 10.1007/s40305-022-00445-1 Abstract （215）      PDF       Knowledge map    Save Let H be a hypergraph with vertex set V(H) and hyperedge set E(H). We call a vertex set R $\subseteq$ V(H) a transversal if it has a nonempty intersection with every hyperedge of H. The transversal number, denoted by τ(H), is the minimum cardinality of transversals. In 2021, Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most $\frac{2 m+1}{3}$, that is, τ(H) $\frac{2 m+1}{3}$, where m is the size of H. Moreover, they gave the necessary and sufficient conditions to reach the upper bound, namely τ(H) = $\frac{2 m+1}{3}$, if and only if H is a hypertree with a perfect matching. In this paper, we investigate the transversal number of connected kuniform hypergraphs for k ≥ 3. We confirm that τ(H) $\frac{(k-1) m+1}{k}$ for any k-uniform hypergraph H with size m. Furthermore, we show that τ(H) = $\frac{(k-1) m+1}{k}$ if and only if H is a hypertree with a perfect matching, which generalizes the results of Diao. Reference | Related Articles | Metrics | Comments（0） Select A Note on B-Subdifferential of Projection Operator on Polyhedral Set Hao-Yang Liu, Jia Wu, Li-Wei Zhang Journal of the Operations Research Society of China    2024, 12 (3): 837-845.   DOI: 10.1007/s40305-022-00433-5 Abstract （200）      PDF       Knowledge map    Save This note characterizes the set of Fréchet-differentiable points of the projection operator on a polyhedral set and the B-subdifferential of this projection operator at any point. Reference | Related Articles | Metrics | Comments（0） Select Trace Lasso Regularization for Adaptive Sparse Canonical Correlation Analysis via Manifold Optimization Approach Kang-Kang Deng, Zheng Peng Journal of the Operations Research Society of China    2024, 12 (3): 573-599.   DOI: 10.1007/s40305-022-00449-x Abstract （198）      PDF       Knowledge map    Save Canonical correlation analysis (CCA) describes the relationship between two sets of variables by finding a linear combination that maximizes the correlation coefficient. However, in high-dimensional settings where the number of variables exceeds sample size, or in the case that the variables are highly correlated, the traditional CCA is no longer appropriate. In this paper, a new matrix regularization is introduced, which is an extension of the trace Lasso in the vector case. Then we propose an adaptive sparse version of CCA (ASCCA) to overcome these disadvantages by utilizing the trace Lasso regularization. The adaptability of ASCCA is that the sparsity regularization of canonical vectors depends on the sample data, which is more realistic in practical applications. The ASCCA model is further reformulated to an optimization problem on the Riemannian manifold. Then we adopt a manifold inexact augmented Lagrangian method to solve the resulting optimization problem. The performance of the ASCCA model is compared with some existing sparse CCA techniques in different simulation settings and real datasets. Reference | Related Articles | Metrics | Comments（0） Select Greedy is Good: Constrained Non-submodular Function Maximization via Weak Submodularity Ma-Jun Shi, Wei Wang Journal of the Operations Research Society of China    2024, 12 (3): 627-648.   DOI: 10.1007/s40305-022-00444-2 Abstract （194）      PDF       Knowledge map    Save The widely used greedy algorithm has been recently shown to achieve near-optimal theoretical guarantees for the problems of constrained monotone non-submodular function maximization, with competitive performances in practice. In this paper, we investigate the problems ofmaximizingmonotone non-submodular set functions under three classes of independent system constraints, including p-matroid intersection constraints, p-extendible system constraints and p-system constraints. We prove that the greedy algorithm yields an approximation ratio of $\frac{\gamma}{p+\gamma}$ for the former two problems, and $\frac{\xi \gamma}{p+\xi \gamma}$ for the last problem, which further has been improved to $\frac{\gamma}{p+\gamma}$, where γ, ξ denote the submodularity ratio and the diminishing returns ratio of set function respectively. In addition, we also show that the greedy guarantees have a further refinement of $\frac{\xi}{p+\alpha \xi}$ for all the problems mentioned above, where α is the generalized curvature of set function. Finally, we show that our greedy algorithm does yield competitive practical performances using a variety of experiments on synthetic data. Reference | Related Articles | Metrics | Comments（0） Select Maximizing the Differences Between a Monotone DR-Submodular Function and a Linear Function on the Integer Lattice Zhen-Ning Zhang, Dong-Lei Du, Ran Ma, Dan Wu Journal of the Operations Research Society of China    2024, 12 (3): 795-807.   DOI: 10.1007/s40305-022-00393-w Abstract （192）      PDF       Knowledge map    Save In this paper, we investigate the maximization of the differences between a nonnegative monotone diminishing return submodular (DR-submodular) function and a nonnegative linear function on the integer lattice. As it is almost unapproximable for maximizing a submodular function without the condition of nonnegative, we provide weak (bifactor) approximation algorithms for this problem in two online settings, respectively. For the unconstrained online model, we combine the ideas of single threshold greedy, binary search and function scaling to give an efficient algorithm with a 1/2 weak approximation ratio. For the online streaming model subject to a cardinality constraint, we provide a one-pass ($3-\sqrt{5}$)/2 weak approximation ratio streaming algorithm. Its memory complexity is (klogk/ε), and the update time for per element is (log2k/ε). Reference | Related Articles | Metrics | Comments（0）