高效的图染色近似型求解算法
|
摘要
图染色问题是一个典型的NP问题,求解图染色问题的方法主要分为完备型算法和近似型算法,完备型算法通过有序的遍历所有解空间来求解,近似型算法使用启发式策略选取有效的解空间来搜索进行求解,近似型算法由于其高效性被广泛使用。
图染色问题的研究重点是快速的选取结点进行有效的染色。论文通过将图染色问题转化成命题逻辑满足的问题,将命题逻辑满足问题中的概念和方法引入到图染色问题中,并将图染色问题转化后的逻辑表达式数值化,建立数值化的评价方法来求解。
在求解图染色的过程中,使用完全子图的特殊结构,将完全子图从原图中剥离出来,确定性的对图的完全子图进行染色,搜索余下图的可行解,使得图染色过程搜索的空间大幅度降低,减轻了算法的搜索负担。同时,将命题逻辑问题中下降变元的概念首次引入到图染色问题的求解中,通过定义图染色中的下降变元,加快了搜索有效解空间的速度,增强了算法的求解能力。在选取结点时,算法使用了次优先选择策略和噪音技术相结合的方法,优化了算法选取结点的能力,使算法搜索图中复杂结构的能力加强。
算法在对DIMACS等通用测试集中DSJC系列算例表现出色,在DSJC500结点即500以下结点的测试中,都能算出目前最好的值,在有结构的图中,尤其是完全子图较大的图中,算法的搜索效率好于目前其它算法。
Graph coloring problem is a typical NP problem, the current method of solving the Graph coloring problem can be divided into the complete search method and the incomplete search method. The complete search method is used for searching all the possible space of the problem to find the solution in a certain sequence, the incomplete search method is used to search the most effective space for finding the solution of the Graph coloring problem. For the high efficient of the incomplete algorithm, it is widely used .
The key point of graph coloring problem research is to find the suitable node coloring in a reasonable way. This paper transforms the graph coloring problem to Boolean satisfiability problem, using the measures and the concepts which used in the Boolean satisfiability for the graph coloring problem, make it into a numerical problem.
In the process of solving the graph coloring problem, this paper finding out the complete subgraph of the graph, then coloring the complete subgraph in a certain way and searching the solution of the problem in the remaining graph. This measure makes the searching space smaller and reducing the burden of the algorithm on search .Meanwhile the algorithm using the promising decreasing variable which defined in the Boolean satisfiability problem to solve the graph coloring problem. By defining the promising decreasing variable in this problem, it accelerated the speed of algorithm to find the solution. This algorithm using the union strategy which is combined of the second best strategy and the noise strategy, it enhances the ability of the algorithm, make searching in the complex structure easier.
This method of searching on graph coloring problem has good results in DIMACS, especially for DSJC. It can get the best records in the most examples. This algorithm performs better in the graph which has large scale complete subgraph.
图染色问题的研究重点是快速的选取结点进行有效的染色。论文通过将图染色问题转化成命题逻辑满足的问题,将命题逻辑满足问题中的概念和方法引入到图染色问题中,并将图染色问题转化后的逻辑表达式数值化,建立数值化的评价方法来求解。
在求解图染色的过程中,使用完全子图的特殊结构,将完全子图从原图中剥离出来,确定性的对图的完全子图进行染色,搜索余下图的可行解,使得图染色过程搜索的空间大幅度降低,减轻了算法的搜索负担。同时,将命题逻辑问题中下降变元的概念首次引入到图染色问题的求解中,通过定义图染色中的下降变元,加快了搜索有效解空间的速度,增强了算法的求解能力。在选取结点时,算法使用了次优先选择策略和噪音技术相结合的方法,优化了算法选取结点的能力,使算法搜索图中复杂结构的能力加强。
算法在对DIMACS等通用测试集中DSJC系列算例表现出色,在DSJC500结点即500以下结点的测试中,都能算出目前最好的值,在有结构的图中,尤其是完全子图较大的图中,算法的搜索效率好于目前其它算法。
Graph coloring problem is a typical NP problem, the current method of solving the Graph coloring problem can be divided into the complete search method and the incomplete search method. The complete search method is used for searching all the possible space of the problem to find the solution in a certain sequence, the incomplete search method is used to search the most effective space for finding the solution of the Graph coloring problem. For the high efficient of the incomplete algorithm, it is widely used .
The key point of graph coloring problem research is to find the suitable node coloring in a reasonable way. This paper transforms the graph coloring problem to Boolean satisfiability problem, using the measures and the concepts which used in the Boolean satisfiability for the graph coloring problem, make it into a numerical problem.
In the process of solving the graph coloring problem, this paper finding out the complete subgraph of the graph, then coloring the complete subgraph in a certain way and searching the solution of the problem in the remaining graph. This measure makes the searching space smaller and reducing the burden of the algorithm on search .Meanwhile the algorithm using the promising decreasing variable which defined in the Boolean satisfiability problem to solve the graph coloring problem. By defining the promising decreasing variable in this problem, it accelerated the speed of algorithm to find the solution. This algorithm using the union strategy which is combined of the second best strategy and the noise strategy, it enhances the ability of the algorithm, make searching in the complex structure easier.
This method of searching on graph coloring problem has good results in DIMACS, especially for DSJC. It can get the best records in the most examples. This algorithm performs better in the graph which has large scale complete subgraph.
引文
[1] D. Achlioptas, C. Gomes, H. Kautz, B. Selman. Generating satisfiable problem instances. Austin, AAAI-2000, 2000: 256–261.
[2] Bl¨ochliger, I., Zufferey. A graph coloring heuristic using partial solutions and areactive tabu scheme[N]. Computers and Operations Research 2008,35(3): 960–975.
[3] R. Dorne, J.K. Hao. A new genetic local search algorithm for graph coloring. Lecture Notes in Computer Science, 1998, 1498:745–754.
[4]黄文奇,金人超.求解SAT问题的拟物拟人算法–Solar.中国科学(E辑), 1998, 27(2): 179~186.
[5] L T Wille. Simulated annealing and the topology of the potential energy surface of Lennard-Jones clusters. Computational Materials Science , 2000, 17(2): 551~554.
[6] Holland J H. Adaptation in natural and artificial systems. MIT Press, 1975
[7] S A Cook. The complexity of theorem proving procedures. the Third Annual ACM Symposium on the Theory of Computing, 1971, 21(5): 151~158
[8] M.R Garey, D.S. Johnson, A guide to the theory of NP-completeness. Computers and intractability. San Francisco ,W.H. Freeman and Company, 1979.
[9] M. Chiarandini, T. St¨utzle. An application of iterated local search to graph coloring. Computational Symposium on Graph Coloring and its Generalizations, Ithaca, New York, USA, 2002: 112–125.
[10] C.M. Li, S. Gerard. On the limit of branching rules for hard random unsatisfiable 3-SAT. Discrete Applied Mathematics, 2003, 130(2): 277-290.
[11] C.M. Li, F. Manyà, J. Planes. Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers. The 11th International Conference on Principles and Practice of Constraint Programming (CP2005), Sitges, Spain, Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2005: 3709, 403-414.
[12] H. Lin, K. Su, C.M. Li. Within-problem learning for efficient lower bound computation in Max-SAT solving. The 23rd National Conference on Artificial Intelligence (AAAI2008), Chicago, AAAI Press, 2008: 351-356.
[13] C.M. Li, W.X. Wei, H. Zhang. Combining adaptive noise and look-ahead in localsearch for SAT.Trends in Constraint Programming, Hermes Science, 2007, 14:261-267,.
[14]黄文奇,许如初.支持求解圆形Packing问题的两个拟人策略.中国科学(A辑), 1999, 29(4):347~353
[15] C. Fleurent, J.A. Ferland. Object-oriented implementation of heuristic search methods for graph coloring, maximum clique and satisfiability, 1996, 26:619-652.
[16] C.M. Li, F. Manyà. MaxSAT, hard and soft constraints. Handbook of Satisfiability, A.Biere, H.v. Maaren, T. Walsh, eds. IOS Press , 2009,185(5): 613-631,
[17] C.M. Li. Equivalent literal propagation in the DLL procedure. Discrete Applied Mathematics, 2003, 130(2): 251-276.
[18] W.X. Wei, C.M. Li, H. Zhang. Switching among non-weighting, clause weighting, and variable weighting in local search for SAT. The 14th International Conference on Principles and Practice of Constraint Programming (CP2008), Sydney, Australia, Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2008, 5202: 313-326.
[19]金人超,黄文奇.并行计算:提高SAT问题求解效率的有效方法.中国科学(E辑).2000, 11(3): 398~400.
[20] C.M. Li, F. Manyà, J. Planes. New inference rules for Max-SAT. Journal of Artificial Intelligence Research, 2007,30: 321-359.
[21] C. Ansótegui, J. Larrubia, C.M. Li, F. Manyà. Exploiting multivalued knowledge in variable selection heuristics for SAT solvers. Annals of Mathematics and Atificial Itelligence, 2007,49: 191-205.
[22] P. Galinier, A. Hertz. A survey of local search methods for graph coloring, Computers and Operations Research,2006, 33(9):2547–2562.
[23] Chiarandini, M., St¨utzle, T.: An application of iterated local search to graph coloring. The Computational Symposium on Graph Coloring and its Generalizations, Ithaca, New York, USA, 2002:112–125
[24] Galinier, P., Hao, J.K. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 1999,3(4): 379–397
[25] Dorne, R., Hao, J.K. Tabu search for graph coloring, T-colorings and set Tcolorings. Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization,Kluwer, Dordrecht 1998(6):77-92
[26] L. Zhang, C.F. Madigan, M.H. Moskewicz, S. Malik,“Efficient conflict driven learning in a Boolean satisfiability solver”, ICCAD,2001: 279-285.
[27] C. Lucet, F. Mendes, A. Moukrim ,An exact method for graph coloring. Computers & Operations Research, 2006, 33(8): 2189-2207.
[28] S. R. Vegdahl , Using node merging to enhance graph coloring. In PLDI’99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, ACM Press, New York, NY, USA, 1999: 150-154.
[29] M. Chiarandini, I. Dumitrescu, T. Sttzle. Very large-scale neighborhood search:Overview and case studies on coloring problems. Hybrid Metaheuristics, Studies in Computational Intelligence, 2008, 114(1): 117-150.
[30] B. Gendron, A. Hertz, P. St-Louis . On edge orienting methods for graph coloring. Journal of combinatorial optimization, 2007,13(2): 163-178.
[31] Br′elaz, D. New methods to color the vertices of a graph. Communications of the ACM 22,1979 ,(4):251–256.
[32] L. Di Gaspero, A. Schaerf. EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software - Practice & Experience, 2003,33(8): 733-765.
[33] T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan. An ant-based algorithm for coloring graphs. Discrete Applied Mathematics, 2008 ,156(2): 190-200.7
[34] I. Dukanovic, F. Rendl. A semidefinite programming-based heuristic for graph coloring.Discrete Applied Mathematics, 2008,156(2): 180-189.
[35] Barnier N, Brisset P. Graph coloring for air traffic flow management. Ann Oper Res ,2004,130(1): 163-178.
[36] de Werra D. An introduction to timetabling. Eur J Oper Res ,1985,19(2): 151-162.
[37] Leighton F. A graph coloring algorithm for large scheduling problems. J Res Natl Bur Stand, 1979,84(6): 489-503.
[38] Lim A, Wang F. Robust Graph Coloring for Uncertain Supply Chain Manage- ment. The 38th Annual Hawaii International Conference on System Sciences-Track 3,2005, 3:81b.
[39] E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu. A graph-based hyperheuristic for timetabling problems, European Journal of Operational Research,2007,176:177–192.
[40] H. A. Peelle . Graph coloring in J: an introduction. The 2001 International Conference on APL: An Arrays Odyssey, Yale University, New Haven, Connecticut, USA, 2001:77-82.
[41] I. Blchliger, N. Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008,35(3): 960-975.
[42] M. Caramia, P. Dell’Olmo . Coloring graphs by iterated local search traversing feasible and infeasible solutions. Discrete Applied Mathematics, 2008,156(2): 201-217.
[43] M. A. Trick, H. Yildiz. A large neighborhood search heuristic for graph coloring. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science,2007, 4510 : 346-360.
[44] C. A. Glass, A. Prgel-Bennett. A polynomially searchable exponential neighbourhood for graph colouring. Journal of the Operational Research Society, 2005, 56(3):324-330.
[2] Bl¨ochliger, I., Zufferey. A graph coloring heuristic using partial solutions and areactive tabu scheme[N]. Computers and Operations Research 2008,35(3): 960–975.
[3] R. Dorne, J.K. Hao. A new genetic local search algorithm for graph coloring. Lecture Notes in Computer Science, 1998, 1498:745–754.
[4]黄文奇,金人超.求解SAT问题的拟物拟人算法–Solar.中国科学(E辑), 1998, 27(2): 179~186.
[5] L T Wille. Simulated annealing and the topology of the potential energy surface of Lennard-Jones clusters. Computational Materials Science , 2000, 17(2): 551~554.
[6] Holland J H. Adaptation in natural and artificial systems. MIT Press, 1975
[7] S A Cook. The complexity of theorem proving procedures. the Third Annual ACM Symposium on the Theory of Computing, 1971, 21(5): 151~158
[8] M.R Garey, D.S. Johnson, A guide to the theory of NP-completeness. Computers and intractability. San Francisco ,W.H. Freeman and Company, 1979.
[9] M. Chiarandini, T. St¨utzle. An application of iterated local search to graph coloring. Computational Symposium on Graph Coloring and its Generalizations, Ithaca, New York, USA, 2002: 112–125.
[10] C.M. Li, S. Gerard. On the limit of branching rules for hard random unsatisfiable 3-SAT. Discrete Applied Mathematics, 2003, 130(2): 277-290.
[11] C.M. Li, F. Manyà, J. Planes. Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers. The 11th International Conference on Principles and Practice of Constraint Programming (CP2005), Sitges, Spain, Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2005: 3709, 403-414.
[12] H. Lin, K. Su, C.M. Li. Within-problem learning for efficient lower bound computation in Max-SAT solving. The 23rd National Conference on Artificial Intelligence (AAAI2008), Chicago, AAAI Press, 2008: 351-356.
[13] C.M. Li, W.X. Wei, H. Zhang. Combining adaptive noise and look-ahead in localsearch for SAT.Trends in Constraint Programming, Hermes Science, 2007, 14:261-267,.
[14]黄文奇,许如初.支持求解圆形Packing问题的两个拟人策略.中国科学(A辑), 1999, 29(4):347~353
[15] C. Fleurent, J.A. Ferland. Object-oriented implementation of heuristic search methods for graph coloring, maximum clique and satisfiability, 1996, 26:619-652.
[16] C.M. Li, F. Manyà. MaxSAT, hard and soft constraints. Handbook of Satisfiability, A.Biere, H.v. Maaren, T. Walsh, eds. IOS Press , 2009,185(5): 613-631,
[17] C.M. Li. Equivalent literal propagation in the DLL procedure. Discrete Applied Mathematics, 2003, 130(2): 251-276.
[18] W.X. Wei, C.M. Li, H. Zhang. Switching among non-weighting, clause weighting, and variable weighting in local search for SAT. The 14th International Conference on Principles and Practice of Constraint Programming (CP2008), Sydney, Australia, Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2008, 5202: 313-326.
[19]金人超,黄文奇.并行计算:提高SAT问题求解效率的有效方法.中国科学(E辑).2000, 11(3): 398~400.
[20] C.M. Li, F. Manyà, J. Planes. New inference rules for Max-SAT. Journal of Artificial Intelligence Research, 2007,30: 321-359.
[21] C. Ansótegui, J. Larrubia, C.M. Li, F. Manyà. Exploiting multivalued knowledge in variable selection heuristics for SAT solvers. Annals of Mathematics and Atificial Itelligence, 2007,49: 191-205.
[22] P. Galinier, A. Hertz. A survey of local search methods for graph coloring, Computers and Operations Research,2006, 33(9):2547–2562.
[23] Chiarandini, M., St¨utzle, T.: An application of iterated local search to graph coloring. The Computational Symposium on Graph Coloring and its Generalizations, Ithaca, New York, USA, 2002:112–125
[24] Galinier, P., Hao, J.K. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization 1999,3(4): 379–397
[25] Dorne, R., Hao, J.K. Tabu search for graph coloring, T-colorings and set Tcolorings. Meta-Heuristics:Advances and Trends in Local Search Paradigms for Optimization,Kluwer, Dordrecht 1998(6):77-92
[26] L. Zhang, C.F. Madigan, M.H. Moskewicz, S. Malik,“Efficient conflict driven learning in a Boolean satisfiability solver”, ICCAD,2001: 279-285.
[27] C. Lucet, F. Mendes, A. Moukrim ,An exact method for graph coloring. Computers & Operations Research, 2006, 33(8): 2189-2207.
[28] S. R. Vegdahl , Using node merging to enhance graph coloring. In PLDI’99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, ACM Press, New York, NY, USA, 1999: 150-154.
[29] M. Chiarandini, I. Dumitrescu, T. Sttzle. Very large-scale neighborhood search:Overview and case studies on coloring problems. Hybrid Metaheuristics, Studies in Computational Intelligence, 2008, 114(1): 117-150.
[30] B. Gendron, A. Hertz, P. St-Louis . On edge orienting methods for graph coloring. Journal of combinatorial optimization, 2007,13(2): 163-178.
[31] Br′elaz, D. New methods to color the vertices of a graph. Communications of the ACM 22,1979 ,(4):251–256.
[32] L. Di Gaspero, A. Schaerf. EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software - Practice & Experience, 2003,33(8): 733-765.
[33] T. N. Bui, T. H. Nguyen, C. M. Patel, K.-A. T. Phan. An ant-based algorithm for coloring graphs. Discrete Applied Mathematics, 2008 ,156(2): 190-200.7
[34] I. Dukanovic, F. Rendl. A semidefinite programming-based heuristic for graph coloring.Discrete Applied Mathematics, 2008,156(2): 180-189.
[35] Barnier N, Brisset P. Graph coloring for air traffic flow management. Ann Oper Res ,2004,130(1): 163-178.
[36] de Werra D. An introduction to timetabling. Eur J Oper Res ,1985,19(2): 151-162.
[37] Leighton F. A graph coloring algorithm for large scheduling problems. J Res Natl Bur Stand, 1979,84(6): 489-503.
[38] Lim A, Wang F. Robust Graph Coloring for Uncertain Supply Chain Manage- ment. The 38th Annual Hawaii International Conference on System Sciences-Track 3,2005, 3:81b.
[39] E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu. A graph-based hyperheuristic for timetabling problems, European Journal of Operational Research,2007,176:177–192.
[40] H. A. Peelle . Graph coloring in J: an introduction. The 2001 International Conference on APL: An Arrays Odyssey, Yale University, New Haven, Connecticut, USA, 2001:77-82.
[41] I. Blchliger, N. Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008,35(3): 960-975.
[42] M. Caramia, P. Dell’Olmo . Coloring graphs by iterated local search traversing feasible and infeasible solutions. Discrete Applied Mathematics, 2008,156(2): 201-217.
[43] M. A. Trick, H. Yildiz. A large neighborhood search heuristic for graph coloring. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science,2007, 4510 : 346-360.
[44] C. A. Glass, A. Prgel-Bennett. A polynomially searchable exponential neighbourhood for graph colouring. Journal of the Operational Research Society, 2005, 56(3):324-330.