整数编程学习指南
整数规划入门框架
1.引言
几乎每个接触运筹学的人都是从线性规划开始。以清华大学出版的,或是胡运权老师出版的《运筹学》为教材,线性规划;对偶规划和灵敏度分析;运输问题;目标规划;整数规划,指派问题;分支定界割平面;图论里的生成树;最短路,最大流,最大割;以及动态规划;网络评审技术等等。
可以说几乎囊括了运筹学的整个分支,其实每个章节拿出来都是可以大书特书的。
整数规划是其中的一个小章节,同时也是一类生活中非常常见的问题。生活中的二元决策太多了,yes or no是与非的二元选择;或是物品属性无法分割的整数决策。
2.整数规划的数学模型
建模三要素是:目标函数;优化变量;以及约束条件。
根据维度不同,可以分为单目标多目标;多元决策或整数规划;以及有约束无约束的数学模型。
当约束条件和目标函数都是线性函数时,为线性规划LP;
当部分或全部优化变量只能取整数解时,为整数规划IP;
特别的:
只能取0/1时,为0-1规划BIP,
部分取整数,为混合整数规划MIP。
线性规划已经有成功的解法了:单纯形法,simplex method;另外也有成熟成型的理论体系。线性规划的特点是:可行域是个凸包,也就是说,最优解必定是在顶点处得到。
整数规划的解是一个个的点,简单的(即变量少的时候),可以通过穷举法求解,然而当变量增多时,求解起来需要很久很久,因此穷举法不现实。
同时很多整数规划都是NP难问题。也就是说,可以通过简单的转化,将其转变成为一个无法求解的难问题。那么我们的一个思路是:能否通过一些转化方法,将整数规划转化为线性规划问题,用成熟成功的线性规划求解算法得以求解呢?
这里的一个关键在于:线性规划求解出的解不一定是整数解,怎么转化成整数解呢?
3.整体框架
因此整数规划的理论,几乎就是建立在线性规划的基础之上的。通过一些方法将整数规划和线性规划联系起来,从而通过线性规划的理论予以求解。
3.1 线性规划和整数规划等价的特例
对于全单模矩阵,线性规划和整数规划是可以化等号的。也就是说,线性规划求解得到的解必定是整数解。
所以拿到一个问题,我们首先检查系数矩阵,是否是全单模矩阵。如果是,拿线性规划的理论就可以求解了。这是个简单的问题。
这里涉及到怎么判别简单还是难的问题。也就是复杂性理论。
3.2 切除多余的可行域,从而转化为LP
线性规划的顶点并非是整数解,然而我们可以通过一些方法,削去一部分变成整数规划所有可行解的凸包围,也就是凸包convex hull。1
这里有两种一般方法:
(1)分支定界法
也就是不断的分支,和比较,切掉一定不是最优解的区域。
(2)割平面法
也就是也就是通过加不等式,来取出凸包外的区域。
整数规划的精确算法框架中最核心的便是B&B,以及增加分支定界效率的各种技巧,例如割平面方法(Cutting Planes Method)等。假设是求解目标函数最小化的问题,它的核心思想便是把这个NP难的问题分解成求解一个个的线性规划(LP)问题(每个LP问题是多项式时间可解),并且在求解的过程中实时追踪原问题的上界(最优可行解)和下界(最优线性松弛解)。
延展阅读链接:混合整数规划/离散优化的精确求解方法及优化求解器
还有一种:就是拉格朗日松弛法,也可以对模型求解起到一定的作用。
3.3 一些特别的IP
(1)如果约束比较少,而变量比较多,也就是比较长(可以把变量和约束想象成一个长方形),可以用列生成求解column generation。
假如** 约束比较多**,可以用** 行生成**求解row generation。
一般整数规划比较复杂,指的是,约束多或是变量多。这里要用到稀疏矩阵的性质,判别,重写reformulation等。(这块也是一个知识点)
(2)如果是多阶段决策,那就是动态规划问题,动态规划也有一部分标准的解法。
所以,整数规划主要分为以下几个部分:
1.怎么判别简单或容易,也就是复杂性理论。
2.一般解法介绍,如分支定界,割平面,拉格朗日松弛。
3.特殊解法介绍,列生成,动态规划。
4.将一般的混合整数规划转化成整数规划的方法,如:benders分解。
总结:
求解整数规划的核心是branch and bound,在此基础上结合cutting plane(row generation)就是branch and cut,结合column generation就是branch and price。
branch and cut = branch and bound + cutting plane(cutting plane本质就是row generation,常见有UserCut用来cut掉实数解,还有LazyCut用来cut掉整数解)
branch and price = branch and bound + row generation。
延展阅读: 整数规划经典方法漫谈
参考书:
-
wolsey, Integer programminng[M].
孙小玲, 李端, 整数规划[M]. ↩︎
推荐阅读
-
掌握 JavaScript 面向对象编程的核心代码:深入分析 JavaScript 面向对象机制的对象基础、原型模式和继承策略全面指导高效创建高质量、可维护的代码 - V. 继承机制
-
读懂知乎,说它牛逼 !-从内容消费者到内容创造者,这种转变的开始只有一次,那就是被别人认可。 浏览量高的很大一部分原因是知乎上有很多程序员,关于互联网、计算机、编程等话题都会有大量曝光,这些相关内容时不时就会出现在热搜榜上。 今天,顺便给大家推荐九个程序员相关的高赞答案,这些答案我会不定期拿出来重温,喜欢的你也不妨收藏一下。(看完第九个答案你再来喜欢~)。 一 话题:程序员未来会是一个很内卷的职业吗?
-
学习编程的一些个人经历 傻瓜也能理解的弗洛伊德算法
-
告别动态编程,刷完40道算法题,我总结了一套动态调控的方法
-
告别动态编程,连刷40题,我总结了这些套路,不懂你就打我(万字长文)
-
与我一起学习 glsl 编程 16 - Sun Ring
-
稳定人工智能开年首个大模型:专用代码、支持 18 种编程语言、100K 上下文以及可离线运行的苹果笔记本电脑
-
Mac 为什么适合编程?
-
2022 年最适合编程的 10 款笔记本电脑分享推荐!
-
编程原则和方法