Groupe d’études et de recherche en analyse des décisions


A Quadratic 0-1 Optimization Algorithm for the Maximum Clique and Stable Set Problems

, , et

It is well known that several combinatorial optimization problems can be nicely and readily modeled as an appropriate quadratic 0-1 function to be optimized. In this paper we present an algorithm for minimizing general quadratic 0-1 functions and, indirectly, any problem such as the maximum clique and stable set problems, which is reducible to this model. We also report on the computational experiments carried out on 44 DIMACS clique benchmark instances and 15 randomly generated clique instances with 90% density and up to 200 nodes. Ours is a general-purpose program that has proved to be effective in solving the maximum clique and stable set problems via quadratic 0-1 optimization.

, 37 pages