检索结果-内蒙古大学图书馆

A Systematic Review on Reinforcement Learning for Industrial combinatorial optimization Problems

APPLIED SCIENCES-BASEL 2025年第3期15卷 1211-1211页

作者： Martins, Miguel S. E. Sousa, Joao M. C. Vieira, Susana Univ Lisbon IDMEC Inst Super Tecn P-1049001 Lisbon Portugal

This paper presents a systematic review on reinforcement learning approaches for combinatorial optimization problems based on real-world industrial applications. While this topic is increasing in popularity, explicit implementation details are not always available in the literature. The main objective of this paper is characterizing the agent-environment interactions, namely, the state space representation, action space mapping and reward design. Also, the main limitations for practical implementation and the needed future developments are identified. The literature selected covers a wide range of industrial combinatorial optimization problems, found in the IEEE Xplore, Scopus and Web of Science databases. A total of 715 unique papers were extracted from the query. Then, out-of-scope applications, reviews, surveys and papers with insufficient implementation details were removed. This resulted in a total of 298 papers that align with the focus of the review with sufficient implementation details. The state space representation shows the most variety, while the reward design is based on combinations of different modules. The presented studies use a large variety of features and strategies. However, one of the main limitations is that even with state-of-the-art complex models the scalability issues of increasing problem complexity cannot be fully solved. No methods were used to assess risk of biases or automatically synthesize the results.

关键词： combinatorial optimization reinforcement learning state space action mapping reward design industry, innovation and infrastructure

来源：评论

学校读者我要写书评

暂无评论

Using machine learning in combinatorial optimization: Extraction of graph features for travelling salesman problem

引用

KNOWLEDGE-BASED SYSTEMS 2025年 314卷

作者： Stodola, Petr Scurek, Radomir Univ Def Inst Intelligence Studies Kounicova 65 Brno Czech Republic

Machine learning has emerged as a paradigmatic approach for addressing complex problems across various scientific disciplines, including combinatorial optimization. This article specifically explores the application of machine learning to the Travelling Salesman Problem (TSP) as a technique for evaluating and classifying graph edges. The methodology involves extracting a set of graph features and statistical measures for each edge in the graph. Subsequently, a machine learning model is constructed using the training data, and this model is employed to classify edges in a TSP instance, determining whether they are part of the optimal solution or not. This article contributes to existing knowledge in these key aspects: (a) enhancement of statistical measures, (b) introduction of a novel graph feature, and (c) preparation of training data to simulate real-world problem scenarios. Rigorous experimentation on benchmark instances from the well-established TSP library demonstrates a noteworthy increase in classification accuracy compared to the original approach without the improvements;various popular machine learning techniques are employed and evaluated. Furthermore, the characteristics and effects of the novel approaches are assessed and discussed, including their application to a basic heuristic algorithm. This research finds practical applications in problem reduction, involving the elimination of decision variables, or as a support for heuristic or metaheuristic algorithms in finding solutions.

关键词： Machine learning combinatorial optimization Travelling salesman problem Graph features extraction Edge classification

来源：评论

学校读者我要写书评

暂无评论

Recycling valid inequalities for robust combinatorial optimization with budgeted uncertainty

引用

MATHEMATICAL PROGRAMMING 2025年第1-2期210卷 97-146页

作者： Buesing, Christina Gersing, Timo Koster, Arie M. C. A. Univ Klinikum RWTH Aachen Klin Unfall & Wiederherstellungsch D-52074 Aachen Germany Rhein Westfal TH Aachen Discrete Optimizat Pontdriesch 10-12 D-52062 Aachen Germany

Robust combinatorial optimization with budgeted uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when solving robust integer problems, in particular due to its weak linear relaxation. To overcome this issue, we propose procedures to derive new classes of valid inequalities for robust combinatorial optimization problems. For this, we recycle valid inequalities of the underlying deterministic problem such that the additional variables from the robust formulation are incorporated. The valid inequalities to be recycled may either be readily available model constraints or actual cutting planes, where we can benefit from decades of research on valid inequalities for classical optimization problems. We first demonstrate the strength of the inequalities theoretically, by proving that recycling yields a facet-defining inequality in many cases, even if the original valid inequality was not facet-defining. Afterwards, we show in an extensive computational study that using recycled inequalities can lead to a significant improvement of the computation time when solving robust optimization problems.

关键词： Robust optimization combinatorial optimization Integer programming Polyhedral combinatorics Computation

来源：评论

学校读者我要写书评

暂无评论

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

引用

QUANTUM INFORMATION PROCESSING 2025年第2期24卷 1-22页

作者： Ponce, Moises Herrman, Rebekah Lotshaw, Phillip C. Powers, Sarah Siopsis, George Humble, Travis Ostrowski, James Univ Tennessee Knoxville Dept Ind & Syst Engn Knoxville TN 37996 USA Oak Ridge Natl Lab Quantum Computat Sci Grp Oak Ridge TN 37830 USA Oak Ridge Natl Lab Comp Sci & Math Div Oak Ridge TN 37830 USA Univ Tennessee Knoxville Dept Phys & Astron Knoxville TN 37996 USA Oak Ridge Natl Lab Quantum Sci Ctr Oak Ridge TN 37830 USA

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum-in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most nkk+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{nk}{k+1}$$\end{document} vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. While this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

关键词： MaxCut QAOA combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Free-energy machine for combinatorial optimization

NATURE COMPUTATIONAL SCIENCE

引用

NATURE COMPUTATIONAL SCIENCE 2025年第4期5卷 322-332页

作者： Shen, Zi-Song Pan, Feng Wang, Yao Men, Yi-Ding Xu, Wen-Biao Yung, Man-Hong Zhang, Pan Chinese Acad Sci Inst Theoret Phys CAS Key Lab Theoret Phys Beijing Peoples R China Univ Chinese Acad Sci Sch Phys Sci Beijing Peoples R China Huawei Technol Co Ltd Lab 2012 Shenzhen Peoples R China UCAS Hangzhou Inst Adv Study Sch Fundamental Phys & Math Sci Hangzhou Peoples R China

Finding optimal solutions to combinatorial optimization problems (COPs) is pivotal in both scientific and industrial domains. Considerable efforts have been invested on developing accelerated methods utilizing sophisticated models and advanced computational hardware. However, the challenge remains to achieve both high efficiency and broad generality in problem-solving. Here we propose a general method, free-energy machine (FEM), based on the ideas of free-energy minimization in statistical physics, combined with automatic differentiation and gradient-based optimization in machine learning. FEM flexibly addresses various COPs within a unified framework and efficiently leverages parallel computational devices such as graphics processing units. We benchmark FEM on diverse COPs including maximum cut, balanced minimum cut and maximum k-satisfiability, scaled to millions of variables, across synthetic and real-world instances. The findings indicate that FEM remarkably outperforms state-of-the-art algorithms tailored for individual COP in both efficiency and efficacy, demonstrating the potential of combining statistical physics and machine learning for broad applications.

关键词： combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Multifactorial evolutionary deep reinforcement learning for multitask node combinatorial optimization in complex networks

引用

INFORMATION SCIENCES 2025年 702卷

作者： Ma, Lijia Xu, Long Fan, Xiaoqing Li, Lingjie Lin, Qiuzhen Li, Jianqiang Gong, Maoguo Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China Shenzhen Technol Univ Coll Big data & Internet Shenzhen 518118 Peoples R China Shenzhen Univ Natl Engn Lab Big Data Syst Comp Technol Shenzhen 518060 Peoples R China Xidian Univ Sch Elect Engn Key Lab Collaborat Intelligence Syst Minist Educ Xian 710071 Peoples R China

The node combinatorial optimization (NCO) tasks in complex networks aim to activate a set of influential nodes that can maximally affect the network performance under certain influence models, including influence maximization, robustness optimization, minimum node coverage, minimum dominant set, and maximum independent set, and they are usually nondeterministic polynomial (NP)-hard. The existing works mainly solve these tasks separately, and none of them can effectively solve all tasks due to their difference in influence models and NP-hard property. To tackle this issue, in this article, we first theoretically demonstrate the similarity among these NCO tasks, and model them as a multitask NCO problem. Then, we transform this multitask NCO problem into the weight optimization of a multi-depth Q network (multi-head DQN), which adopts a multi-head DQN to model the activation of influential nodes and uses the shared head and unshared output DQN layers to capture the similarity and difference among tasks, respectively. Finally, we propose a Multifactorial Evolutionary Deep Reinforcement Learning (MF-EDRL) for solving the multitask NCO problem under the multi-head DQN optimization framework, which enables to promote the implicit knowledge transfer between similar tasks. Extensive experiments on both benchmark and real-world networks show the clear advantages of the proposed MFEDRL over the state-of-the-art in tackling all NCO tasks. Most notably, the results also reflect the effectiveness of information transfer between tasks in accelerating optimization and improving performance.

关键词： Multifactorial learning Evolutionary algorithm Reinforcement learning Complex networks combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A Spin Scale-Aware Self-Adaptive Ising Annealing Processing Architecture for combinatorial optimization Problems

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2025年

作者： Jiang, Dong Wang, Xiangrui Huang, Zhanhong Kang, Longyuan Yang, Simei Yao, Enyi South China Univ Technol Sch Microelect Guangzhou 511442 Peoples R China

The Ising annealing processor has emerged as a promising approach to accelerate the discovery of the optimal solutions for a wide range of combinatorial optimization problems (COPs), by mapping various COPs into a unified Ising model. However, fixed computational strategies and inflexible architectures make previous designs suffer from a low hardware resource utilization rate when the numbers of the total required and real-time flipped spins vary across different COPs and iteration steps. In this paper, a novel spin scale-aware self-adaptive Ising annealing processing architecture (AIAPA) is proposed to address this problem, with an adaptive computational strategy, a custom instruction set, multi-traffic mode routers, and a fully-pipelined computing array. It can dynamically adapt to the varying scenarios during the Ising annealing process to maximize the performance of limited hardware resources. Its prototype, supporting 65k fully-connected spins, is implemented on an FPGA platform, operates at a clock frequency of 188 MHz. The AIAPA achieves up to a 24.22 times faster annealing speed compared to the state-of-the-art FPGA design on the max-cut optimization problem while maintaining a high convergence accuracy.

关键词： Annealing Computational modeling Hardware optimization Computer architecture Real-time systems Instruction sets Semiconductor device modeling Simulated annealing Resource management combinatorial optimization Ising model Ising computer momentum annealing network-on-chip

来源：评论

学校读者我要写书评

暂无评论

Bi-Objective combinatorial optimization Model for Emission Reduction Projects at Container Terminals Considering Investment Amount and Reduction Efficiency

引用

TRANSPORTATION RESEARCH RECORD 2025年第1期2679卷 1447-1465页

作者： Zhao, Ruijia Song, Yunting Zhao, Zhenyu Fu, Qiang Zhao, Ruihao Dalian Maritime Univ Integrated Transport Inst Dalian Peoples R China Dongbei Univ Finance & Econ Sch Publ Adm Dalian Peoples R China Liao Ning Maritime Safety Adm Dalian Peoples R China Shanghai Maritime Univ Coll Transport & Commun Shanghai Peoples R China

Ports play a significant role in socio-economic development. However, the substantial carbon emissions generated during their operation processes pose serious health and environmental risks. Port operations involve a wide array of expensive equipment. With the current technological methods, it is possible to transform higher carbon-emitting equipment into lower carbon-emitting equipment through the implementation of emission reduction projects, thereby effectively reducing the carbon emissions of ports. This paper explores the combinatorial optimization methods in the implementation process of various emission reduction projects at container terminals from the perspective of port managers. Firstly, this paper refines the calculation method of estimating carbon emission reduction efficiency by implementing various emission reduction projects throughout the entire process from ship arrival to the completion of handling operations. Secondly, considering practical factors such as the required investment, emission reduction efficiency, and the impacts on port productivity associated with implementing varied emission reduction projects, a bi-objective combinatorial optimization model for emission reduction projects is formulated, with the objectives of minimizing both carbon emissions and the investment amount. An augmented epsilon-constraint method is introduced to obtain the Pareto solutions, which representing a series of implementation plans for emission reduction projects under different investment levels. Finally, the concept of the "emission reduction rate" is proposed to identify the optimal scheme from the Pareto solutions. The impacts of government carbon emission requirements, status of implemented emission reduction projects, container throughput, and differences in vehicle types on optimization results are explored, leading to several managerial insights. The optimization method can provide a theoretical basis for port managers to devise investment plans for

关键词： container terminal emission reduction investment combinatorial optimization reduction efficiency

来源：评论

学校读者我要写书评

暂无评论

Feature augmented PPP-RTK/INS/Vision integration based on combinatorial optimization for urban vehicle navigation

引用

MEASUREMENT SCIENCE AND TECHNOLOGY 2025年第5期36卷 055101-055101页

作者： Gu, Shengfeng Zhou, Shujie Song, Weiwei Li, Ruizhuo Wuhan Univ GNSS Res Ctr Wuhan 430079 Peoples R China Wuhan Univ Sch Geodesy & Geomat Wuhan 430072 Peoples R China

Multi-sensor fusion and precise point positioning real-time kinematic (PPP-RTK) techniques are gaining popularity in vehicle navigation studies. The integration of the Global Navigation Satellite System (GNSS), inertial navigation system (INS), and vision can significantly improve the accuracy and continuity of positioning. The methods used to integrate different measurements are usually divided into an extended Kalman filter and factor graph optimization (FGO). We propose an integration method of PPP-RTK/INS/Vision that utilizes both the square-root information filter (SRIF) and FGO, combining the merits of the two algorithms. The proposed PPP-RTK/INS/Vision integration consists of two parts: the first is reweighted PPP-RTK/INS tightly coupled integration based on SRIF, and the second is GNSS/INS/Vision integration based on a two-step FGO method with feature selection in the vision component. The first positioning result is integrated with the FGO-based visual INS with uniform depth distribution to generate the final navigation information. The real-world experiment, carried out in an urban area, includes many GNSS-challenged environments, such as high buildings, tunnels, and viaducts. The results demonstrate that the proposed method achieves a root mean square of 0.57, 0.65, and 0.86 m in the north, east, and down components of the entire trajectory, respectively. Compared to the PPP-RTK/INS/Vision tightly coupled integration with a multi-state constrained Kalman filter, it shows an 11.0% improvement in vertical accuracy and comparable horizontal accuracy. Moreover, in the GNSS-challenged environment, the performance of the proposed method is more outstanding in the vertical component, with an improvement of 83.0% in the vertical direction and similar horizontal accuracy. Our study provides a novel approach to integrating both measurements and optimal estimation methods.

关键词： precise point positioning real-time kinematic PPP-RTK/INS/Vision integration combinatorial optimization urban vehicle navigation

来源：评论

学校读者我要写书评

暂无评论

A combinatorial optimization Method for Large Scale Problems Based on an Inverse Self-Convolution Algorithm

IEEJ Transactions on Electronics, Information and Systems

引用

IEEJ Transactions on Electronics, Information and Systems 2025年第2期145卷 145-155页

作者： Shigehiro, Yuji Yamamura, Mayuko Faculty of Engineering Osaka Institute of Technology 5-16-1 Ohmiya Asahi-ku Osaka535-8585 Japan NTT Data Sekisui Systems Corporation 1-11-8 Shibuya Shibuya-ku Tokyo150-0002 Japan

In this paper, we consider an effective search method for large scale combinatorial optimization problems, only by means of neighborhood operations, not by means of such operation as crossover in genetic algorithm. The fundamental ideas on which our method is based are the following: 1) Many different neighborhood operations, which consist of the iterations of unit neighborhood operations, are applied to solutions. 2) The probability distribution of the objective function values of the neighborhood solutions is estimated, from the data obtained in the search process. 3) The neighborhood operation, which maximizes the expected value of the amount of the improvement of the current solution, is selected to be applied. From these ideas, a new method for searching for solutions is constructed, on the basis of the self-convolution and the inverse self-convolution. We have applied the local search method, the previously proposed method, and the newly proposed method to traveling salesman problems and maximum satisfiability problems. The effectiveness of the newly proposed method is shown by the computational experiments. © 2025 The Institute of Electrical Engineers of Japan.

关键词： combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：