基于SDP松弛的整数规划凸化方法研究的开题报告.docx

基于SDP松弛的整数规划凸化方法研究的开题报告
一、选题背景
整数规划问题是数学规划中的重要问题之一，应用广泛。但一般情况下，整数规划问题是NP难问题，既难以求解。为了解决该类问题，以往多采用凸化方法或者割平面算法等，但这些方法都存在局限性，无法适用于所有情况。为了进一步提高整数规划问题的求解效率，近年来出现了基于松弛的凸化方法，并且有一定的应用前景。SDP（SemidefiniteProgramming)松弛是其中比较常见的一种。本文将从该方法出发，对其原理和应用展开研究。
二、研究目的和意义
本文旨在研究基于SDP松弛的整数规划凸化方法，探讨其原理、特点、优缺点及应用范围。并且通过该方法，尝试求解一些实际问题，以验证其解决复杂问题的能力。本研究成果可以为整数规划求解问题提供新思路和方法，为工业生产、货物配送等方面的优化提供一定的理论和方法指导。
三、研究内容和方法
（1）了解SDP松弛的基本原理和特点，对其进行归纳总结和分析比较。
（2）研究SDP松弛方法在整数规划中的应用，包括SDP松弛模型的建立、求解方法及其正确性证明等。
（3）以一些典型实际问题为例，应用研究所得方法来解决整数规划问题。
（4）通过仿真实验等方法，对所得结果进行分析和评价。
四、预期结果和进展
（1）研究SDP松弛方法在解决整数规划问题方面的有效性、实用性和性能优劣。
（2）得到应用该方法来解决一些实际问题的经验及可行方案。
（3）论文撰写及发表。
五、可行性分析
SDP松弛方法是已经研究并掌握的一种数学方法，而整数规划问题又是实际应用中经常遇到的问题，本研究的可行性较高。此外，本人在数学模型和算法分析方面有一定的能力和经验，能够从理论和实践两方面，探索和分析相关问题。
六、进度计划
第一周：收集整数规划的相关文献，了解SDP松弛方法
第二周：学习整数规划和SDP松弛的基本知识，总结分类
第三周：研究SDP松弛方法在整数规划中的具体应用
第四周：以典型问题为例，应用所学方法进行求解
第五周：对结果进行仿真分析，并撰写论文
第六周：继续完善论文，准备答辩
七、参考文献
[1]BarvinokA,HartiganJC,WeibelC.Convexbodiesassociatedwitharrangementsofhyperplanes.DiscreteComputGeom,2002,28(4):505-531.
[2]BarvinokA.Integerpointsinpolyhedra.EuropeanCongressofMathematics,VolI,2001:535-549.
[3]BarvinokA.Mixedvolumesandlatticepointsinrationalconvexpolytopes.Proc.Amer.Math.Soc.,2003,131(8):2295-2301.
[4]BeckA,BlekhermanG.HardnessofapproximateoptimainLasserrehierarchyofsemidefiniteprogrammingrelaxationsforgenericpolynomialoptimization.ConferenceonDecisionandControl,2004.
[5]BlondelVD,TsitsiklisJN.Asurveyofcomputationalcomplexityresultsinsystemsandcontrol.Automatica,2000,36(9):1249-1274.