摘要
整数规划问题在经济、工业生产、管理调度等领域有着广泛应用。然而解决此类问题常用的传统方法大多都是依赖人工设计的启发式算法,该算法已经逐渐不能满足大规模问题下实时性求解的要求。论文将深度强化学习应用于对整数规划的分布式可行域切割的序贯决策问题中,设计并构建了状态与动作空间以及奖励函数,并结合注意力机制与LSTM网络来训练了强化学习代理,以解决整数规划问题中可行域分割的切割平面选择的问题。实验结果表明,该策略方法能有效进行Gomory切割平面的选择,且拥有相对稳定的切割质量。
Integer programming problems have wide applications in various domains,such as economy,industrial production,and management scheduling.However,conventional methods for solving these problems mostly rely on heuristic algorithms designed manually,which gradually fail to meet the real-time solving requirements for large-scale problems.This study applies deep reinforcement learning to the sequential decision problem of distributed feasible region cuts in integer programming.It designed and constructed the state and action spaces as well as the reward function.Additionally,it incorporated attention mechanisms and LSTM networks to train the reinforcement learning agent,addressing the selection of cutting planes in feasible region partitioning for integer programming problems.Experimental results demonstrate that this strategy effectively selects Gomory cutting planes while maintaining relatively stable cutting quality.
作者
吴闻笛
吴征天
WU Wendi;WU Zhengtian(School of Electronic&Information Engineering,SUST,Suzhou 215009,China)
出处
《苏州科技大学学报(自然科学版)》
2025年第2期76-84,共9页
Journal of Suzhou University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金项目(61803279,61672371)
江苏省“青蓝工程”项目。
关键词
整数规划
强化学习
算法优化
NP-HARD问题
integer programming
reinforcement learning
algorithm optimization
NP-hard problems
