Polyhedral Methods for the Maximum Clique Problem,

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1994
Accession Number
ADA298925

Entities

People

  • Egon Balas
  • Gabor Pataki
  • Gérard Cornuéjols
  • Sebastian Ceria

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Convex Sets
  • Demographic Cohorts
  • Eigenvalues
  • Inequalities
  • Linear Programming
  • Military Research
  • Nonlinear Systems
  • Notation
  • Test Sets
  • Theorems

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research