组合优化和整数规划应用研究与软件实现关于分支定界法的思考 (4)
我们的数学工具的局限和对离散优化问题认识的不足，还有许多整数规划问题不
能得到很好的解决，特别是在实际应用中提出的很多整数规划问题的规模一般都
很大，直接利用现有的算法和软件求解往往是不可能的。这就促使人们研究有效
快速的近似算法或启发式算法以寻找问题的一个近似最优解或较好的可行解，如
近年来发展起来的基于半定规划的随机化算法和各种针对具体整数规划和组合优
化问题的近似算法。
1.2.3完备性理论[6]
整数规划问题属于 ƝƤ 难问题，定义及证明如下：
定义 1.1 对于问题P, Q ∈ ƝƤ，如果 P 中的实例可以在多项式时间内转化为 Q
的一个实例，则称P 多项式时间可化归到 Q，即 P 不比Q难，记为P ⊲ Q。 定义1.2 对于问题P ∈ ƝƤ，如果ƝƤ中所有的问题 Q都可多项式时间化归到 P，
则定义P 为ƝƤ完备问题，记为P ∈ ƝƤC。
定义1.3 若最优化问题相应的判定问题是ƝƤ完备的，则该最优化问题称为ƝƤ
难问题。
可满足性问题 给定N = {1,…, n}及 N 的 2m 个子集{��}�=1
在x ∈ {0,1}�使得
性质1.1 可满足性问题是一个ƝƤ完备问题。
性质1.2 假设问题P, Q ∈ ƝƤ。
(i) 若Q ∈ Ƥ且P 多项式时间可化归到 Q，则P ∈ Ƥ;
(ii) 若P ∈ ƝƤC且 P 多项式时间可化归到Q，则Q ∈ ƝƤC。
首先考虑 0-1线性整数规划问题，它的一个实例为
max{��