爱华网如果区别与线性规划的话，整数规划就是求变量取值为整数时候的最优解，首先声明的是整数最优解不能通过简单的线性最优解取整而获得。
整数规划的解决方法有几个比较主流的，分枝定界是在线性规划的基础上理解起来较为简单的算法，蒙特卡洛算法是听起来比较cool的，所以打算准备整理一下这两个。
惯例，先念诗：亡我祁连山，使我牛羊不蕃息;失我胭脂山，令我妇女无颜色。
分枝定界有些搜索的基因，是在可行解空间内的适当搜索和缩小范围。分枝，把全部的可行解空间反复地分割为越来越小的子集。定界，对每个子集内的解集计算一个目标下届。越界的可行解子集丢弃不再分枝（剪枝）。
每个整数规划问题A都会有一个线性规划问题B与其遥相呼应，暗送秋波（注意节操！摔！）。想，如果线性规划的最优解不是整数解，那这个最优解显然就是整数解的上界，而可行解内的任意整数解都可以使最优整数解的下界。如果你能把这个空间逐步缩小，最后就能找到最优整数解。
例：
求整数规划问题A： max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a,b >=0
解：
按照线性规划求一下式子的最优解:
c=[-40;-90] A=[9,7;7,20] b=[56;70]
linprog(c,A,b,[],[],zeros(2,1))
Optimization terminated.
ans=
4.8092
1.8168
如上最优解为 a =4.8092 b= 1.8168 最大 z=355.8779显然，最优解不是整数解，所以整数最优解的z*将以z=355.8779为上界；由题可知a=0b=0显然是问题的一个整数可行解。所以我们得到一个相对较大的最优解范围0<= z*<=356。
下面我们就做分枝工作： 因为最优解中两个变量都不是整数，我们任选一个进行分枝，如选 a=4.8092 把a分成两个子集 第一个：a<=[4.8092]=4 第二个：a>=[4.8092]+1=5同时便把问题A划分成了两个问题A1和A2，且因为4和5之间没有整数两个问题的整数最优解就是原题目的整数最优解：
A1：max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a<=4,b >=0
A2：max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a>=5,b >=0
A1:linprog([-40;-90],[9,7;7,20;1,0],[56;70;4],[],[],zeros(2,1))
A2:linprog([-40;-90],[9,7;7,20;-1,0],[56;70;-5],[],[],zeros(2,1))
A1的最优解为 a= 4.0000 b = 2.1000z1 =349
A2的最优解为 a =5.0000 b = 1.5700z2 = 341.4
选取两个最优解大的更新上界，如果两个最优解存在整数解，更新下界，这里两个都不是整数解所以不更新下界。这一步定界完后，目标函数范围是：0<=z*<=349。
由于没有得到最优整数解，还需要继续分枝。
那先将A1分为A11和A12两个问题(由于都是一样的工作，我只列出linprog函数)。
A11：linprog([-40;-90],[9,7;7,20;1,0;0,1],[56;70;4;2],[],[],zeros(2,1))
最优解： a = 4.0000 b = 2.0000;z11 = 340
A12:linprog([-40;-90],[9,7;7,20;1,0;0,-1],[56;70;4;-3],[],[],zeros(2,1))
最优解： a = 1.4286 b = 3.0000;z12 = 327.2
我们得到一个整数可行解，虽然不知道它是不是最优的，但能更新目标函数的下界340<=z*<=356
这个界可以帮我们进行剪枝，如A12中不可能在出现某个整数可行解使z>340>327.2，变量在那一部分的取值可舍弃，即剪枝。
而，不要忘了我们还有A2没有分枝，需要分成A21和A22，
A21：linprog([-40;-90],[9,7;7,20;-1,0;0,1],[56;70;-5;1],[],[],zeros(2,1))
最优解： a = 5.4 b = 1 ; z21 = 308
A22:linprog([-40;-90],[9,7;7,20;-1,0;0,-1;],[56;70;-5;2],[],[],zeros(2,1))
无最优解
由于在分枝A1的时候确定了新的界，由线性最优解可知，A21和A22空间内不可能出现使目标函数z值大于340（下界）的的整数解，两部分都能剪枝。
至此，只剩下A11空间，且已知最优解 a = 4.0000 b = 2.0000; z11 =340。
那在原空间内a = 4 ,b = 2 ,z* = 340 ，就是我们所找的最优整数解。
