最大团问题的一个线性混合整数规划模型
|
摘要
最大团问题(MCP)是图论中的一个传统问题,在很多领域都有广泛的应用.主要利用已有研究的相关结论,将(MCP)的二次0-1规划模型等价转化为一个线性混合整数规划模型,再利用计算线性混合整数规划的软件求解.通过对所构造实例的计算,验证了求解(MCP)方法的有效性.
The maximum clique problem(MCP)is a basic problem in graph theory,having wide applications in different fields.Based on the relevant valid conclusions,the quadratic 0-1programming model of the MCP was equivalently transformed into a linear mixed integer programming model.Then the linear mixed integer programming software was used to obtain the solution.The calculation of the constructed problem verified the validity of the method for solving the MCP.
The maximum clique problem(MCP)is a basic problem in graph theory,having wide applications in different fields.Based on the relevant valid conclusions,the quadratic 0-1programming model of the MCP was equivalently transformed into a linear mixed integer programming model.Then the linear mixed integer programming software was used to obtain the solution.The calculation of the constructed problem verified the validity of the method for solving the MCP.
引文
[1]Horst R,Pardlos P M,Thoai V.全局优化引论[M].黄红选译.北京:清华大学出版社,2003.
[2]Wood D R.An algorithm for Finding a maximum clique in a Graph[J].Operations Research Letters,1997,21:211-217.
[3]Tomita E,Seki T.An efficient branch-and-bound algorithm for finding a maximum clique[J].Lecture Notes in Computer Science,2003,2 631:278-289.
[4]Wanpracha C,Pardlos P M,Prokopyev O A.A new linearization technique for multi-quadratic 0-1programming problems[J].Operation Research Letters,2004,31:517-522.
[5]Adams W,Forrester R.A Simple Approach for Generating Concise Linear Representations of Mixed 0-1Polynomial Programs[J].Operations Research Letters,2005,33(1):55-61.
[6]Adams W P,Sherali H D.Linearization strategies for a class of 0-1mixed integer programming problems[J].Oper.Res.1990,2(38):217-226.
[7]Sherali H D,Smith J C.An improved linearization strategy for zero-one quadratic programming problems[J].Optimization Letters.2007,1:33-47.
[8]任燕,陈伟.对带有盒约束的二次整数规划的一种线性化方法[J].运筹学学报,2010,14(1):66-75.
[9]Gharibi W,Yong XIA.A tight linearization strategy for zero-one quadratic programming problems[J].International Journal of Computer Science Issues.2012,9:294-299.
[10]于泳海,王杉林.遗传算法与微粒群算法的比较[J].甘肃科学学报,2010,22(2):120-123.
[2]Wood D R.An algorithm for Finding a maximum clique in a Graph[J].Operations Research Letters,1997,21:211-217.
[3]Tomita E,Seki T.An efficient branch-and-bound algorithm for finding a maximum clique[J].Lecture Notes in Computer Science,2003,2 631:278-289.
[4]Wanpracha C,Pardlos P M,Prokopyev O A.A new linearization technique for multi-quadratic 0-1programming problems[J].Operation Research Letters,2004,31:517-522.
[5]Adams W,Forrester R.A Simple Approach for Generating Concise Linear Representations of Mixed 0-1Polynomial Programs[J].Operations Research Letters,2005,33(1):55-61.
[6]Adams W P,Sherali H D.Linearization strategies for a class of 0-1mixed integer programming problems[J].Oper.Res.1990,2(38):217-226.
[7]Sherali H D,Smith J C.An improved linearization strategy for zero-one quadratic programming problems[J].Optimization Letters.2007,1:33-47.
[8]任燕,陈伟.对带有盒约束的二次整数规划的一种线性化方法[J].运筹学学报,2010,14(1):66-75.
[9]Gharibi W,Yong XIA.A tight linearization strategy for zero-one quadratic programming problems[J].International Journal of Computer Science Issues.2012,9:294-299.
[10]于泳海,王杉林.遗传算法与微粒群算法的比较[J].甘肃科学学报,2010,22(2):120-123.