Optimization Online


Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

Pierre Hansen (pierre.hansen***at***gerad.ca)
Martine Labbé (mlabbe***at***ulb.ac.be)
David Schindl (david.schindl***at***gerad.ca)

Abstract: We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in which constraints express that two stable sets cannot have a common vertex, and large stable sets are preferred in the objective function. We identify facets with small coefficients for the polytopes associated with both formulations. We show by computational experiments that both formulations are about equally efficient when used in a branch-and-price algorithm. Next we propose some preprocessing, and show that it can substantially speed up the algorithm, if it is applied at each node of the enumeration tree. Finally we describe a cutting plane procedure for the set covering formulation, which often reduces the size of the enumeration tree.

Keywords: Graph coloring, stable sets, facets, branch-cut-and-price algorithm

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: Cahier du GERAD G-2005-76, Montreal, september 2005

Download: [PDF]

Entry Submitted: 12/08/2005
Entry Accepted: 12/08/2005
Entry Last Modified: 12/08/2005

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