非线性整数规划问题的若干新算法

摘要

整数规划问题是指在一些等式约束、不等式约束和整数变量的限制下，最小化或最大化一个目标函数的优化问题。如果问题中的所有函数都是线性的，那就是线性整数规划问题。否则，就称之为非线性整数规划问题。研究整数规划的主要任务就是要设计一些有效算法来解决各种涉及整数变量的实际问题。随着解决线性整数规划问题的一系列高效算法和软件的发展，再加上高速计算机的发明，线性整数规划已经成为解决各个领域实际问题的一个重要工具。然而，由于目标函数的非线性性或者约束函数的非线性性，使得应用领域中的许多实际问题，不能用一个线性整数规划问题来表示，甚至也不能用一个线性整数规划问题来充分逼近。近30年来，人们在求解非线性整数规划问题方面作出了很大努力，并且取得了很大进展。与线性整数规划和非线性连续优化不同的是，非线性整数规划几乎没有一种能应用广泛的有效算法，针对不同结构和特性的问题所设计的算法有时差异会很大。在这一点非线性整数规划与组合优化很类似。本文就三类不同的非线性整数规划问题给出了几种有效的精确算法。 全文共分五章，每章都有详细的数值例子和图形说明，而且还包含大量的计算实验，并且以表格的形式给出数值计算结果。 第一章介绍了非线性整数规划问题的发展背景，并且给出几个非线性整数规划问题在不同应用领域的实际模型，问题涉及分层抽样的最优样本配置问题和制造业中的容量计划问题等。 第二章研究了一类带有单个线性约束的凹背包问题。我们对这类问题提出了一种有效的精确算法。该算法利用线性函数来下逼近目标函数，通过求解松弛后的线性规划问题得到问题的下界和上界。然后运用区域分割来消除对偶间隙。对每个子问题重复上述过程，下界在迭代过程中不断更新。该算法经过有限步迭代即可找到原问题的最优解。数值结果表明该算法可以计算大规模的凹背包问题，变量个数可达1200个整数变量。我们还将算法与现有的其它算法进行了比较，比较结果表明我们所提出的算法能更有效地解决凹背包问题。 第三章针对二次目标函数的可分离非线性整数规划问题，提出了一种收敛的拉格朗日和等值面切割法。该算法把拉格朗日对偶方法和一种新颖的等值面切割法有效地结合起来。在算法的迭代过程中，拉格朗日对偶法用来产生问题的下界和上界，等值面切割法用来减小对偶间隙。我们首先给出单约束问题的算法，然后将其推广到多约束情形和目标函数是不定二次函数的情况。计算结果表明该算法是非常有效的，可以求解含有2000个整数变量的大规模二次可分离整数规划问题。与其它算法的比较结果也表明我们的算法是令人满意的。 第四章提出了一种拉格朗日和区域分割法用来求解多个线性约束、有界变量的不可分离凸背包问题。该算法利用拉格朗日分解对偶法产生问题的一个上界、一个下界、一个可行解和一个不可行解。得到的可行解和不可行解用来进行区域分割，这样可以逐步减小对偶间隙。上界和下界可以用来去掉一些不存在最优解的子问题。该算法经过有限步迭代可以找到问题的最优解。初步计算结果也在文中给出。 第五章总结了前面几章提出的算法。这些算法本质上都属于分枝定界法的框架。算法的创新性在于针对不同的非线性整数规划问题的特殊结构，导出了不同的有效界估计方法。与求解整数规划问题的传统分枝定界法相比较，本文提出的算法是用区域分割或等值面切割来产生子问题的，同时产生的子问题可能不止两个，而传统的分枝定界法在每个结点同时只产生两个子问题。

目录

文摘

英文文摘

原创性声明及本论文使用授权说明

第一章绪论

第二章凹背包问题的一种精确算法

第三章具有二次目标函数的可分离整数规划问题的一种收敛的拉格朗日等值面切割算法

§3.1拉格朗日对偶及对偶搜索

§ 3.2二次目标函数的等值面切割法

§ 3.3单约束问题的收敛拉格朗日等值面切割法

§ 3.4多个约束的情况

§ 3.5目标函数为不定二次函数的情况

§3.6数值结果

§ 3.7结论

第四章不可分离凸背包问题的拉格朗日分解和域分割法

第五章总结

参考文献

本文作者在攻读博士学位期间已发表和投稿的论文

致谢