电路二等分问题的强化半定规划松弛  

A Strengthened SDP Relaxation of the Circuit Bisection

作　　者：徐凤敏 刘三阳[1] 王燕军[3] 

机构地区：[1]西安电子科技大学数学系 [2]西安交通大学理学院,西安710049 [3]西安交通大学理学院

出　　处：《工程数学学报》2002年第2期69-74,共6页Chinese Journal of Engineering Mathematics

基　　金：陕西省自然科学基金项目 (99SL0 2 )

摘　　要：将表示电路的超图转化成带权值的无向图 ,从而将电路二等分问题转化成图的划分问题。图的划分问题存在已知的半定规划松弛 ,在此半定规划松弛基础上增加两个非线性结束 ,得到了强化半定规划松弛 ,定理和数值试验保证了强化半定规划松弛给出原问题一个更好的下界。The hypergraph denoting circuit is transformed into a weighted undirected graph, so the problem of circuit bisection is transformed into the graph partition problem. Since the graph partition problem has the well known SDP (semidefinite programming) relaxation, the strengthened SDP relaxation is achieved by an addition of two nonlinear constraints to SDP relaxation. Theory and numerical experiment ensure that the strengthened SDP relaxation gives the problem of circuit bisection a lower bound greater than exited lower bownds.

关 键 词：半定规划 电路二等分 松弛 VLSI 无向图 

分 类 号：O221.2[理学—运筹学与控制论] TN47[理学—数学]