基于线性规划的图最小带宽排序问题求解示例
问题描述
图最小带宽排序问题（Minimum Bandwidth Ordering Problem）是一个经典的组合优化问题，在图论和数值线性代数中都有重要应用。给定一个无向图 \(G = (V, E)\)，其中 \(V = \{1, 2, ..., n\}\) 是顶点集，\(E\) 是边集。我们需要找到一个顶点排列（排序）\(\pi: V \rightarrow \{1, 2, ..., n\}\)，使得所有边 \((u, v) \in E\) 在排列中的最大“拉伸”最小化。
形式化定义：
对于排列 \(\pi\)，边 \((u, v)\) 的带宽定义为 \(|\pi(u) - \pi(v)|\)。
整个图的带宽定义为 \(B(\pi) = \max_{(u, v) \in E} |\pi(u) - \pi(v)|\)。
目标是找到排列 \(\pi\) 最小化 \(B(\pi)\)。
线性规划建模思路
该问题本身是NP-hard，但可以通过整数线性规划（ILP）建模，并利用线性规划松弛来获得下界或启发式解。
核心思想：
- 用0-1变量表示每个顶点在每个位置上的分配关系。
- 用连续变量表示带宽值。
- 通过约束确保每个顶点恰好分配到一个位置，每个位置恰好分配一个顶点。
- 对每条边，约束其位置差的绝对值不超过带宽变量。
整数线性规划模型
决策变量
- \(x_{i,p} \in \{0,1\}\)：顶点 \(i\) 是否被分配到位置 \(p\)（1表示是，0表示否）。
- \(B \ge 0\)：连续变量，表示图的带宽。
目标函数
\[\min B \]
约束条件
- 每个顶点恰好一个位置：
\[ \sum_{p=1}^n x_{i,p} = 1, \quad \forall i \in V \]
- 每个位置恰好一个顶点：
\[ \sum_{i=1}^n x_{i,p} = 1, \quad \forall p = 1,\dots,n \]
- 带宽约束（直接建模绝对值较难，需线性化）：
对于每条边 \((i,j) \in E\)，我们希望 \(|\pi(i) - \pi(j)| \le B\)。
引入辅助变量 \(y_{i,j,p,q}\) 表示顶点 \(i\) 在位置 \(p\) 且顶点 \(j\) 在位置 \(q\)（这将导致变量过多）。
更实用的方法：利用位置变量线性表达式。
定义连续变量 \(p_i\) 表示顶点 \(i\) 的位置：
\[ p_i = \sum_{k=1}^n k \cdot x_{i,k}, \quad \forall i \in V \]
则约束变为：
\[ p_i - p_j \le B, \quad \forall (i,j) \in E \]
\[ p_j - p_i \le B, \quad \forall (i,j) \in E \]
这等价于 \(|p_i - p_j| \le B\)。
- 变量类型：
\[ x_{i,p} \in \{0,1\}, \quad B \ge 0, \quad p_i \ge 0 \]
线性规划松弛
将整数约束 \(x_{i,p} \in \{0,1\}\) 松弛为 \(0 \le x_{i,p} \le 1\)，得到线性规划（LP）松弛问题。
该LP松弛的最优值 \(B_{LP}^*\) 是原整数规划最优值 \(B_{IP}^*\) 的下界，即 \(B_{LP}^* \le B_{IP}^*\)。
求解步骤示例
实例
考虑一个小图：
\(V = \{1,2,3,4\}\)
\(E = \{(1,2), (2,3), (3,4), (1,4)\}\)（即一个4个顶点的环）
步骤1：建立LP松弛模型
变量：
\(x_{1,1}, x_{1,2}, x_{1,3}, x_{1,4}\) 表示顶点1在位置1~4。
类似定义 \(x_{2,p}, x_{3,p}, x_{4,p}\)。
\(p_1, p_2, p_3, p_4\) 为连续变量。
\(B\) 为带宽变量。
目标：最小化 \(B\)。
约束：
-
每个顶点一个位置：
\(x_{1,1} + x_{1,2} + x_{1,3} + x_{1,4} = 1\)
类似对顶点2,3,4。 -
每个位置一个顶点：
\(x_{1,1} + x_{2,1} + x_{3,1} + x_{4,1} = 1\)
类似对位置2,3,4。 -
位置变量定义：
\(p_1 = 1\cdot x_{1,1} + 2\cdot x_{1,2} + 3\cdot x_{1,3} + 4\cdot x_{1,4}\)
类似对 \(p_2, p_3, p_4\)。 -
带宽约束（对每条边）：
边(1,2)：\(p_1 - p_2 \le B\)，\(p_2 - p_1 \le B\)
边(2,3)：\(p_2 - p_3 \le B\)，\(p_3 - p_2 \le B\)
边(3,4)：\(p_3 - p_4 \le B\)，\(p_4 - p_3 \le B\)
边(1,4)：\(p_1 - p_4 \le B\)，\(p_4 - p_1 \le B\) -
变量范围：
\(0 \le x_{i,p} \le 1\)，\(B \ge 0\)，\(p_i \ge 0\)。
步骤2：求解LP松弛
使用单纯形法或内点法求解上述LP，得到：
最优目标值 \(B_{LP}^* = 1.5\)。
解可能不唯一，例如可能得到分数解：
\(x_{1,1} = 0.5, x_{1,4} = 0.5\)（顶点1一半在位置1，一半在位置4，这是分数解的特征）。
步骤3：获得整数解（启发式方法）
从LP松弛解中提取信息构造可行整数解。常用方法：
-
基于位置变量的舍入：
LP解给出 \(p_1, p_2, p_3, p_4\) 的值（可能是分数）。
按 \(p_i\) 值从小到大排序，得到顶点顺序。
例如：若 \(p_1 = 1.5, p_2 = 2.0, p_3 = 2.5, p_4 = 4.0\)，则排序为1,2,3,4。
计算该顺序的带宽：
边(1,2)位置差1，边(2,3)差1，边(3,4)差1，边(1,4)差3 → 带宽为3。
但这不是最优的（最优整数解带宽应为2，例如顺序1,2,4,3）。 -
迭代约束添加（分支定界）：
若需要精确解，可对分数变量分支（如强制 \(x_{1,1}=1\) 或 \(x_{1,1}=0\)），并求解子问题，最终得到整数最优解。
步骤4：验证最优性
对于本例，最优整数排列可以是 \(\pi = (1,2,4,3)\)：
位置：顶点1在1，顶点2在2，顶点4在3，顶点3在4。
边带宽：|1-2|=1，|2-4|=1，|4-3|=1，|1-3|=3。
最大带宽为3。
但更好的排列：\(\pi = (1,2,3,4)\) 带宽为3？检查环(1-2-3-4-1)：
|1-2|=1，|2-3|=1，|3-4|=1，|1-4|=3 → 带宽3。
最优排列：\(\pi = (1,2,4,3)\) 边(3,4)变成(3在4,4在3)：|3-4|=1，其他边：|1-2|=1，|2-4|=|2-3|=1，|1-4|=|1-3|=3？不对：顶点4在3，顶点3在4，所以边(3,4)连接位置3和4，差1；边(1,4)：位置1和3，差2；边(1,2)：差1；边(2,3)：位置2和4，差2。最大带宽为2。
因此最优整数带宽为2。
LP下界为1.5 < 2，表明下界紧密。
算法扩展
- 切割平面法：在LP松弛基础上添加有效不等式（如对称割、团割）加强下界。
- 启发式算法：利用LP解指导局部搜索或遗传算法。
- 近似算法：有基于Laplacian特征向量的谱排序方法，可提供理论保证。
总结
图最小带宽排序问题的线性规划建模提供了问题的下界和启发式信息。尽管求解整数解需要结合分支定界，但LP松弛在理论和实际中都是重要工具。此方法可推广到带宽最小化、波形松弛等实际应用。