基于半定規(guī)劃的多約束圖劃分問(wèn)題

打開(kāi)文本圖片集

摘要：提出一種遞歸的二分算法 ， 用于求解帶頂點(diǎn)權(quán)重約束的圖劃分問(wèn)題.首先利用內(nèi)點(diǎn)法求解不加頂點(diǎn)權(quán)重約束的半定規(guī)劃松弛模型 ， 然后利用超平面舍入算法得到滿足頂點(diǎn)權(quán)重約束的初始可行解 ， 再進(jìn)一步設(shè)計(jì)啟發(fā)式算法對(duì)初始可行劃分進(jìn)行局部改進(jìn) ， 以得到更優(yōu)的劃分結(jié)果.實(shí)驗(yàn)結(jié)果表明 ， 所設(shè)計(jì)的算法可在較（剩余9897字）