动态规划(DP)是解决决策问题的跨学科框架。在计算机科学与运筹学(OR)领域，DP算法被开发用于组合优化——即通过有限决策集优化目标函数的问题类别。传统DP算法通常针对特定组合优化问题专门实现。相较之下，基于模型的范式使用通用求解器处理特定数学模型表述的问题，旨在解耦问题建模与求解过程（声明式问题求解的"终极目标"）。实践中，混合整数规划(MIP)与约束规划(CP)等基于模型的范式被广泛用于求解各类组合优化问题。本文提出领域无关动态规划(DIDP)——基于DP的新型组合优化建模范式。在DIDP中，用户通过声明式建模语言构建DP模型，并使用通用DP求解器求解。本论文系统开发了DIDP建模语言与通用求解器。
语言受人工智能(AI)规划启发，基于状态转移系统构建，但专为组合优化设计：类似MIP与CP，用户可声明式地在模型中包含冗余信息（这些信息虽隐含于模型其他部分，但显式表达有助于求解器优化）。通过将11类组合优化问题表述为DP模型，展示了该语言的建模能力。采用AI领域广泛应用的启发式搜索算法开发DIDP求解器：首先开发即时精确求解器（随时间提升解质量直至获得最优解）；其次基于大邻域搜索(LNS)开发DIDP求解器（借鉴MIP/CP快速获取高质量解的方法）；最终利用并行启发式搜索算法开发多线程DIDP求解器。通过开发的建模语言与求解器，我们证实DIDP是极具前景的方法——在多个组合优化问题类别中实证优于MIP与CP。
论文结构如下：第2章综述DIDP相关文献；第3章提出DIDP建模语言；后续三章（4-6章）开发特性各异的DIDP求解器；第7章总结贡献并展望未来。第2章首先介绍组合优化DP算法，阐述现有基于模型的组合优化范式及其与DP的关联，评述现有基于模型的DP方法并论证其作为实用组合优化范式的不足。第3章提出动态规划描述语言(DyPDL)作为DIDP建模形式化框架，进而推出实用建模语言YAML-DyPDL。通过DP模型实例解析YAML-DyPDL（正式语法见附录A.1），并通过11类组合优化问题的DP建模展示DyPDL与YAML-DyPDL的建模能力。
第4章采用启发式搜索算法开发通用DIDP求解器。这些即时精确求解器持续提升解质量直至获得最优解，并提供中间解的最优性差距。实证比较表明：在11类组合优化问题中，DIDP求解器在7类问题上优于商用MIP/CP求解器。第3-4章内容基于投稿《Artificial Intelligence》的论文[266]（该文扩展了国际自动规划调度会议论文[267,270]）。第5章将DIDP与大邻域搜索(LNS)结合（该算法框架在MIP/CP中用于快速获取优质解），提出融合LNS与状态空间搜索的大邻域束搜索(LNBS)算法。实证显示：采用LNBS的DIDP求解器在11类问题中的6类上优于第4章最优DIDP求解器。本章工作基于国际约束编程会议论文[268]。第6章利用并行启发式搜索算法开发多线程DIDP求解器。实验证明：相比单线程求解器，多线程版本在32线程下实现显著加速，并在多类问题上优于商用多线程MIP/CP求解器。本章工作基于AAAI人工智能会议论文[269]。第7章总结贡献并展望DIDP未来研究方向。
原文
相关内容
微信扫码咨询专知VIP会员