基于SDP松弛的整數(shù)規(guī)劃凸化方法研究的開題報(bào)告

基于SDP松弛的整數(shù)規(guī)劃凸化方法研究的開題報(bào)告一、選題背景整數(shù)規(guī)劃問題是數(shù)學(xué)規(guī)劃中的重要問題之一，應(yīng)用廣泛。但一般情況下，整數(shù)規(guī)劃問題是NP難問題，既難以求解。為了解決該類問題，以往多采用凸化方法或者割平面算法等，但這些方法都存在局限性，無(wú)法適用于所有情況。為了進(jìn)一步提高整數(shù)規(guī)劃問題的求解效率，近年來出現(xiàn)了基于松弛的凸化方法，并且有一定的應(yīng)用前景。SDP（SemidefiniteProgramming)松弛是其中比較常見的一種。本文將從該方法出發(fā)，對(duì)其原理和應(yīng)用展開研究。二、研究目的和意義本文旨在研究基于SDP松弛的整數(shù)規(guī)劃凸化方法，探討其原理、特點(diǎn)、優(yōu)缺點(diǎn)及應(yīng)用范圍。并且通過該方法，嘗試求解一些實(shí)際問題，以驗(yàn)證其解決復(fù)雜問題的能力。本研究成果可以為整數(shù)規(guī)劃求解問題提供新思路和方法，為工業(yè)生產(chǎn)、貨物配送等方面的優(yōu)化提供一定的理論和方法指導(dǎo)。三、研究?jī)?nèi)容和方法（1）了解SDP松弛的基本原理和特點(diǎn)，對(duì)其進(jìn)行歸納總結(jié)和分析比較。（2）研究SDP松弛方法在整數(shù)規(guī)劃中的應(yīng)用，包括SDP松弛模型的建立、求解方法及其正確性證明等。（3）以一些典型實(shí)際問題為例，應(yīng)用研究所得方法來解決整數(shù)規(guī)劃問題。（4）通過仿真實(shí)驗(yàn)等方法，對(duì)所得結(jié)果進(jìn)行分析和評(píng)價(jià)。四、預(yù)期結(jié)果和進(jìn)展（1）研究SDP松弛方法在解決整數(shù)規(guī)劃問題方面的有效性、實(shí)用性和性能優(yōu)劣。（2）得到應(yīng)用該方法來解決一些實(shí)際問題的經(jīng)驗(yàn)及可行方案。（3）論文撰寫及發(fā)表。五、可行性分析SDP松弛方法是已經(jīng)研究并掌握的一種數(shù)學(xué)方法，而整數(shù)規(guī)劃問題又是實(shí)際應(yīng)用中經(jīng)常遇到的問題，本研究的可行性較高。此外，本人在數(shù)學(xué)模型和算法分析方面有一定的能力和經(jīng)驗(yàn)，能夠從理論和實(shí)踐兩方面，探索和分析相關(guān)問題。六、進(jìn)度計(jì)劃第一周：收集整數(shù)規(guī)劃的相關(guān)文獻(xiàn)，了解SDP松弛方法第二周：學(xué)習(xí)整數(shù)規(guī)劃和SDP松弛的基本知識(shí)，總結(jié)分類第三周：研究SDP松弛方法在整數(shù)規(guī)劃中的具體應(yīng)用第四周：以典型問題為例，應(yīng)用所學(xué)方法進(jìn)行求解第五周：對(duì)結(jié)果進(jìn)行仿真分析，并撰寫論文第六周：繼續(xù)完善論文，準(zhǔn)備答辯七、參考文獻(xiàn)[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