整数规划.PPT

2011年9月,第3章 整数线性规划,山东大学 软件学院,2011年9月,山东大学 软件学院,2,整数（线性）规划,整数规划问题与模型 整数规划算法 计算软件,2011年9月,山东大学 软件学院,3,背包问题,实例：一个背包，容量为W。 n 件物品，物品 i 容量（重量）为 wi，价值 vi。 询问：选择一些物品装入背包，使其总容量 W，总价值最大。,2011年9月,山东大学 软件学院,4,问题分析（建模）,变量xi 是否选择物品 i。 整数规划（0-1规划）： max i vixi s.t. i wixi W xi 0, 1,2011年9月,山东大学 软件学院,5,举例：集合覆盖（Set Cover）问题,实例：基础集合U = e1, e2, , en，集合族C = S1, S2, , Sm，每一个集合Si是U的一个子集。 询问：最小数目的子集的集合族C C，使得C中子集的“并”包含（覆盖）U中的所有元素。 整数规划（0-1规划）： 定义判定变量xi，xi = 1表示集合Si被选取，xi = 0表示集合Si未被选取。 min i xi s.t. Si: e Si xi 1, e U xi 0, 1,2011年9月,山东大学 软件学院,6,举例：旅行售货员（TSP）问题,实例：给定 n+1 个城市，任两个城市 vi 和 vj 之间有一个距离cij 0（cij = cji, cii = 0）。一个旅行售货员，从城市 v0 出发，走遍所有的城市，再回到 v0。 询问：售货员应该怎样走，才能使走过的总距离最短？,2011年9月,山东大学 软件学院,7,TSP实例,2011年9月,山东大学 软件学院,8,TSP实例,,2011年9月,山东大学 软件学院,9,建模,变量 xij：是否使用从城市 vi 到城市 vj 的路径。 约束 每个城市只能到达一次、离开一次。 所走过的路径构成一个圈（不能多于一个圈）。,2011年9月,山东大学 软件学院,10,TSP的（混合）整数规划,2011年9月,山东大学 软件学院,11,强制路径构成仅一个圈的另一种方法,2011年9月,山东大学 软件学院,12,整数线性规划的特征、模型,特征变量整数性要求 问题本身的要求 引入的逻辑变量的需要 性质可行域是离散点的集合 整数线性规划的常见模型： 一般整数规划模型变量取值为整数。 0-1整数规划模型变量取值为0或1。 混合整数规划模型部分变量取值为整数，部分变量取值为实数。,2011年9月,山东大学 软件学院,13,线性规划,整数规划与线性规划的关系,线性规划是整数规划的放松。 整数规划的可行解是对应的放松问题的可行解。 放松的线性规划的最优值 整数规划的最优值。,整数规划,2011年9月,山东大学 软件学院,14,解整数规划,对整数规划的几点说明： 对放松问题的最优解进行简单的舍入（如，四舍五入）不能得到整数规划的最优解。这样的整数解对于原整数规划甚至是不可行的。 整数可行解的数目可呈爆炸性增长，简单的枚举法不可取。,2011年9月,山东大学 软件学院,15,算法,已有算法： 割平面算法 分枝定界算法 近似算法,2011年9月,山东大学 软件学院,16,割平面算法Gomory, 1958,由放松问题的可行域开始，不断寻找超平面（约束条件）切割可行域。 切割过程中，所有整数可行解保留。 放松问题不断增加约束条件，最优值增加，从而向原整数规划问题的可行域逼近。,2011年9月,山东大学 软件学院,17,割平面生成方法,2011年9月,山东大学 软件学院,18,割平面生成方法,2011年9月,山东大学 软件学院,19,割平面生成方法,2011年9月,山东大学 软件学院,20,Gomory割平面算法,2011年9月,山东大学 软件学院,21,算例,2011年9月,山东大学 软件学院,22,得到松弛问题(P0),2011年9月,山东大学 软件学院,23,解松弛问题(P0),2011年9月,山东大学 软件学院,24,得到松弛问题(P1),2011年9月,山东大学 软件学院,25,解松弛问题(P1),2011年9月,山东大学 软件学院,26,得到松弛问题(P2),2011年9月,山东大学 软件学院,27,解松弛问题(P2),2011年9月,山东大学 软件学院,28,两次切割,x1,x2,3x1 + 2x2 = 6,3x1 + 2x2 = 0,x2 = 1,x1 x2 = 0,2011年9月,山东大学 软件学院,29,分枝定界法的基本思想,将状态空间 U 一分为二。分枝 状态空间可以取 IP 的可行域，或者比其更大。 进入一个状态空间 U。若判定在 U 内不可能找到比当前已知解更好的解，则摒弃该搜索空间。剪枝 若在状态空间 U 内能够找到更好的解，则用新的解代替当前的已知解。定界 若在状态空间 U 内已经找到了最好的解，则结束对 U 的搜索。 否则对状态空间 U 继续分枝。,2011年9月,山东大学 软件学院,30,整数规划的情形,2011年9月,山东大学 软件学院,31,整数规划的情形,2011年9月,山东大学 软件学院,32,整数规划的情形,2011年9月,山东大学 软件学院,33,搜索树,解LP7，得到整数解x7，x* = x7。,解LP4，得到整数解x4，cTx4 cTx*，x* = x4。,解LP2，得到分数解x2，cTx2 cTx*，剪枝。,2011年9月,山东大学 软件学院,34,例子,2011年9月,山东大学 软件学院,35,第1次分枝,2011年9月,山东大学 软件学院,36,第2次分枝,2011年9月,山东大学 软件学院,37,第3次分枝,2011年9月,山东大学 软件学院,38,求得最优解,2011年9月,山东大学 软件学院,39,搜索树,2011年9月,山东大学 软件学院,40,搜索过程,2011年9月,山东大学 软件学院,41,搜索过程,2011年9月,山东大学 软件学院,42,分枝定界法解整数规划,1 活点集合 A IP0，上界 U +，当前最好的整数解 x* NIL。 2 while A do 3 从 A 中取出一个问题 IPk，并将 IPk 从 A 中删除。 4 解 LPk。 5 if 无解 then 转 2 else 记最优解为 xk*，值为 zk*。 6 if zk* U then 7 if xk* 是整数解 then x* xk*，U zk* else 选择 xk* 的一个非整数分量，生成 IP