整数规划的求解方法——分枝定界法

1、概述
设有最大化的整数规划问题 A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z ；而A的任意可行解的目标函数值将是z*的一个下界z 。分枝定界法就是将B的可行域分成子区域的方法。逐步减小z 和增大z ，最终求到z*。
2、求解步骤
将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。

• 对问题B进行求解：若B没有可行解，即A也没有可行解，则停止；若B有最优解，并符合A的整数条件，B的最优解即为A的最优解，停止计算；若B有最优解，但不适合A的整数条件，记它的目标函数值为z0；
• 分枝。此时在B的最优解中任选一个不条例整数条件的变量，从而构造两个约束条件；将这两个问题分别加入到问题B，不考虑整数条件，求解这两个后继问题；
• 定界。以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。
• 比较与前枝。各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。若大于z ，且不符合整数条件，则重复第一步骤。

3、Matlab实现代码

function [x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options)
%整数线性规划分支定界法，可求解纯整数规划和混合整数规划。
%y=minf’*x s.t. G*x<=h Geq*x=heq x为全整数或混合整数列向量
%用法
%[x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options)
%参数说明
%lb:解的下界列向量（Default:-int）
%ub:解的上界列向量（Default:int）
%x:迭代初值列向量
%id：整数变量指标列向量，1-整数，0-实数（Default:1）
global upper opt c x0 A b Aeq beq ID