Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these pro...Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these problems,almost all state-of-the-art local search algorithms adopt a common general initialization method.This paper develops a general group driven initialization method for clique relaxation problems.The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information.We apply the proposed initialization method to two clique relaxation problems.Experimental results demonstrate that the proposed initialization method clearly improves the performance of stateof-the-art algorithms for the clique relaxation problems.展开更多
Multi-commodity flow problems（MCFs） can be found in many areas, such as transportation, communication, and logistics. Therefore, such problems have been studied by a multitude of researchers, and a variety of method...Multi-commodity flow problems（MCFs） can be found in many areas, such as transportation, communication, and logistics. Therefore, such problems have been studied by a multitude of researchers, and a variety of methods have been proposed for solving it. However, most researchers only discuss the properties of different models and algorithms without taking into account the impacts of actual implementation. In fact, the true performance of a method may differ greatly across various implementations. In this paper, several popular optimization solvers for implementations of column generation and Lagrangian relaxation are discussed. In order to test scalability and optimality, three groups of networks with different structures are used as case studies. Results show that column generation outperforms Lagrangian relaxation in most instances, but the latter is better suited to networks with a large number of commodities.展开更多
This article presents an image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem. The algorithm works by solving its equivalent problem, and by using convex hull and concave ...This article presents an image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem. The algorithm works by solving its equivalent problem, and by using convex hull and concave hull approximation of bilinear function, we can construct the affine relaxation problem of the equivalent problem, which can be used to compute the lower bounds during the branch-and-bound search. By subsequently refining the initial image space rectangle and solving a series of affine relaxation problems, the proposed algorithm is convergent to the global optima of the primal problem. For improving the convergence speed, an image space region reducing method is adopted for compressing the investigated image space rectangle. In addition, the global convergence of the algorithm is proved, and its computational complexity is analyzed. Finally, comparing with some existing methods, numerical results indicate that the algorithm has better computational performance.展开更多
This work develops near-optimal controls for systems given by differential equations with wideband noise and random switching.The random switching is modeled by a continuous-time,time-inhomogeneous Markov chain.Under ...This work develops near-optimal controls for systems given by differential equations with wideband noise and random switching.The random switching is modeled by a continuous-time,time-inhomogeneous Markov chain.Under broad conditions,it is shown that there is an associated limit problem,which is a switching jump diffusion.Using near-optimal controls of the limit system,we then build controls for the original systems.It is shown that such constructed controls are nearly optimal.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61976050)CCF Huawei Hu Yanglin Foundation Theoretical Computer Science Project(CCFHuaweiLK2023001)+1 种基金the Fundamental Research Funds for the Central Universities(2412022ZD015,2412023YQ003)Jilin Science and Technology Department(YDZJ202201ZYTS412,20240602005RC).
文摘Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these problems,almost all state-of-the-art local search algorithms adopt a common general initialization method.This paper develops a general group driven initialization method for clique relaxation problems.The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information.We apply the proposed initialization method to two clique relaxation problems.Experimental results demonstrate that the proposed initialization method clearly improves the performance of stateof-the-art algorithms for the clique relaxation problems.
基金supported by research funds from the National Natural Science Foundation of China (Nos. 61521091, 61650110516, 61601013)
文摘Multi-commodity flow problems（MCFs） can be found in many areas, such as transportation, communication, and logistics. Therefore, such problems have been studied by a multitude of researchers, and a variety of methods have been proposed for solving it. However, most researchers only discuss the properties of different models and algorithms without taking into account the impacts of actual implementation. In fact, the true performance of a method may differ greatly across various implementations. In this paper, several popular optimization solvers for implementations of column generation and Lagrangian relaxation are discussed. In order to test scalability and optimality, three groups of networks with different structures are used as case studies. Results show that column generation outperforms Lagrangian relaxation in most instances, but the latter is better suited to networks with a large number of commodities.
基金supported by the National Natural Science Foundation of China(Grant Nos.11871196,12071133,12071112)by the Key Scientific and Technological Research Projects of Henan Province(Grant Nos.232102211085,202102210147)+1 种基金by the China Postdoctoral Science Foundation(Grant No.2017M622340)by the Science and Technology Climbing Program of Henan Institute of Science and Technology(Grant No.2018JY01).
文摘This article presents an image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem. The algorithm works by solving its equivalent problem, and by using convex hull and concave hull approximation of bilinear function, we can construct the affine relaxation problem of the equivalent problem, which can be used to compute the lower bounds during the branch-and-bound search. By subsequently refining the initial image space rectangle and solving a series of affine relaxation problems, the proposed algorithm is convergent to the global optima of the primal problem. For improving the convergence speed, an image space region reducing method is adopted for compressing the investigated image space rectangle. In addition, the global convergence of the algorithm is proved, and its computational complexity is analyzed. Finally, comparing with some existing methods, numerical results indicate that the algorithm has better computational performance.
基金supported in part by the National Science Foundation under DMS-1207667supported in part by NSFC and RFDP
文摘This work develops near-optimal controls for systems given by differential equations with wideband noise and random switching.The random switching is modeled by a continuous-time,time-inhomogeneous Markov chain.Under broad conditions,it is shown that there is an associated limit problem,which is a switching jump diffusion.Using near-optimal controls of the limit system,we then build controls for the original systems.It is shown that such constructed controls are nearly optimal.
