Accession Number : ADA298925

Title :   Polyhedral Methods for the Maximum Clique Problem,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATI ON

Personal Author(s) : Balas, Egon ; Ceria, Sebastian ; Cornuejols, Gerard ; Pataki, Gabor

PDF Url : ADA298925

Report Date : FEB 1994

Pagination or Media Count : 24

Abstract : This paper presents an integer programming approach to the maximum clique problem. An initial linear programming relaxation is solved and, when there is an integrality gap, this relaxation is strengthened using one of several tightening procedures. This is done through the addition of cutting planes to the linear program. The bulk of the paper deals with theoretical and computational issues associated with the generation of these cuts. In particular, we describe how to obtain cuts from the positive semi-definiteness of an underlying matrix. The various cuts are then compared in a computational experiment. These cuts can be incorporated into a branch-and-cut algorithm and we report results with such an algorithm on some of the DIMACS benchmark instances. (AN)

Descriptors :   *ALGORITHMS, *LINEAR PROGRAMMING, *INTEGER PROGRAMMING, OPTIMIZATION, COMPUTATIONS, MATRICES(MATHEMATICS), HEURISTIC METHODS, NUMERICAL METHODS AND PROCEDURES, CONVEX SETS, INEQUALITIES.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE