运筹学

独立系统(Independence system)：对一个有限基础集V，一个集族 $\mathcal V\subseteq 2^V$ 是一个独立系统如果 $\mathcal F$ 满足如下条件：

• $\emptyset\in \mathcal F$
• 若 $F'\subseteq F\in \mathcal F$ ，则$F'\in \mathcal F$

$(V,\mathcal F,c)$ 的最大化问题：对一个独立系统 $(V,\mathcal F)$ 和一个目标函数向量 $\mathbf c\in \mathbb K_+^V$ ，求

$\max \left\{ \mathbf c(F)=\sum_{v\in F} c_v: F\in \mathcal I \right\}$

最大匹配问题(MMP)：给定图 $G=(V,E)$ ，求使 $|M|$ 最大的匹配 $M\subseteq E$ ，或对 $\mathbf w\in \mathbb R^E$ ，使权重 $\mathbf w(M)=\sum_{e\in M} w_e$ 最大的匹配

最大匹配问题是一个独立系统： $\max \left\{ \mathbf w(M)=\sum_{e\in M} w_e: M\in \mathcal M\right\}$

最大匹配问题是一个ILP：

$\max \sum_{e\in E} w_e x_e\\ s.t.\ \sum_{e\in \delta(v)} x_e\leq 1, \forall v\in V\\ x_e\in \{0,1\}, \forall e\in E$

最大稳定集问题(MSSP)：给定图 $G=(V,E)$ ，求使 $|S|$ 最大的稳定集 $S\subseteq V$ ，或对 $\mathbf w\in \mathbb R^E$ ，使权重 $\mathbf w(S)=\sum_{v\in S} w_v$ 最大的稳定集

最大稳定集问题是一个独立系统： $\max \left\{ \mathbf w(S)=\sum_{v\in S} w_v: S\in \mathcal S\right\}$

最大稳定集问题是一个ILP：

$\max \sum_{v\in V} w_v x_v\\ s.t.\ x_u+x_v\leq 1, \forall uv\in E\\ x_v\in \{0,1\}, \forall v\in V$

最小集合划分问题(MSPP)：给定有限基础集V和可行集组成的集族 $\mathcal F\subseteq 2^V$ ，求使 $|\mathcal P|$ 最小的V的划分 $\mathcal P\subseteq \mathcal F$ ，它是一个NP-hard问题

最小集合划分问题是一个ILP：

$\min \sum_{F\in \mathcal F}x_F\\ s.t.\ \sum_{F\ni i}x_F=1, \forall i\in V\\ x_F\in \{0,1\}, \forall F\in \mathcal F$

装箱问题(BPP)：给定基础集 $V=\{1,\cdots,n\}$ ，其中每个货物有权重 $\mathbf a\in \mathbb R_+^n$ ，箱子容量均为 $b\in \mathbb R_+, b\geq a_i,\forall i\in V$ ，求装箱需要的最少箱子数

装箱问题是一个MSPP

节点染色问题(NCP)：给图G=(V,E)染色使相邻节点颜色不同，并使用最少颜色

节点染色问题是一个ILP：

$\min \sum_{S\in \mathcal S}x_S\\ s.t.\ \sum_{S\ni i}x_S=1, \forall i\in V\\ x_S\in \{0,1\}, \forall S\in \mathcal S$

最小集合覆盖问题(MSCP)：给定有限基础集V和可行集组成的集族 $\mathcal F\subseteq 2^V$ ，求使 $|\mathcal C|$ 最小的V的覆盖 $\mathcal C\subseteq \mathcal F$

最小集合覆盖问题是一个ILP：

$\min \sum_{F\in \mathcal F}x_F\\ s.t.\ \sum_{F\ni i}x_F\geq1, \forall i\in V\\ x_F\in \{0,1\}, \forall F\in \mathcal F$

最小截线问题(MTP)：对 $(V,\mathcal F)$ 求基数最小的截线(transversal)。如果 $F',F\in \mathcal F,F'\subset F$ 则对任意截线 $T$ 有$T\cap F'\subset F$ ，因此只需考虑clutter $(V,\mathcal F)$ ，其中没有元素包含在另一个内。

最小截线问题是一个NP-hard问题

clutter矩阵： $M(\mathcal F)$ 由 $F\in\mathcal F$的关联向量作为行向量，是一个0/1矩阵

最小截线问题是一个ILP：

$\min \mathbf 1^\top x\\ s.t.\ M(\mathcal F)x\geq\mathbf 1\\ x\in \{0,1\}^V$

clutter $(V,\mathcal F)$ 可定义一个独立系统 $(V,\mathcal I)$ ， $\mathcal I=\{I\subseteq V:|I\cap F|\leq |F|-1,\forall F\in \mathcal F\}$

反过来一个独立系统 $(V,\mathcal I)$ 的circuits的集族 $\mathcal F=\{F\subseteq V: F\nsubseteq I, \forall I\in \mathcal I, F最小\}$ 可以定义一个clutter $(V,\mathcal F)$

等价关系：对仿射变换 $y=1-x$

$\min \mathbf 1^\top y\\ s.t.\ M(\mathcal F)y\geq\mathbf 1\\ y\in \{0,1\}^V$

和

$|V|-\max\mathbf 1^\top x\\ s.t.\ (x^F)^\top x\leq |F|-1,\forall F\in \mathcal F\\ x\in \{0,1\}^V$

等价。

理想表达式(Ideal formulation)：一个整数线性规划 $\max c^\top x, Ax\leq b, x\in \mathbb Z^n$ 是一个优化问题的理想表达式如果 $P(A,b)=\{x\in\mathbb R_+^n:Ax\leq b\}=conv\{x\in \mathbb Z^n_+:Ax\leq b\}$ ，即 $P(A,b)$ 只有整数极点

全单模(Total unimodualrity)：一个矩阵 $A\in \mathbb Z^{m\times n}$ 是全单模的，如果它的任意方子阵的行列式值属于集合 $\{-1,0,1\}$

定理： $P(A,b)=\{x\in \mathbb R_+^n:Ax\leq b\},\forall b\in \mathbb Z^m$ 是整的，当且仅当A是全单模的

定理：任意有向图的关联矩阵是全单模的

定理：最大流问题对整数容量有整数最优解

定理：最小割问题对整数向量有整数最优解

多边形表达式(Polyhedral formulation)的最大匹配问题：给定G=(V,E)和权重 $w\in \mathbb R_+^E$ ，求 $\max w^\top x, x\in Match(G)$ ，其中 $Match(G)=conv\{x^M\in\{0,1\}^E:M\subseteq E\ matching\}$ 是一个匹配多面体(polytope)。由松弛化得到 度约束多面体(degree constraint polytope)$DegM(G)=\{x\in[0,1]^E :\sum_{e\in\delta(v)}x_e\leq 1,\forall v\in V\}$

定理：矩阵 $M\in \mathbb Z^{m\times n}$ 是全单模的当且仅当任意子集 $J\subset\{1,\cdots,m\}$ 对应的行有二分集 $J_A\cup J_B=J$ ，使得对任意列 $i\in\{1,\dots,n\}$ ，有 $\sum_{j\in J_A} m_{ji}-\sum_{j\in J_B} m_{ji}\in\{-1,0,1\}$

定理：Match(G)=DegM(G)当且仅当G是二分的

定理：对任意图G=(V,E)，匹配多面体Match(G)包含所有满足度约束和奇数集(odd set)约束的 $x\in \mathbb R_+^E$ ，其中

• 度约束： $x(\delta(v))=\sum_{e\in\delta(v)} x_e \leq 1, \forall v\in V$
• 奇数集约束： $x(E(V'))=\sum_{e\in E(V')} x_e\leq \frac{|V'|-1}{2}, \forall V'\in \mathcal O$ 其中 $\mathcal O=\{V'\subseteq V:|V'|\geq 3, odd\}$ 表示奇数大小的节点集族， $E(V')$ 表示端点在V'内的边

因此有松弛化后的最大匹配问题的ILP形式：

$\max \sum_{e\in E} w_e x_e\\ s.t.\ x(\delta(v))=\sum_{e\in\delta(v)} x_e \leq 1, \forall v\in V\\ x(E(V'))=\sum_{e\in E(V')} x_e\leq \frac{|V'|-1}{2}, \forall V'\in \mathcal O\\ x_e\geq 0, \forall e\in E$

结论：存在 $O(\sqrt{|V|}\cdot |E|)$ 的解决最大基数匹配问题的组合算法，和 $O(|V|^3)$ 的解决最大权重匹配问题的组合算法

多边形表达式(Polyhedral formulation)的最大稳定集问题：给定G=(V,E)和权重 $w\in \mathbb R_+^V$ ，求 $\max w^\top x, x\in STAB(G)$ ，其中 $STAB(G)=conv\{x^S\in\{0,1\}^V:S\subseteq V\ stable\}$ 是一个稳定集多面体(polytope)。由松弛化得到 边约束稳定集多面体(edge constraint stable set polytope)$ESTAB(G)=\{x\in[0,1]^V : x_u+x_v\leq 1,\forall uv\in E\}$

定理：矩阵 $M\in \mathbb Z^{m\times n}$ 是全单模的当且仅当任意子集 $I\subset\{1,\cdots,n\}$ 对应的列有二分集 $I_A\cup I_B=I$ ，使得对任意列 $j\in\{1,\dots,m\}$ ，有 $\sum_{i\in I_A} m_{ji}-\sum_{i\in I_B} m_{ji}\in\{-1,0,1\}$

定理：STAB(G)=ESTAB(G)当且仅当G是二分的

定理：一个团Q和一个稳定集S至多有一个公共点

因此有团约束： $x(Q)=\sum_{v\in Q} x_v\leq 1, \forall Q\subseteq V是团$

松弛化后得到团约束稳定集多面体 $QSTAB(G)=\{x\in[0,1]^V :\sum_{v\in Q} x_v\leq 1,\forall Q\subseteq V是团\}$

定理：用 $\omega(G)$ 表示最大团大小， $\chi(G)$ 表示最小染色数，有 $\omega(G)\leq\chi(G)$

完美图：G是完美图当且仅当对G的任意诱导子图 $G'\subseteq G$ 有 $\omega(G')=\chi(G')$

定理：STAB(G)=QSTAB(G)当且仅当G是完美图

定理：对任意完美图，最大稳定集问题可以在多项式时间解决

截线问题的表达式：覆盖多边形(covering polyhedron) $Cov_I(A)=conv\{x\in \{0,1\}^V:Ax\geq \mathbf 1\}$ ，松弛化 $Cov(A)=\{x\in \mathbb R_+^V:Ax\geq \mathbf 1\}$ 是无界的，但是所有极点都在 $[0,1]^V$ 中。

理想cluter：一个clutter $\mathcal C$ 和clutter矩阵 $A=M(\mathcal C)$ 是理想的，如果松弛化Cov(A)有整数极点。阻碍子(blocker) $b(\mathcal C)=(V,\mathcal T)$ 是有 $\mathcal C$ 的最小截线作为超边的clutter

定理：一个clutter $\mathcal C$ 是理想的当且仅当它的阻碍子 $b(\mathcal C)$ 是理想的。Cov(M(C))是理想的当且仅当Cov(M(b(C)))是理想的

定理：有向图D中(s,t)路径的clutter DP(D)是理想的。有向图D中(s,t)割的clutter b(DP(D))是理想的

令 $\mathcal H=(E,\mathcal F)$ 为一个clutter， $\mathcal F $ 中两两不交的集合族是一个packing(matching)。最大packing的基数 $v(\mathcal H)$ 是最小截线的 $\tau(\mathcal H)$ 的下界。当 $v(\mathcal H)=\tau(\mathcal H)$ 时称这个clutter packs，此时对应的线性规划有整数最优解

定理：每个二分图都packs

定理：任意图G=(V,E)中，两两不交(s,t)路径的个数等于最小(s,t)割中的边数。令 $\mathcal P$ 为G中(s,t)路径的集族，超图 $P(G)=(E,\mathcal P)$ packs。

MFMC性质：令 $\mathcal C=(V,\mathcal E)$ 为一个clutter， $A=M(\mathcal C)$ 。若两个等价的线性规划

$\max \mathbf 1^\top y\\ s.t. A^\top y\leq w\\ y\geq 0$ 和

$\min w^\top x\\ Ax\geq \mathbf 1\\ x\geq 0$

对任意 $w\in\mathbb Z_+^V$ 有整数最优解，则 $\mathcal C$ 有MFMC性质

推论：MFMC性质可导出 $\mathcal C$ 是理想的且packs

推论：DP(D)有MFMC性质，b(DP(D))有MFMC性质

综上所述，以下情形下我们可以多项式时间内解决ILP

1. 原来的ILP表达式是理想的，P(A,b)是整的
2. 原表达式不理想，但是松弛化的约束系统容易找到
3. 一般情况下原表达式不理想，但是特殊情形下一些组合性质被满足了

增强表达式的方法：Cutting planes，Branch & Bound