(A) linear programming based ant colony optimization method for the maximum independent set problem

Abstract

Ant colony optimization is a metaheuristic developed for solving many difficult combinatorial optimization problems. In this thesis, the ant colony optimization method is modified for solving the maximum independent set problem. We propose a new approach combining linear programming with the ant colony optimization method to define the local information. The experiments on instances from the discrete mathematics and computer science benchmark set show that the suggested method is comparable with the previous ant colony optimization algorithms. For the maximum weighted independent set problem, we compare the results solved by CPLEX with those solved by our method.