运筹学与最优化(优化理论与运筹学的关系是什么)

运筹学与最优化(优化理论与运筹学的关系是什么)

adminqwq 2026-01-28 社会资讯 15 次浏览 0个评论

目前接触了mathematical programming、optimization和operation research,个人感觉OR偏向建模,optimization偏向求解,MP两者都有,不知道理解的对不对

运筹学与最优化(优化理论与运筹学的关系是什么)
(图片来源网络,侵删)

------------------------------------

谢邀,我基本同意你的题述。优化理论和运筹学肯定是有很大重叠的。但是起源有所不同,所以关注点有重叠但是也有差异。

从运筹学的角度来说,是有清晰的发展脉络的,因为我做整数规划比较多,那么在整数规划中,精确求解的“三板斧”:

原始线性规划(一切的起源):线性规划/整个运筹学之父,这个应该无争议,George Dantzig及他的单纯形法,可以说开创了这个学问,从历史角度来看,运筹学有着深度绑定(军方)实用场景的基因,所以你说的OR偏向建模(把实际问题“翻译”成数学模型)是有其道理的,难度在于,面对复杂的世界,我们所掌握并解出的模型范式太少了,比如线性规划及单纯形法一开始被提出的时候,就被批评“世界不是线性的,线性规划有什么用”,所以说建模是一门艺术,怎样做实际的assumption,并且让模型快速能被解出,并且求出的解有现实意义,是运筹学中很重要也是很难学的本领。列生成(Column generation / Branch-and-Price) :从线性规划跳入整数规划,建模及其解法的复杂度又上升了一个台阶,面临到组合指数爆炸的问题。这个时候我感觉,运筹学就开始偏离以连续优化为核心的 optimization 理论体系了,因为整数规划 / 离散优化有一套在大运筹学内部发展出来的、非常工程化的建模与解法范式。起源是Branch-and-Bound (分支定界),基本运行模式是“求线性问题-得出分数解-手动分支(把一个变量分支成可能的整数解)- 重新求解分支出的子问题 - 定界剪枝 - 循环直到得出最优整数解”。而在这里,很重要的一个发展是列生成思想,粗暴解释,又来到了运筹学的重点,(Dantzig–Wolfe decomposition - Dantzig这个名字又出现了),把模型重构,生成大量的列,每个列都是一组promising的整数解组合,然后在主问题中,用传统线性规划的方式,选择这些列,子问题则生成列。从这个角度来说,这个方法更像以建模为起点,催化出的一种解法。行生成(Row Generation / Benders Decomposition):更年轻一点的方法,就是行生成,每行代表一个现实约束,因为现实约束太多,所以粗暴解释,人为限制,只考虑一部分约束,然后求解,最后逐步加约束,直到达到最优且可行的解。所以主问题求解,子问题验证可行性,如果不可行,则加约束。所以从这个角度来说,也是建模驱动的解法开发。这个方面,最新的进展是John Hooker开发了Logic based benders decomposition。LBBD的创新性,是在行生成的框架下,极大延展了子问题的自由度,所谓的逻辑割,只要在求解过程中能够识别当前主问题解在子问题层面上的不可行性,并据此生成一个逻辑上必要的排除条件,即可作为一条 Benders 行反馈给主问题,但是其原理还是在子问题中不断生成行,检查当前解的可行性。加更:这三板斧的连接,往往通过对偶问题,粗暴解释,把线性规划中的列变成行,行变成列,形成关联性极强的对偶问题,两个问题最优值相同,则强对偶,最优值有差异,则弱对偶(可以以此定上下界),这也可以理解为通过建模的方式催化新解法。

列生成推荐书目,新鲜热乎的:Desrosiers, J., Lübbecke, M., Desaulniers, G., & Gauthier, J. B. (2024).Branch-and-price. GERAD, HÉC Montréal.

行生成推荐书目,新鲜热乎的:Hooker, J. (2023). Logic-based benders decomposition: theory and applications.

转载请注明来自海坡下载,本文标题:《运筹学与最优化(优化理论与运筹学的关系是什么)》

每一天,每一秒,你所做的决定都会改变你的人生!

发表评论

快捷回复:

评论列表 (暂无评论,15人围观)参与讨论

还没有评论,来说两句吧...