第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法
整数（线性）规划 整数规划问题与模型 整数规划算法 2018/12/8 山东大学 软件学院
背包问题 1 实例：一个背包，容量为W。 n 件物品，物品 i 容量（重量）为 wi，价值 vi。 2 3 4 5 6 7 8 9 10 体积 200 350 500 430 320 120 700 420 250 100 价格 15 45 70 50 75 90 20 30 2018/12/8 山东大学 软件学院
问题分析（建模） 变量xi – 是否选择物品 i。 整数规划（0-1规划）： max i vixi s.t. i wixi W 2018/12/8 山东大学 软件学院
集合覆盖（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} 2018/12/8 山东大学 软件学院
旅行售货员（TSP）问题 实例：给定 n+1 个城市，任两个城市 vi 和 vj 之间有一个距离cij 0（cij = cji, cii = 0）。一个旅行售货员，从城市 v0 出发，走遍所有的城市，再回到 v0。 询问：售货员应该怎样走，才能使走过的总距离最短？ 2018/12/8 山东大学 软件学院
TSP实例 2018/12/8 山东大学 软件学院
TSP实例 www.princeton.edu 2018/12/8 山东大学 软件学院
建模 变量 xij：是否使用从城市 vi 到城市 vj 的路径。 约束 每个城市只能到达一次、离开一次。 所走过的路径构成一个圈（不能多于一个圈）。 2018/12/8 山东大学 软件学院
TSP的整数规划 2018/12/8 山东大学 软件学院
强制路径构成仅一个圈 2018/12/8 山东大学 软件学院
整数线性规划的特征、模型 特征—变量整数性要求 性质—可行域是离散点的集合 整数线性规划的常见模型： 问题本身的要求 引入的逻辑变量的需要 一般整数规划模型——变量取值为整数。 0-1整数规划模型——变量取值为0或1。 混合整数规划模型——部分变量取值为整数，部分变量取值为实数。 2018/12/8 山东大学 软件学院
整数规划与线性规划的关系 整数规划 线性规划 线性规划是整数规划的放松。 整数规划的可行解是对应的放松问题的可行解。 放松的线性规划的最优值 整数规划的最优值。 2018/12/8 山东大学 软件学院
解整数规划 对整数规划的几点说明： 对放松问题的最优解进行简单的舍入（如，四舍五入）不能得到整数规划的最优解。这样的整数解对于原整数规划甚至是不可行的。 整数可行解的数目可呈爆炸性增长，简单的枚举法不可取。 2018/12/8 山东大学 软件学院
算法 求精确解： 割平面算法 分枝定界算法 求近似解： 舍入法 原始-对偶方法 2018/12/8 山东大学 软件学院
割平面算法[Gomory, 1958] 基本思想 用单纯形法解松驰问题(P0)，求到最优解x0。 若x0是整数向量，则x0是ILP问题(P)的最优解，计算结束。 否则，根据x0设法对(P0)增加一个约束条件，称为割平面条件。这个割平面条件将(P0)的可行域割掉一块，且x0在被割掉的区域中，而原ILP的任何一个整数可行解都没有被割掉。 记增加了约束条件的问题为(P1)。对(P1)继续上述过程，直到求到一个整数最优解为止。 2018/12/8 山东大学 软件学院
说明 如果在增加约束的过程中，得到的LP没有可行解，则原ILP没有可行解。 如果得到的LP问题无界，则原ILP问题或者无界，或者没有可行解。 2018/12/8 山东大学 软件学院
割平面生成方法 2018/12/8 山东大学 软件学院
割平面生成方法 2018/12/8 山东大学 软件学院
割平面生成方法 2018/12/8 山东大学 软件学院
注意 2018/12/8 山东大学 软件学院
Gomory割平面算法 求放松问题的 最优基可行解 是否为 整数解？ 是 得到最优解， 停止。 否 将割平面方程加入到单纯形表，得到新的松弛问题。用对偶单纯形算法求最优解。 2018/12/8 山东大学 软件学院
算例 (1,1.5) x1 x2 3x1 + 2x2 = 6 3x1 + 2x2 = 0 2018/12/8 山东大学 软件学院
得到松弛问题LP0 2018/12/8 山东大学 软件学院
解松弛问题LP0 2018/12/8 山东大学 软件学院
得到松弛问题LP1 2018/12/8 山东大学 软件学院
解松弛问题LP1 2018/12/8 山东大学 软件学院
得到松弛问题LP2 2018/12/8 山东大学 软件学院
解松弛问题LP2 2018/12/8 山东大学 软件学院
对割平面的解释 2018/12/8 山东大学 软件学院
对割平面的解释 x1 x2 3x1 + 2x2 = 6 3x1 + 2x2 = 0 x2 = 1 x1 x2 = 0 2018/12/8 山东大学 软件学院
2018/12/8 山东大学 软件学院