The Experts below are selected from a list of 30753 Experts worldwide ranked by ideXlab platform
Malek Mouhoub - One of the best experts on this subject based on the ideXlab platform.
-
a hierarchical parallel genetic approach for the Graph Coloring problem
Applied Intelligence, 2013Co-Authors: Reza Abbasian, Malek MouhoubAbstract:Graph Coloring Problems (GCPs) are constraint optimization problems with various applications including time tabling and frequency allocation. The GCP consists in finding the minimum number of colors for Coloring the Graph vertices such that adjacent vertices have distinct colors. We propose a hierarchical approach based on Parallel Genetic Algorithms (PGAs) to solve the GCP. We call this new approach Hierarchical PGAs (HPGAs). In addition, we have developed a new operator designed to improve PGAs when solving constraint optimization problems in general and GCPs in particular. We call this new operator Genetic Modification (GM). Using the properties of variables and their relations, GM generates good individuals at each iteration and inserts them into the PGA population in the hope of reaching the optimal solution sooner. In the case of the GCP, the GM operator is based on a novel Variable Ordering Algorithm (VOA) that we propose. Together with the new crossover and the estimator of the initial solution we have developed, GM allows our solving approach to converge towards the optimal solution sooner than the well known methods for solving the GCP, even for hard instances. This was indeed clearly demonstrated by the experiments we conducted on the GCP instances taken from the well known DIMACS website.
-
an efficient hierarchical parallel genetic algorithm for Graph Coloring problem
Genetic and Evolutionary Computation Conference, 2011Co-Authors: Reza Abbasian, Malek MouhoubAbstract:Graph Coloring problems (GCPs) are constraint optimization problems with various applications including scheduling, time tabling, and frequency allocation. The GCP consists in finding the minimum number of colors for Coloring the Graph vertices such that adjacent vertices have distinct colors. We propose a parallel approach based on Hierarchical Parallel Genetic Algorithms (HPGAs) to solve the GCP. We also propose a new extension to PGA, that is Genetic Modification (GM) operator designed for solving constraint optimization problems by taking advantage of the properties between variables and their relations. Our proposed GM for solving the GCP is based on a novel Variable Ordering Algorithm (VOA). In order to evaluate the performance of our new approach, we have conducted several experiments on GCP instances taken from the well known DIMACS website. The results show that the proposed approach has a high performance in time and quality of the solution returned in solving Graph Coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.
Caner Z Taskin - One of the best experts on this subject based on the ideXlab platform.
-
an exact cutting plane algorithm to solve the selective Graph Coloring problem in perfect Graphs
European Journal of Operational Research, 2021Co-Authors: Oylum Seker, Tuna Ekim, Caner Z TaskinAbstract:Abstract We consider the selective Graph Coloring problem, which is a generalization of the classical Graph Coloring problem. Given a Graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective Graph Coloring in perfect Graphs. Since there exists no suite of perfect Graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect Graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on Graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem.
-
an exact cutting plane algorithm to solve the selective Graph Coloring problem in perfect Graphs
arXiv: Data Structures and Algorithms, 2018Co-Authors: Oylum Seker, Tuna Ekim, Caner Z TaskinAbstract:Graph Coloring is the problem of assigning a minimum number of colors to all vertices of a Graph in such a way that no two adjacent vertices share the same color. The Selective Graph Coloring Problem is a generalization of the classical Graph Coloring problem. Given a Graph with a partition of its vertex set into clusters, the aim of the selective Graph Coloring problem is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors necessary to color the vertices in the selection is minimized. This study focuses on an exact cutting plane algorithm for selective Coloring in perfect Graphs, where the selective Coloring problem is known to be NP-hard. Since there exists no suite of perfect Graph instances to the best of our knowledge, we also propose an algorithm to randomly generate perfect Graphs and provide a large collection of instances available online. We test our method on Graphs with different size and densities, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the art algorithm from the literature. Our computational experiments indicate that our approach significantly improves the solution performance.
Reza Abbasian - One of the best experts on this subject based on the ideXlab platform.
-
a hierarchical parallel genetic approach for the Graph Coloring problem
Applied Intelligence, 2013Co-Authors: Reza Abbasian, Malek MouhoubAbstract:Graph Coloring Problems (GCPs) are constraint optimization problems with various applications including time tabling and frequency allocation. The GCP consists in finding the minimum number of colors for Coloring the Graph vertices such that adjacent vertices have distinct colors. We propose a hierarchical approach based on Parallel Genetic Algorithms (PGAs) to solve the GCP. We call this new approach Hierarchical PGAs (HPGAs). In addition, we have developed a new operator designed to improve PGAs when solving constraint optimization problems in general and GCPs in particular. We call this new operator Genetic Modification (GM). Using the properties of variables and their relations, GM generates good individuals at each iteration and inserts them into the PGA population in the hope of reaching the optimal solution sooner. In the case of the GCP, the GM operator is based on a novel Variable Ordering Algorithm (VOA) that we propose. Together with the new crossover and the estimator of the initial solution we have developed, GM allows our solving approach to converge towards the optimal solution sooner than the well known methods for solving the GCP, even for hard instances. This was indeed clearly demonstrated by the experiments we conducted on the GCP instances taken from the well known DIMACS website.
-
an efficient hierarchical parallel genetic algorithm for Graph Coloring problem
Genetic and Evolutionary Computation Conference, 2011Co-Authors: Reza Abbasian, Malek MouhoubAbstract:Graph Coloring problems (GCPs) are constraint optimization problems with various applications including scheduling, time tabling, and frequency allocation. The GCP consists in finding the minimum number of colors for Coloring the Graph vertices such that adjacent vertices have distinct colors. We propose a parallel approach based on Hierarchical Parallel Genetic Algorithms (HPGAs) to solve the GCP. We also propose a new extension to PGA, that is Genetic Modification (GM) operator designed for solving constraint optimization problems by taking advantage of the properties between variables and their relations. Our proposed GM for solving the GCP is based on a novel Variable Ordering Algorithm (VOA). In order to evaluate the performance of our new approach, we have conducted several experiments on GCP instances taken from the well known DIMACS website. The results show that the proposed approach has a high performance in time and quality of the solution returned in solving Graph Coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.
Oylum Seker - One of the best experts on this subject based on the ideXlab platform.
-
an exact cutting plane algorithm to solve the selective Graph Coloring problem in perfect Graphs
European Journal of Operational Research, 2021Co-Authors: Oylum Seker, Tuna Ekim, Caner Z TaskinAbstract:Abstract We consider the selective Graph Coloring problem, which is a generalization of the classical Graph Coloring problem. Given a Graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective Graph Coloring in perfect Graphs. Since there exists no suite of perfect Graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect Graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on Graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem.
-
an exact cutting plane algorithm to solve the selective Graph Coloring problem in perfect Graphs
arXiv: Data Structures and Algorithms, 2018Co-Authors: Oylum Seker, Tuna Ekim, Caner Z TaskinAbstract:Graph Coloring is the problem of assigning a minimum number of colors to all vertices of a Graph in such a way that no two adjacent vertices share the same color. The Selective Graph Coloring Problem is a generalization of the classical Graph Coloring problem. Given a Graph with a partition of its vertex set into clusters, the aim of the selective Graph Coloring problem is to pick exactly one vertex per cluster so that, among all possible selections, the number of colors necessary to color the vertices in the selection is minimized. This study focuses on an exact cutting plane algorithm for selective Coloring in perfect Graphs, where the selective Coloring problem is known to be NP-hard. Since there exists no suite of perfect Graph instances to the best of our knowledge, we also propose an algorithm to randomly generate perfect Graphs and provide a large collection of instances available online. We test our method on Graphs with different size and densities, present computational results and compare them with an integer programming formulation of the problem solved by CPLEX, and a state-of-the art algorithm from the literature. Our computational experiments indicate that our approach significantly improves the solution performance.
Rongjian Chen - One of the best experts on this subject based on the ideXlab platform.
-
mtpso algorithm for solving planar Graph Coloring problem
Expert Systems With Applications, 2011Co-Authors: Shi-jinn Horng, Yuhrau Wang, Muhammad Khurram Khan, Rongjian ChenAbstract:Research highlights? A modified turbulent particle swarm optimization (MTPSO) model is proposed to solve the planar Graph. ? MTPSO combines walking one strategy, assessment strategy and turbulent strategy. ? MTPSO can solve the four-colors problem efficiently and accurately. In this paper, we proposed a modified turbulent particle swarm optimization (named MTPSO) model for solving planar Graph Coloring problem based on particle swarm optimization. The proposed model is consisting of the walking one strategy, assessment strategy and turbulent strategy. The proposed MTPSO model can solve the planar Graph Coloring problem using four-colors more efficiently and accurately. Compared to the results shown in Cui et al. (2008), not only the experimental results of the proposed model can get smaller average iterations but can get higher correction Coloring rate when the number of nodes is greater than 30.
