动机
通讯系统可分配半单位传输时间,却不能安装半个不可分割的中继装置。编译器要决定是否启用某项转换,同时给已启用工作分配连续处理时间。整数规划把这些离散选择写进模型;移除整数性虽可能令计算较容易,却改变了什么决策算可行。
线性松弛仍有作用。最大化时,允许额外分数点只会提高最佳值,因此松弛最优值是整数模型的上界。这是可行集包含关系的结果,不依赖某个软件。把分数答案直接当成可实现决策,正是丢失了建整数模型的理由。
真正困难是证明没有漏掉更好选择。分枝定界把整数决策分成穷尽情况,再用有效上界整批排除。有效不等式则删去分数点而保留全部整数决策。另有特殊矩阵结构保证顶点全是整数,使线性松弛已能解决离散问题;这种保证必须证明,不能由小例子猜出。
定义
定义 3.1.1
(整数模型、松弛、现有最佳解及界)
整数线性最大化问题可写为
二元变量只可取零或一;混合整数模型只要求指定变量为整数。线性松弛把整数限制改成实数限制,其他条件不变。
现有最佳解必须是真正可行的整数点,其值 是最大值的下界。有效上界 必须不小于相关搜索区域内每个可行整数目标值。
整数可行点的凸包称为整数包。对全部整数可行点成立的线性不等式称为有效不等式;加入它可收紧松弛而不改变原整数问题。要把某不等式用作割平面,必须先证明它保留每个整数决策,不能只看它是否删去目前分数点。
概念视角几何
整数规划是在整数包上的线性规划
设整数可行集 有限且非空,其整数包为 ,松弛多面体为 。则 是顶点都在 中的多胞形,而线性目标在 上的最大值在某个顶点取得,所以 。由于 ,松弛界只会更大。有效不等式恰好是在 上成立的线性不等式;每个割平面都把 推向 ,而下面的整数性定理描述的正是 的有界情形。
建模也是推理。若二元 表示是否启用工作,而连续工作量有已知上界 ,限制 使停用时工作量为零,但不迫使启用时工作量严格为正。 必须由模型推导:过小删掉合法安排,过大则使松弛变弱。
整数矩阵若每个方形子矩阵的行列式都为零、正一或负一,称为全单模。这要求检查所有方形子式,并非只看整个矩阵的一个行列式。对本节的非空有界多面体,全部顶点都是整数便保证它等于整数点凸包,称为整多面体。
定理/命题
命题 3.1.2
(松弛界为剪枝提供理由)
最大化搜索节点若有已证明的有限松弛上界 ,而现有整数解值为 ,则 时此节点不能改善现有解。松弛不可行表示节点内没有整数可行点。松弛最优点若已是整数,便同时解决该节点的整数问题。
只求一个最优解时,相等也可剪枝;若要列出全部最优解,同界节点可能藏有其他最优点,须另外处理。目标值差距也不是决策向量之间的距离。
定理 3.1.3
(全单模令基本解成为整数)
设整数矩阵 全单模且有满行秩,右端 为整数向量。则 的每个基本可行解都是整数。若此标准形线性问题有已取得的有限最优值,便有整数最优解。
矩阵性质及整数右端缺一不可。只有整数系数并不足够。结论也不是每个可行或最优点都为整数;整数顶点的凸组合仍可能有分数坐标。
定理 3.1.4
(有向图的关联矩阵是全单模的)
有向图的节点—弧关联矩阵(每条弧在弧尾放 、在弧头放 )是全单模的。附加单位行或单位列后仍保持全单模。
证明思路
证明
(嵌套可行集与穷尽分枝)
节点的整数可行集包含在松弛可行集内,故所有整数目标都不超过松弛最优值,也不超过其有效上界。若上界不高于已取得的整数值,便不能有改善。空的松弛集没有整数子集;若松弛最优点恰为整数,它已在子集内取得同一上界。
若松弛最优点的某个指定整数坐标为分数 ,每个整数坐标值恰好符合以下一边:
两个子节点涵盖父节点全部整数点,并排除目前分数解。完整证书需要这个穷尽分解,以及每个叶节点的关闭理由:不可行、上界足够,或松弛最优点已整数。只展示搜索过的最好点,还不是全局证明。
全部指定整数变量若有有限整数上下界,且不重复处理相同节点,这种分枝有限步终止。每次沿树往下都把至少一个整数坐标区间严格缩短,路径长度受原区间宽度总和限制;分枝数有限且深度有界,树便有限。无界整数域需要额外论证,本节不作普遍终止保证。
证明
(单模基矩阵的整数逆矩阵)
全单模定理取任意非奇异基矩阵 。其行列式为非零子式,故必为正负一。伴随矩阵公式显示 的每项都是整数余因子除以正负一,因此仍是整数。 为整数,非基本坐标为零。再用线性规划的基本最优代表定理,只要线性最优值已取得,便得到整数最优点。
网络矩阵为什么符合条件
证明
(对子式大小归纳)
有向图的关联矩阵 在弧尾放负一,在弧头放正一。非自环弧有两个相反非零项;自环弧的头尾贡献抵消,整列为零。任取方形子矩阵:若某列全零,行列式为零;若某列只有一个非零项,沿列展开降为较小子式的正负值;若每列都有两个非零项,两项符号相反,所有行相加为零,行列式也为零。归纳即证全单模。
证明透视
相反符号在何处被使用
归纳分三种情况,只有最后一种用到图的结构。零列及只有一个非零项的列,对任何元素属于 的矩阵都可处理:前者给出零行列式,后者经展开化为较小的子式。关键情况是方形子矩阵中每一列都保留两个非零项。此时相反符号 与 使每列之和为零,全一的行组合消失,故行列式为零。
没有方向时失效的正是这一步。三角形的无向关联矩阵每列都有两个 ,其行列式为 。证明也从未用到图的大小或连通性,所以删去行、附加单位行或单位列都可用同一展开处理。
删去冗余关联行保留此性质,附加单位列或单位行也可用同一展开法证明。具容量的流可写为
任一子式先沿松弛列展开,再沿只剩单个原变量项的容量行展开,便化为关联子式。移除冗余等式可得到满行秩。因此整数供需及容量给出整数顶点;最小费用流即使用线性规划求解,也有整数最优代表。任意新增耦合限制未必保留这个证明。
例题详解
例题 3.1.5
(一棵附完整证书的小搜索树)
二元工作开关 最大化 ,限制 。松弛加上 ,最优点 值四;先分配给系数较大的 ,余下半单位总额给 。
按 分枝。 时松弛最优为 ,产生整数现有解值三。 时 ,松弛上界为 。由于原整数目标系数及变量都整数,实际目标是整数,故此节点可用向下取整上界三,不能改善现有解。
两个子节点涵盖 的全部值,各有合法结论,故 全局最优。若没有整数目标假设,单凭 并不能剪枝,仍需下一步分枝或更强证书。上界中的任何取整步骤都必须有自己的假设。
例题 3.1.6
(把松弛解向下取整仍会丢失最优值)
二元选择满足
松弛按收益与容量比 分配,得 、值 。也可独立证明:容量乘 再加 的 倍,所得系数逐一不小于目标系数,上界为 。
向下取整给 、值七,但 可行且值八。若 ,其他两项都放不下,值至多七;若 ,其余两项都可选,值至多八。这两种穷尽情况证明整数最优值八。
项目一、二合用容量七大于五,形成覆盖,故有效不等式 保留每个二元可行点。分数最优点的左边为 ,因此被割去。一条覆盖不等式未必足以描述整个整数包。
例题 3.1.7
(辨认结构性整数保证及其限制)
整数容量、整数供需的网络流顶点由上述关联矩阵论证保证为整数。例如单弧模型的尾端供一、头端需一,容量至少一时,唯一可行弧流便是一。
但标量模型 最大化 ,其一阶子式为二,不全单模;松弛顶点为半,整数最优为零。整数数据并没有阻止分数顶点。
即使系数矩阵全单模, 的非整数右端仍给半这个分数最优值。反过来,不全单模也不表示每个右端都有差距: 最大化 时,两个模型都以一最优。定理提供充分结构保证,不是判断每个个别实例的必要条件。
常见错误
常见错误
(取整只是启发式,不是证明)
向下取整只是启发式。非负系数的容量上界模型中,它保持可行,却不保证最优;等式、负系数或下限需求则连可行性也可能破坏。向上取整甚至可超出普通容量上限,每次都要重查实际限制。
常见错误
(上界必须覆盖节点内每个整数点)
最大化的某个松弛可行点只提供已取得的值,不自动是上界。上界应来自已证明的松弛最优值、对偶可行点或有效不等式论证。中途停止的求解器所给的当前点与其已证明的界,意义并不相同。不能因分数坐标“接近整数”便跳过精确条件;数值容差另须明确政策及可行性重查。
常见错误
(松弛无界不证明存在改善的整数点)
松弛无界也不保证整数模型有改善射线。例如指定 整数,限制 而最大化 ,松弛无界但整数可行集空。
有效割不能只凭排除当前观察到的分数最优点来证明,必须保留全部整数可行点。覆盖不等式依赖二元上界及非负容量系数;把同一公式套在不受限制的整数重数上会改变论证,并可能删去可行解。
反例模式
整数顶点不表示每个最优点都整数
错误推论是全单模保证软件返回的任何最优点都整数。取 ,目标恒为零;矩阵全单模且两个顶点为整数,但中点 也最优,它是两顶点的平均。正确结论是在定理假设下存在整数基本最优点。若算法返回最优面内点,整多面体性质本身不会把该点自动变成整数。
总结
整数限制改变可行集。松弛界、穷尽分枝及有效割各提供最优性证明的一部分;某些网络矩阵直接保证整数顶点。向下取整目标界需要整数目标,基本终止证明需要有限整数域,全单模结论需要整数右端;每个假设都有实际工作。
练习
快速检查
(第一例把目标改为 ,求松弛值及整数值,写出两种情况的完整证书。)
解答 · 答案
松弛容许 ,值 ,例如 达到。整数情况若 ,二元 给值至多三;若 ,容量迫使 ,也至多三。 及 都达到三,所以三是整数最优值。分数决策能达到较大松弛值,却非可实现二元安排。
快速检查
(证明背包例的 是有效覆盖不等式。 也有效吗?)
解答 · 答案
同选一、三用容量六大于五,所以二元可行点至多选其中一个。二、三的容量和恰为五,点 可行,却违反第二个提议,故后者无效且会删去真实最优解。
快速检查
(最大化节点有已证上界 ,现有解值十一。若所有目标值整数能否剪枝?若目标另含系数二分之一的连续变量呢?)
解答 · 答案
整数目标不超过 ,只求一个最优解时可以关闭。连续项取消这个整数保证,节点可能有 等超过十一的值;单凭原上界便不能关闭。
快速检查
(证明把松弛点 向下取整会违反整数需求 ,另给可行整数点。最小化时松弛界方向如何?)
解答 · 答案
向下取整是一,违反下限;整数二可行。最小化在更大的松弛集合上取最小值得到下界,实际可行整数解则提供上界。与最大化相比,偏好方向反转,两种界的角色也反转。
快速检查
(证明全单模矩阵附加一个单位列后仍全单模。为什么不能据此宣称任意耦合行也安全?)
解答 · 答案
任取方形子式,不含新列时原已符合条件;含新列而其中全零时行列式为零;否则沿其唯一非零项展开,得到原矩阵较小子式的正负值,仍为零或正负一。任意耦合行可有很多非零项,这种单项展开未必适用,需要另外证明其子式性质。