动机
分数最优点指出线性松弛过于宽松之处,但拒绝该点很容易,很多不等式都办得到。真正要求是保留每个整数可行点。割的理由必须来自整数性、行方程及变量符号,而不是只看当前答案划一条线。
表格割使用简单算术:整数部分加上非负变量乘系数分数部分,必须保留右端同一个分数余数。若后者加权和非负,它就不能落在零与所需正余数之间,因而得到当前分数基违反的不等式。
加割后,下个线性最优点仍可能分数。连续有效割可使上界下降,却永远不在有限步达到整数答案。要论证算法,必须指定如何选割、如何解线性问题,以及何时必须分支。有效性与有限终止是两份不同的数学承诺。
定义
定义 7.1.1
(分数部分与纯整数表格行)
实数 的下取整为不大于它的最大整数,分数部分 。考虑
本纯整数推导要求出现的每个变量,包括普通松弛,都为整数。目前基本点令非基本量全零、,所以违反整数性。
有理原数据若需要整数松弛表示,应先以正公分母乘各不等式,再加松弛。整数系数及整数右端配整数决策,才保证普通松弛整数。人工量或新连续量不因出现在表格中就自动变整数。
割平面对全部整数可行点有效,并违反某个指定松弛点。分支割平面节点包含祖先限制、有效新增割及分支变量域。最大化节点的线性值只有在最优性或另一对偶上界已证明后,才能作上界;任意松弛可行点的值不能代替它。
定理/命题
定理 7.1.2
(纯整数 Gomory 分数不等式)
在上述行假设下,每个整数可行点满足
目前非基本量全零的基本点违反它。负系数必用数学下取整,不能向零截断。
命题 7.1.3
(聚合及取整产生有效割)
设 且 为整数,取 使 为整数行,则全部整数可行点满足
这称为聚合取整或 Chvátal–Gomory 不等式。对上界限制,聚合乘数必非负。
定理 7.1.4
(一组足够的有限分支割平面策略)
指定整数变量都有有限整数上下界,每个处理的节点线性问题不可行或有已取得的有限最大值。每节点只用有效割,在关闭或分支前只产生有限个割,并以有限终止精确方法解线性子问题。按分数整数坐标的下取整/上取整析取分支,最终处理所有存活节点,则搜索有限终止,证明整数不可行或回传全局最优。
在节点线性问题符合上述条件时,策略也适用于保留连续变量的混合整数模型,但纯整数分数割不能因此套在连续列上。无界松弛需要另外有效的整数无界分析,或先假设松弛有界,不能单凭线性无界就宣称节点已解决。
证明思路
证明
(同余与非负性给出分数割)
把行中各系数与右端拆成整数、分数部分,移项得
分数加权和非负,且与右端有同一个严格介于零与一的余数,所以最小非负可能值就是该余数。这证明割。当前非基本量全零,左边加权和为零,小于正右端,故确实分离目前点。
负系数没有障碍,例如 而非负半。连续变量却破坏关键步:整数系数乘连续值未必整数,原来同余关系便不成立。这正是不能把纯整数公式直接当混合整数公式的理由。
证明透视
每个假设在分数割中的位置
记 。证明有三个输入和一个收尾步骤。每个变量都是整数,使 为整数;连续列破坏的正是这一步,下面的反例会说明。下取整的约定使每个 都在 内,再加上变量非负,便得 。收尾步骤把这些与 结合:整数 大于 ,所以至少为 。
假设 只用于分离。若余数为零,不等式便是 ,有效却无用。分离本身不需要任何关于整数点的事实:当前基本解的每个非基本坐标都是零,所以 。
证明
(非负聚合与整数取整)
聚合定理以非负乘数相加得 。左边已知为整数,所以不超右端下取整。证明不用最优表格或特定目标。有效割也可能不违反目前点;这时它虽合法,却没有分离该点。
证明
(有限树上的覆盖与现任解不变量)
有限搜索维持两个不变量:每个原整数可行点仍被某个活节点涵盖,除非已由有效关闭证书处理;每个现有最佳解都是真正整数可行点。有效割保留前者,两边分支覆盖父域;不可行、整数松弛最优及足够上界则合法关闭。
沿树往下,每个分支使至少一个整数区间严格缩短一个整数单位,深度不超原区间宽度总和,故二元树有限。每节点有限割与有限线性求解给有限工作。所有节点关闭后,不变量保证没有更佳整数点;若未找到任何可行整数点,便证不可行。
搜索必须最终处理全部活节点。即使抽象树有限,若安排方式永远重做无关工作,仍不构成终止算法。某节点若无限加割,亦违反有限工作条件,即使每个割合法、每次线性求解都完成。
例题详解
例题 7.1.5
(负表格系数贡献正分数)
取纯整数非负行
两个非基本系数分数部分都为半,因 。割为 ,即 。
松弛基 被删去;整数点 及 都满足行及割。把负系数的分数部分错当负数,就得到不受证明支持的另一式,并非容许的软件惯例。
例题 7.1.6
(两个有效割的强度不同)
最大化 ,限制 , 非负整数。松弛最优 值 。各限制乘三分之一再相加得 ,左端整数,故割 。点 都达二,完整关闭目标差距。
另引整数松弛 ,基本行为
标准左边系数是 ,分数部分均 。分数割为 ,即松弛和至少半。由 ,直接线性形式是 。它有效且删旧解,却弱于聚合割二;不能声称每个分数割一步都封住全部差距。
概念视角代数
分数割其实是聚合取整割
表格割是换了形式的 Chvátal–Gomory 割。由 ,该行给出 ;左边是整数,故不超过 。把它从行方程中减去,恰好得到 。在上例中, 的行给出 ,代入 便回到 。
例题 7.1.7
(一般整数树以两个证书关闭)
最大化 ,限制 , 非负整数。容量还给 。松弛先用较高单位容量收益的 到三,再用 ,值十六。
分支 或 。前者给 值十五。后者有
点 达十三,所以这是精确节点上界,低于现有十五,可关闭。两边覆盖 的全部整数情况,并非只处理二元值,故十五全局最优。
反例模式
连续非基本变量不能套纯整数割
设 , 非负整数、 连续。可行点 存在;纯整数公式却会以 得 ,错删可行点。修补是保留纯整数假设,或另外推导适当混合整数不等式,不能把连续列自行宣称整数。
有效且严格改善仍可不终止
最大化整数 ,原限制 ,整数最优一。依次加有效有理割 ,。第一步以后,每个新割都删去前次松弛最优并严格改善上界,但每个有限阶段最优仍分数且大于一,只在极限靠近答案。
这不反驳某个选割及字典序重优化规则完整指定的 Gomory 有限收敛定理;它反驳的是“有效加严格改善必有限”这个过强说法。专门纯割收敛证明另需条件;本节证明的策略是限制每节点割数,再以穷尽分支保终止。
常见错误
常见错误
(左端不是整数时把右端下取整)
只有左端已知整数,才可把上界右端下取整。有理系数乘整数变量未必整数:由 不能推出 ,否则会删去整数点 。负聚合乘数也未必保留上界方向。两种错误都可能删掉真正最优点。
常见错误
(加割后沿用旧的原始比值检验)
新割可令旧原始基不可行,即使整数模型未变。重优化须恢复原始或对偶不变量,不能不检查可行性就沿用旧比值检验。精确的线性规划终止可由第一阶段及前一单元的防循环规则提供。
常见错误
(没有目标格点便以小差距关闭节点)
小目标差距不等于精确关闭,除非已证目标值落在可用取整的格点;连续目标项可以取消这一保证。数值容差与系数尺度另须分析。
总结
分数割由同余及非负性而来;聚合割由非负组合再用整数取整而来。两者都要明确假设,强度也不同。有限搜索另外需要有界整数域、每节点有限割工作、终止精确线性求解及完整处理;单有有效性并不足够。
练习
快速检查
(从纯整数行 推导分数割。)
解答 · 答案
分数部分为 ,因 ;右端余数 。故 ,即 ,非基本量全零时确实违反。
快速检查
(对整数 的限制 ,聚合得到 的有效界,与分数交点比较。)
解答 · 答案
各乘四分之一相加得 ,再用左端整数得 。分数交点 被删去; 达二,所以在另加非负性时同样证明最大和二。
快速检查
(一般整数例把 明写出来,会否删去根节点分数解?)
解答 · 答案
不会。点 已满足此界。它是证有限域的有效限制,却不分离目前点;有效、分离及强度是不同性质。
快速检查
(给一维不终止割例一个有限搜索策略,指出原割序列缺少哪项假设。)
解答 · 答案
最多作固定有限次割,然后对分数 分成 与 。后者与原上界矛盾,前者取得整数最优一。原序列缺少分支前有限工作规则,即使整数域有界、每个后续割严格改善也不够。