有些线性规划的变量多得难以逐一列出,但每个变量的意义都很简单。在切割备料问题中,一个变量表示采用某个单条原料切割方案的次数。可行方案可能很多,实际解通常只用其中少数。列生成先以一小部分方案求解,再用另一个优化问题判断是否有值得加入的方案。停止的证据来自对偶性,而不是因为我们暂时想不到其他方案。
以下假设模式集合有限且计算精确;重要限制会在文中说明。
动机
假设每条原料长 10,产品长度分别是 3 和 4。一条原料可以切成三件第一类、两件第二类,或两件第一类加一件第二类。模式记录单条原料产生的各类件数。这个小例子可以枚举所有模式,但当类别和原料长度增加时,枚举可能很繁重。我们希望有严谨方法挑选模式,而无须预先猜对哪些有用。
定义
设 是有限、非空的模式集合。模式 产生非负向量 ,成本为 。对需求 ,考虑完整主问题
这里容许 为分数;若它表示原料条数,这就是整数问题的松弛。不等式容许超额生产;若要求生产量恰好等于需求,对偶变量的符号限制便不同。
对非空子集 ,受限主问题只保留 中的变量。将其余变量设为零,可把受限可行解延伸为完整主问题的可行解。受限问题的对偶是
对候选对偶向量 ,模式的约化成本为 。定价问题是在所有 上最小化 。这是另一个优化问题,不能只检查已在 中的模式。
定理与命题
定理 17.1.1
(定价给出的全局证书)
假设受限主问题可行,且取得有限最优值。设 分别是其原始和对偶最优解。若每个 均满足 ,则将 的其余分量补零后得到 (1) 的最优解,且 是完整对偶的最优解。
证明与思路
证明
(弱对偶补上受限问题留下的缺口)
受限对偶可行性给出 。定价条件补上所有遗漏的不等式 ,因此 对完整对偶可行。对任何完整主问题可行解 ,由非负性得到
这直接证明弱对偶。受限主问题可行且最优值有限,线性规划强对偶性给出 的目标值等于 。补零后的解对完整主问题可行,并达到刚得到的下界,因此两者分别为完整原始问题和对偶问题的最优解。此证书涵盖整个线性规划,却不保证分数解是整数解。
证明透视
定价究竟证明什么
受限原始解也是完整问题的可行解,所以其值是完整最小值的上界。受限对偶解可能违反某个遗漏列的不等式,未必对完整对偶可行。定价正是检查所有缺失的不等式;若没有违反,同一个数亦是下界,两个界便相等。
命题 17.1.2
(有限模式下的有限列生成)
假设 有限、所有成本 非负、初始受限主问题可行,且每次都精确求解受限主问题。每一轮选取受限对偶最优解 并精确求解定价:若最小约化成本为负,加入一个达到该最小值的模式;否则停止。此程序经有限次加列后停止,并给出完整主问题的最优解与对偶证书。
证明
(从有限集合中加入互不相同的模式)
由 对受限对偶可行, 中的模式都不会有负约化成本。因此每次加入的模式均为新模式,最多加入 次。之后每个受限问题仍可行,因为原解仍可使用;成本和变量均非负,目标值以下界零限制。由线性规划最优值存在定理,每轮均取得有限最优值。停止时,精确定价检查了完整对偶的所有不等式,上述定理便给出结论。
非负成本确保每轮的最优值有限;更一般的成本需要另外证明有界。加入负约化成本的列后,下一轮最优目标值不一定严格下降:退化可能使其不变。这里的有限终止依靠每次加入不同的列,并非依靠目标值严格下降。
例题详解
例题 17.1.3
(两类产品和一个有用的遗漏模式)
长度为 10 的原料每条成本为 1,两类产品长度为 3 和 4,需求为 。模式 的分量是非负整数且满足 。先取 ,受限主问题为
其最优解为 ,值为 。对偶最优解是 ,因为 、。定价即在整数 和 下最大化 。 只可能是 0、1、2;分别得到最大值 、、。因此 的约化成本为 ,应加入该模式。
加入后,使用两次模式 ,恰好满足需求,值为 2。为证明最优,取 。当 时,所有模式中 的最大值分别是 。因此每个模式的对偶值都不超过其单位成本, 对完整对偶可行。其目标值 ,等于上述原始解。线性规划最优值是 2;这个解同时使用整数条原料,所以也是整数最优解。
例题 17.1.4
(分数主问题值不是原料条数)
保留相同原料和产品长度,改为每类需求一件。分数方案 、 满足两类需求,成本为 。对偶向量 对所有模式仍可行,目标值亦为 ,故这是线性规划最优值。整数最优值则为 1:一条 已满足需求,且任何整数可行解至少使用一条。把两个分数变量各自向上取整恰好使用两条,并非最优。
例题 17.1.5
(零需求与不唯一的受限对偶解)
保留相同原料和模式,需求改为 ,并再次由 开始。受限主问题是在 、、 下最小化 ,最优解为 ,值为 1。其对偶是在 、、 下最大化 ,所以每个 ()都是最优解:零需求令 无法确定。
取 时,定价在所有模式上最大化 ,最大值是 的 1,所有约化成本非负,完整线性规划最优值被证明为 1。若改取 ,模式 的约化成本是 。加入它并不降低受限最优值:只用 需要 ,成本为 ,所以最优值仍是 1。负约化成本反映的是所选的对偶解,而加入模式也未必严格改善目标值。
常见错误
反例模式
受限最优不代表完整最优
第一个例子中,使用最初两种模式的最优值是 ,但遗漏的 有负约化成本,完整问题存在两条原料的解。因此受限问题已求至最优,仍不能单独证明全局最优。反过来说,负约化成本表示所选对偶证书失效,并不保证下一个受限目标值严格下降。
常见错误
(把定价启发式找不到模式当作证书)
定价启发式可以找到有用模式;但它找不到模式,不能证明所有约化成本非负。精确定价,或最小约化成本的一个非负的有效下界,才提供所需证书。约化成本取决于所选的对偶最优解;另一个对偶最优解可能给出不同的约化成本。第三个例题正好展示这种依赖。
快速检查
快速检查
(为什么受限目标值是完整最小值的上界?)
解答 · 答案
因为将所有遗漏变量设为零,任何受限可行方案仍对完整主问题可行。对最小化问题增加选择不会令最优值上升。
习题
快速检查
(对上述长度为 10 的模式,判断 是否对完整对偶可行;若否,明确指出违反的不等式。)
解答 · 答案
不可行。 满足 ,但其对偶不等式要求 ,显然不成立。
快速检查
(需求为 时,验证分数最优值 和整数最优值 1,不要假设取整一定能求解整数问题。)
解答 · 答案
第二个例子的分数解与达到相同值的可行对偶解证明线性规划值为 。一条 已满足需求,而正需求排除零条原料,因此整数值为 1。
快速检查
(若受限最优值为 9,其对偶向量在所有模式上的最小约化成本为 0,完整线性规划最优值是多少?整数最优值必定为 9 吗?)
解答 · 答案
由定价证书和受限原始、对偶目标值相等,完整线性规划值为 9。若没有成本为 9 的整数可行方案或进一步整数分析,不能断言整数值为 9;它可能更大,如第二个例子所示。
快速检查
(若只近似求解定价,抽查所得最小约化成本为 ,这能证明完整线性规划最优吗?还需要什么事实?)
解答 · 答案
不能。未检查的模式可能有负约化成本。若能严谨证明所有模式上的最小值下界至少为零,或精确求得全局最小值非负,便足以证明。