跳转至

整数线性规划

这节我们讨论的一个核心概念是integral polyhedra(整数多面体). 当线性规划问题的约束矩阵具有特定性质的时候, 所有基本可行解都自动是整数向量, 无需额外的整数约束. 传统线性规划可能产生分数解, 但某些特殊的约束矩阵结构能保证解的整数性.

全幺模矩阵

背景

我们有一个整数规划问题(IP), 希望最小化\(c⋅x\), 约束条件是\(Ax=b\), 并且\(x\)必须是正整数. 直接求解整数规划通常很困难. 一个常用的技巧是先忽略"整数"这个要求, 把它变成一个普通的线性规划问题(LP). 解线性规划要容易得多. 如果我们能找到一种情况, 使得LP问题的最优解恰好总是整数, 那么这个解也就是原来IP问题的最优解. 我们的目标就是探究, 矩阵\(A\)和向量\(b\)需要满足什么性质才能保证这一点.

线性规划的理论告诉我们, 如果LP问题又一个最优解, 那么至少存在一个基本可行解是最优的, 基本可行解的形式是\(x_B=A_B^{-1}b\), 其中\(A_B\)是从\(A\)中选出的一些列组成的方阵(称为基矩阵), \(b\)是已知的整数向量. 为了让\(x_B\)是整数, 一个充分条件是\(A_B^{-1}\)本身是一个整数矩阵. 根据线性代数理论(Cramer法则), 如果一个整数矩阵\(A_B\)的行列式\(\det(A_B)\)的值是\(1\)或者\(-1\),那么它的逆矩阵\(A_B^{-1}\)就一定是整数矩阵.

幺模矩阵

想要了解全幺模矩阵, 我们首先从一个更加弱的概念开始, 那就是幺模矩阵. 下面是幺模矩阵的正式定义和一个重要定理.

定义6.1(什么是幺模矩阵): 一个\(m×n\)的整数矩阵\(A\), 如果它满足以下两个条件, 就被称为幺模矩阵: 1. 满行秩(full row rank): 矩阵的行是线性无关的. 2. 基行列式为\(±1\): 从\(A\)中任意选取\(m\)个线性无关的列组成一个\(m×m\)的方阵(称为一个基(basis)), 这个基的行列式的值必须是\(1\)或者\(-1\).

定理6.1(幺模矩阵的充要条件): 一个满行秩的整数矩阵A是幺模矩阵, 当且仅当对于所有可能的整数向量\(b\), 由约束条件\(\{x \in \mathbb{R}^n : Ax=b, x \ge 0\}\)定义的多面体(polyhedron)都是一个整多面体(integral polyhedron).

证明定理6.1

前提: 假设矩阵A是幺模矩阵.

目标: 证明多面体\(\{x : Ax=b, x \ge 0\}\)的任意顶点(extreme point)x都是整数向量.

证明步骤:

  1. 根据线性规划理论, 任何一个顶点\(x\)都对应一个基本可行解. 这意味着\(x\)可以由一个基矩阵\(A_B\)算出, 其基本变量为\(x_B = A_B^{-1}b\).
  2. 我们的目标是证明\(x_B\)是整数.
  3. 根据克莱姆法则(Cramer's rule), 矩阵的逆可以表示为: \(A_B^{-1} = \frac{\text{Adj}(A_B)}{\det(A_B)}\).
  4. 其中\(\text{Adj}(A_B)\)是\(A_B\)的伴随矩阵. 因为\(A_B\)是一个整数矩阵, 它的伴随矩阵也必然是整数矩阵.
  5. 根据前提, \(A\)是幺模矩阵, 所以其任意基矩阵的行列式\(\det(A_B)\)的值只能是1或者-1.
  6. 因此, \(A_B^{-1} = \frac{\text{一个整数矩阵}}{\pm 1}\), 这说明\(A_B^{-1}\)本身就是一个整数矩阵.
  7. 由于\(x_B = A_B^{-1}b\), 而\(A_B^{-1}\)和\(b\)都是整数的, 它们的乘积\(x_B\)也必然是整数向量.
  8. 这就证明了任意顶点\(x\)都是整数, 正向证明完毕.

前提: 假设对于任意整数向量\(b\), 多面体\(\{x : Ax=b, x \ge 0\}\)的顶点都是整数.

目标: 证明矩阵\(A\)是幺模矩阵, 即证明\(A\)的任意基矩阵\(A_B\)的行列式都是1或-1.

证明步骤:

  1. 任取一个\(A\)的基矩阵\(A_B\). 我们需要证明\(|\det(A_B)| = 1\).
  2. 这里使用一个巧妙的构造方法. 我们令右侧向量\(b = A_B z + e_i\). 其中\(e_i\)是一个单位向量(第\(i\)个位置是1, 其余是0), \(z\)是一个足够大的整数向量, 用以确保最终的解\(x_B \ge 0\)从而满足可行性.
  3. 计算此时对应的基本解: \(x_B = A_B^{-1}b = A_B^{-1}(A_B z + e_i) = z + A_B^{-1}e_i\).
  4. 根据前提, 由于我们构造的\(b\)是一个整数向量, 那么解\(x_B\)也必须是整数向量.
  5. 因为\(x_B\)是整数, \(z\)也是整数, 所以\(A_B^{-1}e_i\)必然是整数向量.
  6. \(A_B^{-1}e_i\)这个乘积的结果正好是\(A_B^{-1}\)矩阵的第\(i\)列.
  7. 因为\(i\)可以是我们任选的, 这就说明\(A_B^{-1}\)的每一列都是整数向量, 从而\(A_B^{-1}\)整个矩阵都是整数矩阵.
  8. 现在我们知道:
    • \(A_B\)是一个整数矩阵.
    • \(A_B^{-1}\)也是一个整数矩阵.
  9. 一个整数矩阵的行列式必然是一个整数. 所以\(\det(A_B)\)和\(\det(A_B^{-1})\)都是整数.
  10. 根据线性代数的基本性质, \(\det(A_B) \cdot \det(A_B^{-1}) = \det(I) = 1\).
  11. 两个整数相乘等于1, 那么这两个整数只有两种可能: 都是1, 或者都是-1.
  12. 无论是哪种情况, 都有\(|\det(A_B)|=1\).
  13. 因为\(A_B\)是我们任选的一个基, 所以结论对所有基都成立. 这就证明了\(A\)是幺模矩阵, 反向证明完毕.

全幺模矩阵

定义6.2(全幺模矩阵,TUM): 一个矩阵\(A\)被称为全幺模矩阵, 如果它的每一个方子矩阵(square submatrix)的行列式(determinant)的值都是0, 1, 或者-1.

和定义6.1的关键区别

这比我们之前讨论的"幺模矩阵(unimodular)"条件更强.

  • 幺模矩阵只要求\(m \times m\)的基矩阵(basis)的行列式是1或-1.
  • 全幺模矩阵要求所有尺寸(\(1 \times 1\), \(2 \times 2\), 等等)的方子矩阵的行列式都只能是0, 1, 或-1.

定理6.2(全幺模矩阵的充要条件): 一个整数矩阵\(A\)是全幺模矩阵, 当且仅当对于所有整数向量\(b\), 由不等式约束\(\{x \in \mathbb{R}^n : Ax \le b, x \ge 0\}\)定义的多面体是一个整多面体(即所有顶点都是整数).

和定理6.1的关键区别

这个定理针对的是含有不等式\(Ax \le b\)的线性规划问题, 这比之前定理6.1中\(Ax=b\)的形式更具一般性. 结论是, TUM这个更强的性质, 保证了更一般形式LP问题的整数解.

证明定理6.2

证明的核心思想是把不等式问题\(Ax \le b\)转换成我们熟悉等式问题. 通过引入松弛变量\(z\), 我们可以把\(Ax \le b\)写成\(Ax + Iz = b\) (其中\(I\)是单位矩阵).

证明的关键在于以下两个等价关系: 1. 矩阵\(A\)是全幺模的(TUM) \(\iff\) 增广矩阵\([A \ | \ I]\)是幺模的(unimodular). 2. 不等式问题\(\{x: Ax \le b, x \ge 0\}\)的顶点是整数 \(\iff\) 等式问题\(\{(x,z): Ax+z=b, x \ge 0, z \ge 0\}\)的顶点是整数.

通过证明这两个等价关系, 就可以把定理6.2(关于TUM和不等式)转化成定理6.1(关于unimodular和等式)的情况, 从而完成证明.

全幺模矩阵的性质

四个基本性质

如果一个矩阵\(A\)是全幺模矩阵, 那么:

  1. 矩阵的元素必须是0, 1, 或-1.

    原因: 矩阵中的任何单个元素本身就是一个\(1 \times 1\)的子矩阵. 根据TUM的定义, 这个子矩阵的行列式(也就是元素自身的值)必须是0, 1, 或-1.

  2. \(A\)的转置矩阵\(A^T\)也是全幺模的.

    原因: 任何方阵的行列式和它转置的行列式都相等. 因此, \(A^T\)的所有方子矩阵的行列式也必定都在\(\{0, 1, -1\}\)这个集合里.

  3. 将单位矩阵\(I\)堆叠在\(A\)下方构成的矩阵\(\begin{pmatrix} A \\ I \end{pmatrix}\)也是全幺模的.

    原因: 这个新矩阵的任何方子矩阵的行列式都可以通过代数余子式展开(cofactor expansion)证明其值等于\(A\)某个子矩阵的行列式(或者为0, 1, -1).

  4. 将\(-A\)堆叠在\(A\)下方构成的矩阵\(\begin{pmatrix} A \\ -A \end{pmatrix}\)也是全幺模的.

    原因: 与上一条性质类似, 它的任何方子矩阵的行列式的值最终都取决于\(A\)的某个子矩阵的行列式, 因此也在\(\{0, 1, -1\}\)集合内.

两个重要推论

这些基本性质引出了两个非常强大的推论.

  1. 第一个推论: 保证"箱式约束"下的整数解

    如果\(A\)是一个TUM矩阵, 那么多面体\(\{x \in \mathbb{R}^n_+ : a \le Ax \le b, l \le x \le u\}\)对于任意整数向量\(a, b, l, u\)都是一个整多面体.

  2. 第二个推论: 保证原始-对偶问题的整数解

    如果\(A\)是TUM矩阵, 并且\(b\)和\(c\)是整数向量, 那么下面两个问题(原始问题和它的对偶问题)都有整数最优解:

    • 原始问题(Primal): \(\min \{c \cdot x : Ax \ge b, x \ge 0\}\)
    • 对偶问题(Dual): \(\max \{b \cdot y : A^T y \le c, y \ge 0\}\)

这个结论在网络流和组合优化等领域至关重要, 它意味着许多问题可以通过高效的线性规划算法求解, 并能直接得到我们想要的整数解.

判断是否为TUM的另一种方法

直接使用TUM的定义 (检查所有方子矩阵的行列式) 来证明一个矩阵是TUM通常非常困难和繁琐. 因此, 数学家们找到了一个等价的、在某些情况下更容易验证的性质, 这就是可均勻二着色(equitable bi-coloring).

可均勻二着色

  1. 二着色 (Bi-coloring): 将一个矩阵的所有列分成两组, 一组染成红色, 一组染成蓝色.
  2. 可均勻 (Equitable): 这种着色方案被称为"可均勻的", 如果对于矩阵的每一行, "红色"列元素之和与"蓝色"列元素之和的差最多为1. 数学表达为: 对任意一行\(i\), \(|\sum_{j \in \text{Red}} A_{ij} - \sum_{j \in \text{Blue}} A_{ij}| \le 1\).

TUM和着色的关系

定理6.3:

一个整数矩阵\(A\)是全幺模的, 当且仅当\(A\)的每一个由列组成子矩阵(column-induced submatrix)都存在一个可均勻二着色方案.

这个条件不仅要对矩阵\(A\)本身成立, 还必须对由\(A\)的任意几列构成的所有子矩阵都成立. 因为\(A\)是TUM当且仅当\(A^T\)是TUM, 所以这个定理有一个等价的"行版本": 对矩阵的行进行着色, 并检查每一列的和.

引理6.1:

二分图匹配(bipartite matching)问题的约束矩阵是全幺模的(totally unimodular). 这个矩阵具体来说就是二分图的关联矩阵(incidence matrix).

证明引理6.1

证明的核心是使用定理6.3的行版本: 对矩阵的行进行红蓝二着色, 然后去检查每一列的红色元素之和与蓝色元素之和的差是否不超过1. 如果满足条件, 那么矩阵就是TUM.

关联矩阵是啥

关联矩阵 (Incidence Matrix) 是一种用矩阵来描述一个图中顶点(vertices)和边(edges)之间连接关系的方式. 它是将一个图结构代数化的重要工具.

对于一个无向图, 它的关联矩阵\(A\)通常是这样构造的:

  1. 矩阵的行代表图中的每一个顶点.
  2. 矩阵的列代表图中的每一条边.
  3. 矩阵中的元素\(A_{ve}\) (第\(v\)行, 第\(e\)列) 的值定义如下:
    • 如果顶点\(v\)是边\(e\)的一个端点, 那么\(A_{ve} = 1\).
    • 否则, \(A_{ve} = 0\).

核心性质:

  • 这是一个只包含0和1的矩阵.
  • 每一列的和恰好是2 (因为一条边恰好连接两个顶点).
  • 每一行的和等于对应顶点的度(degree), 也就是连接到这个顶点的边的数量.

关联矩阵的例子

假设有一个三角形的图, 顶点是{1, 2, 3}, 边是{a, b, c}, 其中边a=(1,2), 边b=(2,3), 边c=(3,1). 它的关联矩阵就是:

\[ \begin{array}{c|ccc} & a & b & c \\ \hline 1 & 1 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 3 & 0 & 1 & 1 \end{array} \]

  1. 定义矩阵A的结构

    • 矩阵\(A\)是二分图的关联矩阵.
    • 矩阵的每一行对应图中的一个顶点.
    • 矩阵的每一列对应图中的一条边.
    • 每一列(每一条边)有且仅有两个值为1的元素, 分别对应这条边的两个端点. 该列的其他元素全为0.

  2. 提出着色方案

    • 二分图的定义是其所有顶点可以被分成两个集合(我们称之为"左岸"和"右岸"), 使得所有的边都只连接两个集合之间的顶点.
    • 证明利用了这个天然的划分来进行着色:
      • 如果一个顶点在左岸, 就把矩阵中它对应的行染成红色.
      • 如果一个顶点在右岸, 就把矩阵中它对应的行染成蓝色.

  3. 验证"可均勻"条件

    • 现在我们需要检查对于每一列, 这个着色方案是否是"可均勻的".
    • 让我们任意选取一列. 这一列代表图中的一条边, 比如边\((u, v)\).
    • 根据二分图的定义, 这条边的两个端点\(u\)和\(v\)必然一个在左岸, 另一个在右岸.
    • 这意味着, 在矩阵的这一列中, 两个值为1的元素, 一个必然落在红色行上, 另一个必然落在蓝色行上.
    • 那么对于这一列:
      • 所有红色元素的和 = 1.
      • 所有蓝色元素的和 = 1.
    • 两者之差为 \(|1 - 1| = 0\).
    • 这个差值\(0\)满足"最多为1"的条件.

  4. 得出结论

    • 由于我们选取的列是任意的, 所以这个结论对矩阵的所有列都成立.
    • 证明中还提到, 这个性质对于任何由行组成的子矩阵(row induced matrices)也成立. (因为即使去掉一些行, 剩下每一列中红色1和蓝色1的数量关系也不会破坏"差值最多为1"的规则).
    • 因为矩阵\(A\)满足了可均勻二着色的条件, 所以根据定理6.3, 矩阵\(A\)是全幺模的. 证明完毕.

引理6.2:网络循环流问题(circulation problem)的约束矩阵是全幺模的(totally unimodular).

什么是"循环流问题"?

  • 这是一个网络流问题. 想象一个管网, "流"在其中循环流动.
  • 核心约束是流量守恒: 对于网络中的每一个节点(vertex), 流入(in-flow)该节点的总流量必须等于流出(out-flow)该节点的总流量.
    • 数学表达为: \(\sum_{e \in \delta^{in}(u)} f_e = \sum_{e \in \delta^{out}(u)} f_e \quad \forall u \in V\).
  • 这种问题没有源点(source)或汇点(sink), 流量在网络中"凭空"产生或消失.

证明引理6.2

证明再次使用了可均勻二着色(equitable bi-coloring)的方法.

  1. 矩阵A的结构

    • 首先, 我们需要知道这个问题的约束矩阵是什么. 它实际上是这个有向图的关联矩阵(incidence matrix).
    • 矩阵的行对应图中的顶点.
    • 矩阵的列对应图中的有向边.
    • 对于一条从顶点\(u\)指向顶点\(v\)的边, 它对应的列有如下特点:
      • 在第\(u\)行 (流出的顶点) 的值为-1.
      • 在第\(v\)行 (流入的顶点) 的值为+1.
      • 在所有其他行都为0. (注意: +1和-1的位置取决于方程的写法, 但它们总是一个+1和一个-1)

  2. 着色方案 (非常巧妙)

    • 证明中提出的着色方案出人意料地简单:
    • 将所有的行都染成红色. (没有蓝色的行).

  3. 验证"可均勻"条件

    • 我们需要检查每一列, 看这个"全红"方案是否满足条件.
    • 我们任意选取一列. 这一列代表一条从\(u\)到\(v\)的边. 我们知道, 这一列里只有一个-1和一个+1, 其余都是0.
    • 现在计算这一列的红蓝元素和:
      • 所有红色元素的和 = \((-1) + (+1) = 0\).
      • 所有蓝色元素的和 = 0 (因为没有蓝色的行).
    • 两者之差为 \(|0 - 0| = 0\).
    • 这个差值\(0\)满足"最多为1"的条件.

  4. 得出结论

    • 这个结论对所有列都成立, 并且也容易验证它对所有由行组成的子矩阵都成立.
    • 因为矩阵\(A\)满足了可均勻二着色的条件, 所以根据定理6.3, 它是全幺模的.

重要意义: 这个引理是网络流理论的基石之一. 它保证了最基本的网络流问题(循环流)的约束矩阵是TUM, 这意味着只要流量的边界值是整数, 线性规划的解就一定是整数. 这个性质可以被扩展到最大流, 最小费用流等一系列核心网络优化问题上.

子集系统

一个子集系统由一个全集U和一个U的子集族\(\mathcal{I}构成,记为(U, \mathcal{I})\). \(\mathcal{I}\)中的集合被称为可行子集 (feasible subsets). 该系统必须满足一个关键性质: 如果一个集合\(S\)是可行的 (\(S \in \mathcal{I}\)), 那么\(S的任何子集T\) (T⊆S) 也必须是可行的 (T∈I). 这被称为向下封闭 (downward-closed)的性质.

子集系统的例子

假设你有一个背包, 全集U是所有可供选择的物品: U={水,食物,帐篷,地图}. 背包的容量有限, 只能装下特定组合的物品. 我们把所有能装进背包的物品组合定义为集合族\(\mathcal{I}\). 假设\(\mathcal{I} = {\emptyset, {\text{水}}, {\text{食物}}, {\text{地图}}, {\text{水}, \text{食物}}, {\text{水}, \text{地图}}}\). 那么, {水,食物} 就是一个可行子集, 因为它在\(\mathcal{I}\)中, 意味着这个组合能装进背包. 而子集\({\text{水}, \text{帐篷}}\) 不是一个可行子集, 因为它不在\(\mathcal{I}\)中 (可能因为它们一起太重了, 超出了背包容量).

给定一个成本函数\(c\), 为\(U\)中的每个元素赋予一个非负成本. 目标是找到一个可行子集\(S \in \mathcal{I}\), 使得该子集中所有元素的成本之和\(c(S)\)最大.

\[ \begin{aligned} \text{maximize} \quad & c(S) \\ \text{subject to} \quad & S \in \mathcal{I} \end{aligned} \]

定义6.3秩函数 (Rank Function):

对于\(U\)的任何子集\(S\) (无论\(S\)是否可行), 其秩函数\(r(S)\)被定义为包含在\(S\)内部的最大可行子集的大小 (即元素的数量).

\[ r(S) = \max_{T \subseteq S, T \in \mathcal{I}} |T| \]

上述优化问题可以被 formulate为一个整数规划问题.

  • 决策变量: 为每个元素\(j \in U\)引入一个二进制变量\(x_j\). 如果\(x_j=1\)则表示选择元素\(j\), \(x_j=0\)表示不选择.
  • 目标函数: 最大化总成本 \(\sum_{j \in U} c_j x_j\).
  • 约束条件:
    1. \(\sum_{j \in S} x_j \le r(S), \forall S \subseteq U\): 对于\(U\)的任何子集\(S\), 我们从中选择的元素总数不能超过\(S\)的秩\(r(S)\). 这是核心约束, 它保证了最终选出的集合是可行的.
    2. \(x_j \in \{0, 1\}, \forall j \in U\): 决策变量为0或1.