基于SDP松弛的整数规划凸化方法研究

摘要

整数规划是一类重要的最优化问题.许多经济、管理、交通和通信中的最优化问题都可以用整数规划来建模.特别是基于分枝定界和各种松弛技术的算法己日趋成熟并开发为各种优化建模和算法商业软件，使整数规划在学术界和工业界得到了广泛的应用.近年来，锥优化方法特别是半定规划多项式时间算法的发展为处理NP-难整数规划问题提供了新的思路和方法，特别是，二次0-1规划和多项式规划领域近年来取得了很大进展，是国际优化领域的研究热点。
　　 本文主要考虑三类整数规划问题：二次0-1背包问题(QKP)，带有概率约束的二次0-1背包问题(CKQP)，无约束0-1多项式问题(0-1UPP).二次0-1背包问题是经典的NP-难问题，其在整数规划和组合优化中有重要的应用，许多复杂的整数规划问题的子问题都可以归结为背包问题模型；概率约束二次0-1背包问题是近年来国际优化的研究热点之一，其容量约束中的系数向量是一个随机向量，与确定性优化问题不同的是，该约束条件要求以一定概率(置信度)成立，由于这类问题的可行域具有高度离散和非凸性，设计求解这类问题的算法具有挑战性。无约束0-1多项式问题是近年来备受关注的一类非线性整数规划问题，利用代数方面的一些深刻成果，多项式优化的理论研究近年来取得了不少突破，但在算法研究方面仍然面临许多问题，有待进一步解决。
　　 本文以半定规划(SDP)方法为工具，对上述三类整数规划问题进行了系统的研究.对二次0-1背包问题和概率约束的二次0-1背包问题分别提出了更有效的凸化和模型重构(reformulation)方法，新的凸化方法能给出连续松弛界更紧的重构问题，从而利用分枝定界算法能更有效求解问题.对于无约束0-1多项式问题，本文给出了新的构造SDP松弛问题的方法，并比较了经典的线性松弛和其它SDP之间的关系，这为设计0-1多项式问题的近似算法提供了理论基础。
　　 本文第一章简单介绍了问题的背景、研究动机和主要结果.第二章详细概述了文献中关于三类整数规划问题的松弛界和精确解方法的研究现状和进展。本文的主要结果在第三至第五章给出，第六章是论文总结和研究展望。
　　 在第三章中，我们给出了0-1二次背包问题的一种新的凸化和模型重构方法，该方法首先对目标函数进行矩阵分解，然后对{0，1}n上的非凸二次项进行分段线性表示.证明了新的凸化方法能给出连续松弛界更紧的重构问题，并证明求解新的重构问题中的最优参数等价于解一个SDP问题.我们将新的凸化方法推广到带有基数约束(k-item)的二次0-1背包问题.我们对文献中经典的二次0-1背包测试问题，从计算时间，节点数和算法终止时的相对误差等三方面比较了利用分枝定界算法CPLEX求解新的重构问题的表现，计算结果表明了新的重构问题能大大提高分枝定界算法的计算效率。
　　 在第四章中，我们考虑了带概率约束的0-1二次背包问题，该问题容量约束中的系数是服从有限离散分布的随机变量.在引入新的整数变量后，概率约束的二次0-1背包问题可以等价地化为一个0-1混合整数规划模型.我们对该模型提出了一种新的凸化和模型重构方法，证明了重构模型的连续松弛比对角扰动方法的连续松弛更紧.我们将该凸化重构方法推广到带有基数约束(k-item)的概率约束二次0-1背包问题.数值试验表明，新的凸化重构方法能使分枝定界算法更有效地求解问题。
　　 在第五章中，我们考虑了无约束0-1多项式优化问题，利用矩阵分解和多项式平方和(SOS)逼近的思想，我们得到了无约束0-1多项式问题的一种新的SDP松弛，证明了该SDP松弛产生的界比经典线性松弛产生的界更紧.我们还讨论了从直接提升(lift)的角度以及利用有效不等式、拉格朗日对偶和SOS松弛方法构造SDP松弛的方法，并且指出该方法给出的SDP问题与Lasserre体系的SDP松弛问题是一致的。