整数规划与线性规划的差别只是变量的整数约束。
问题区别一点点，难度相差千万里。
选择简单通用的编程方案，让求解器去处理吧。
『Python小白的数学建模课 @ Youcans』带你从数模小白成为国赛达人。
1. 从线性规划到整数规划 1.1 为什么会有整数规划？
线性规划问题的最优解可能是分数或小数。整数规划是指变量的取值只能是整数的规划。
这在实际问题中很常见，例如车间人数、设备台数、行驶次数，这些变量显然必须取整数解。
整数规划并不一定是线性规划问题的变量取整限制，对于二次规划、非线性规划问题也有变量取整限制而引出的整数规划。但在数学建模问题中所说的整数规划，通常是指整数线性规划。
根据对变量的不同情况，整数规划又可以分为：
完全整数规划，全部变量都要求是整数；
混合整数规划，部分变量要求是整数；
0-1整数规划，变量的取值只能是 0 或 1；
混合0-1规划，部分变量的取值只能是 0 或 1。
0-1整数规划 是非常重要也非常特殊的整数规划，需要在另外的文章进行讨论。
1.2 四舍五入就能得到整数解吗？
整数规划问题与线性规划问题的区别只是增加了整数约束。这看上去好像只要把线性规划得到的非整数解舍入化整，就可以得到整数解，并不是多么复杂的问题。
但是问题并没有这么简单。化整后的解不仅不一定是最优解，甚至不一定是可行解的——线性规划的最优解，取整后可能就不满足约束条件了。
那么，不要按四舍五入取整，而是向满足约束条件的方向取整，是不是就可以呢？这是很好的想法，通常这样可以获得可行解，但却不一定是最优解了。
因此，整数规划问题比线性规划复杂的多，以至于至今还没有通用的多项式解法，也就是说算法复杂度与问题规模成指数关系（NP问题）。还没有意识到与问题规模指数关系意味着什么吗？就是那个在象棋棋盘上放麦子，每格比前一格加倍的故事。
问题区别一点点，难度却相差千万里。小白与学霸，差距其实并不大。
欢迎关注 『Python小白的数学建模课 @ Youcans』，每周更新数模笔记
Python小白的数学建模课-01.新手必读
Python小白的数学建模课-02.数据导入
Python小白的数学建模课-03.线性规划
Python小白的数学建模课-04.整数规划
Python数模笔记-PuLP库
Python数模笔记-StatsModels统计回归
Python数模笔记-Sklearn
Python数模笔记-NetworkX
Python数模笔记-模拟退火算法
2. 整数规划的求解方法 2.1 分支定界法（Branch and bound）
分支定界法的基本思想是把原问题（整数规划问题）转换为一个个线性规划问题来处理，并在求解这些线性规划问题的过程中不断追踪原问题的上界（最优可行解）和下界（最优线性松弛解）。
分支定界法把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标上界，称为定界。每次分枝后，对于超出已知可行解集目标值的那些子集不再进一步分枝，就可以删减很多子集，这称为剪枝。
数学课代表的说法是：设有最大化的整数规划问题 A，先解与之相应的线性规划问题 B，若 B 的最优解不符合 A 的整数条件，则 B 的最优目标函数必是 A 的最优目标函数 z 的上界，记为 z2，而 A 的任意可行解的目标函数值将是 z 的一个下界 z1。分支定界法就是将 B 的可行域分成子区域（分支）的方法，逐步减小 z2 和增大 z1，最终求到 z*。
分支定界法是一个迭代算法，随着迭代过程不断更新上界和下界，直到上界和下界非常接近时结束。通常设置 Gap < 0.1%，就可把当前的最优可行解近似为问题的全局最优解了。因此，分支定界法的“收敛” 不是分析意义上的而是算法意义上的，优化结果是近似解而不是精确解。
分支定界法不用区分完全整数规划与混合整数规划，算法便于实现，但计算量比较大。
2.2 割平面法（Cutting plane）割平面法的基本思路是先求解普通线性规划问题的最优解，再对非整数解添加约束条件使可行域缩小，如此反复求解添加了约束条件的普通线性规划问题，直到得到整数解。
也就是说，先不考虑整数约束条件，直接求解松弛问题的最优解，如果满足整数条件就结束了，如果不满足整数条件，就在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件称为割平面，对松弛问题的可行域割一刀，割去松弛问题的部分非整数解。经过有限次的反复切割，必定可在缩小的可行域的一个整数极点上达到整数规划问题的最优解 。
割平面法的计算量比较小，但对问题的结构及求解的要求较高，算法比较复杂。
2.3 整数规划的编程方案