组合优化和整数规划应用研究与软件实现关于分支定界法的思考 (3)
于一组等式和不等式条件的最优化问题。许多经济、管理、交通、通信和工程中
的最优化问题都可以用整数规划来建模。
整数规划的历史可以追溯到 20 世纪 50 年代，运筹学创始人和线性规划单纯
型算法发明者 Dantzig 首先发现可以用 0-1 变量来刻画最优化模型中的固定费用、
变量上界、非凸分片线性函数等。他和Fulkerson及Johnson对旅行售货员问题（TSP）
的研究成为后来的分支——割方法和现代混合整数规划算法的开端。1958 年，
Gomory发现了第一个一般线性整数规划的收敛算法——割平面方法。随着整数规
划理论和算法的发展，整数规划已成为最广泛的最优化方法之一，特别是近年来
整数规划算法技术和软件系统（如 CPLEX）的发展和推广，整数规划在生产企业、
服务、运营管理、交通、通信等领域得到了极大的应用和发展。
整数规划(IP)和混合整数规划(MIP)问题是当今国际上最优决策与应用领域里
的一个极为重要的分支[1~5]
，因此如何求解IP和MIP问题是一个重要的研究领域。由于问题的可行解区域为离散点，所以一般不能用连续区域的求解算法，而只能
用特殊方法求解，因此这方面的研究非常困难。随着计算技术的快速发展，人们
已研究出许多快速求解非整数规划的算法，如变尺度法、内点法、罚函数法、信
赖域法等[1]
，这些算法具有良好的收敛性和收敛速度快等特点，可用于大规模问
题的求解，但遗憾的是不能将这些方法用于求解 IP 和MIP 问题。然而，如果我们
能将IP和MIP转化成等价的非整数规划问题(NIP)，便可以使用这些方法来求解，
显然这是非常有意义的工作。如文献[4]对0-1 整数规划的转化做了这方面的工作，
文献[5]研究了线性 0-1 整数规划的转化并给出了一个代数求解算法，但这方面研
究国内外还很少，并未引起人们的重视。
1.2.2整数规划问题的挑战性[6]
很多整数规划问题看上去很简单，数学模型也不复杂，如 0-1 背包问题，最
大割问题等，但求解这类问题其实非常困难。绝大部分整数规划问题的可行域都
只有有限多个可行点，一个简单幼稚的想法是枚举所有的可行点。设X = {0,1}�是
某问题的可行域，计算每个可行点的目标函数值所需的基本运算次数是常数。假
设有一个超级计算机，其每秒基本运算次数是 1 亿次。则计算机通过枚举 X 计算
问题的最优解所需时间是下列时间的常数倍：
n = 30, |X| = 230 ≈ 109, 10s
n = 60, |X| = 260 ≈ 1018, 360y
n = 100, |X| = 2100 ≈ 1030, 4 × 1014y
我们看到，文数n 每增加1，则可行点个数增加 1倍，即可行点的个数随着 n
成指数增长。故完全枚举法只适用于文数很小的问题，对一般整数规划问题是行
不通的。大部分整数规划问题的困难在于：我们本质上只能使用枚举法或隐枚举
法的思想来求解问题的最优解，故当问题的规模越来越大时，算法的计算时间急
剧增加。一个朴素的想法是“四舍五入”：求解相应的连续优化问题（丢掉整数约
束），然后对求得的解进行四舍五入，得到一个整数解。这个方法有两个问题：（1）
一般很难通过四舍五入得到一个满足约束条件的可行解；（2）即使求得一个可行
解，其质量往往很差，即可能离最优解的距离很远，甚至和随机产生的可行解差
不多。
尽管整数规划的研究有了很大的进展，许多原来不能解决的大规模整数规划
问题现在可以在合理的时间内使用新的算法和更快速的计算机解决。然而，由于