Optimization Online


Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry

Tim Januschowski (janus***at***cs.ucc.ie)
Marc E. Pfetsch (m.pfetsch***at***tu-bs.de)

Abstract: Given an undirected graph and a positive integer k, the maximum k-colorable subgraph problem consists of selecting a k-colorable induced subgraph of maximum cardinality. The natural integer programming formulation for this problem exhibits two kinds of symmetry: arbitrarily permuting the color classes and/or applying a non-trivial graph automorphism gives equivalent solutions. It is well known that such symmetries have negative effects of the performance of constraint/integer programming solvers. We investigate the integration of a branch-and-cut algorithm for solving the maximum k-colorable subgraph problem with constraint propagation techniques to handle the symmetry arising from the graph. The latter symmetry is handled by (non-linear) lexicographic ordering constraints and linearizations thereof. In experiments, we evaluate the influence of several components of our algorithm on the performance, including the different symmetry handling methods. We show that several components are crucial for an efficient algorithm; in particular, the handling of graph symmetries yields a significant performance speed-up.

Keywords: branch-and-cut algorithm; constraint programming, symmetry breaking; combinatorial optimization; coloring

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 02/02/2011
Entry Accepted: 02/03/2011
Entry Last Modified: 03/16/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society