| 一种改进的逻辑Benders分解方法 |
| Advanced strategies for logic-based Benders decomposition |
| 摘要点击 131 全文点击 0 投稿时间：2023-04-10 修订日期：2024-06-05 |
| 查看/发表评论 下载PDF阅读器 |
| 中文关键词 逻辑Benders分解；增强割；单机调度问题；组合优化 |
| 英文关键词 logic-based Benders decomposition；cut strengthening；single machine scheduling；combinatorial optimization |
| 基金项目 国家自然科学基金项目（面上项目）；陕西省社会科学基金资助项目；西北工业大学特色文科发展计划——青年创新能力培养资助项目；西北工业大学博士论文创新基金 |
| 作者 | 单位 | 邮编 | | 刘海潮 | 西北工业大学 | 710129 | | 王阳 | 西北工业大学 | 710129 | | 王洪普 | 西北工业大学 | |
|
| 中文摘要 |
| 大规模组合优化是解决复杂决策问题的关键, 对优化资源配置、提升服务效率和质量起到了至关重要的作用. 逻辑Benders分解(LBBD)算法是求解大规模组合优化问题的有效方法, 其求解效率十分依赖反馈信息的质量. 本文提出了一种改进LBBD算法, 通过在子问题中重优化主问题的部分变量, 更易求得高质量可行解, 并获得更多解信息生成局部最优割来引导后续求解. 此外, 还提出了多重最优解识别和维护算法, 以保证借助通用优化求解器实现改进LBBD算法时所得解的最优性. 最后, 在考虑工序设置和多时间窗的单机调度问题上进行大量实验测试, 对比了使用改进LBBD算法、传统LBBD算法和混合整数规划求解效率, 验证了改进LBBD算法的有效性与合理性. |
| 英文摘要 |
| Large-scale combinatorial optimization is the key to solving complex decision-making problems, playing a vital role in optimizing resource allocation and enhancing the efficiency and quality of services. Logic-Based Benders Decomposition (LBBD) is an effective method to solve large-scale combinatorial optimization problems. Its computational performance depends on the quality of feedback information. This paper develops an improved LBBD method that adds partial variables of the master problems into the subproblem to obtain high-quality solutions more easily. A novel local optimality cut is proposed for feedback of subproblem information. An algorithm is proposed to ensure the optimality of the solutions obtained by improved LBBD algorithm with general-purpose solvers. Using a single machine scheduling problem with sequence-dependent setup times and multiple time windows as a case study, four LBBD variants are proposed and compared with the integrated mixed integer programming model. Extensive experimental results demonstrate the effectiveness of the proposed LBBD method. |
| 关闭 |
