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

基于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.Asurveyofcomputationa