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

G-2011-08

An Interior-Point Algorithm with Selective Addition of Inequalities for Solving Doubly Non-Negative Relaxations of Maximum-Stable-Set and Maximum-Clique Problems

, et

The maximum-stable-set and maximum-clique problems are operations research problems that arise in numerous areas such as social networking, electrical engineering, environmental forest planning, bioinformatics clustering and prediction, and computational chemistry. The doubly nonnegative relaxation is known to provide high-quality bounds on the size of the global optimal solution of both problems. However, it is an expensive conic optimization problem to solve in general. We propose an integrated interior-point cutting-plane method to efficiently handle the large number of nonnegativity constraints in the relaxation. The approach is based on a recent interior-point algorithm that selectively adds inequalities in a dynamic fashion. We present computational results showing the significant benefits of the integrated algorithm in comparison to a standard interior-point cutting-plane method.

, 21 pages

Ce cahier a été révisé en novembre 2011