  


BranchCutandPropagate for the Maximum kColorable Subgraph Problem with Symmetry
Tim Januschowski (januscs.ucc.ie) Abstract: Given an undirected graph and a positive integer k, the maximum kcolorable subgraph problem consists of selecting a kcolorable 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 nontrivial 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 branchandcut algorithm for solving the maximum kcolorable subgraph problem with constraint propagation techniques to handle the symmetry arising from the graph. The latter symmetry is handled by (nonlinear) 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 speedup. Keywords: branchandcut algorithm; constraint programming, symmetry breaking; combinatorial optimization; coloring Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Integer Programming (01 Programming ) Citation: Download: [PDF] Entry Submitted: 02/02/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  