整数规划与半定规划松弛问题研究

### 整数规划与半定规划松弛问题研究 #### 1. 整数规划相关理论 在整数规划领域，有一个重要的定理证明与 3 - SAT 问题紧密相关。为了证明某个定理的 NP 难问题，采用了从 3 - SAT 问题进行多项式时间归约的方法。3 - SAT 问题是一个经典的 NP 完全问题。 ##### 1.1 证明思路 设 $\phi$ 是一个 3 - CNF 公式，将一个赋值编码到变量 $y$ 中。对于公式 $\phi$ 中的每个变量 $v_i$，都关联一个素数 $p_i$，使得 $y \bmod p_i$ 表示变量 $v_i$ 的布尔值，即通过辅助小装置（gadget）强制 $y \bmod p_i$ 始终在 $\{0, 1\}$ 中。对于公式 $\phi$ 中的每个子句 $C$，用 $\|C\|$ 表示与子句 $C$ 中出现的变量相关联的所有素数的乘积。根据中国剩余定理，在 $[\|C\|]$ 中有一个唯一的值与使子句 $C$ 为假的赋值相关联，需要禁止 $y \bmod \|C\|$ 取这个值，通过盒子约束（即向量 $l$ 和 $u$）来实现这一点。 例如，若 $\phi = (v_1 \vee \neg v_2 \vee v_3)$，且与这三个变量相关联的素数分别为 2、3 和 5，则 $\|(v_1 \vee \neg v_2 \vee v_3)\| = 30$。因为 $v_1 = v_3 = false$ 且 $v_2 = true$ 是使该子句为假的唯一赋值，所以 21 是 $y \bmod 30$ 的禁止值。最终，从 $\phi$ 构造的 SIP（整数规划问题）有可行解当且仅当 $\phi$ 有满足赋值。 ##### 1.2 具体构造 设 $\phi$ 是一个具有 $n'$ 个变量 $v_1, \cdots, v_{n'}$ 和 $m'$ 个子句 $C_1, \cdots, C_{m'}$ 的 3 - CNF 公式。定义一个 SIP，即向量 $b$、$l$、$u$ 和一个具有 $O((n' + m')^5)$ 行和列的矩阵 $A$，其解集非空当且仅当 $\phi$ 存在满足赋值。 将 SIP 的向量 $x$ 自然地拆分为与所寻求的满足赋值、变量和子句相关的子向量，即 $x = [y, x_1, \cdots, x_{n'}, z_1, \cdots, z_{m'}]$。 - **变量小装置（Variable Gadget）**：将 $x$ 的 $x_i = [x_{i0}, \cdots, x_{ip_i}]$ 部分与变量 $v_i$ 关联，并将 $v_i$ 的赋值绑定到 $y$。添加以下约束： - $x_{i1} = x_{i\ell}$，对于所有 $\ell \in [2 : p_i]$。 - $x_{i0} = y + \sum_{\ell = 1}^{p_i} x_{i\ell}$。 - 盒子约束：$-\infty \leq x_{i\ell} \leq \infty$，对于所有 $\ell \in [p_i]$；$0 \leq x_{i0} \leq 1$。 可以证明，对于给定的 $x_{i0}$ 和 $y$ 的值，当且仅当 $x_{i0} \equiv y \bmod p_i$ 时，才可以选择 $x_{i\ell}$（$\ell \in [p_i]$）的值使得上述约束满足。通过这个小装置，建立了 $y$ 与变量 $v_1, \cdots, v_{n'}$ 的真值赋值之间的直接对应关系。 - **子句小装置（Clause Gadget）**：设 $C_j$ 是一个包含变量 $v_e$、$v_f$、$v_g$ 的子句，定义 $\|C_j\|$ 为与子句 $C_j$ 中出现