  


Set covering and packing formulations of graph coloring: algorithms and first polyhedral results
Pierre Hansen (pierre.hansengerad.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 branchandprice 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, branchcutandprice algorithm Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Citation: Cahier du GERAD G200576, Montreal, september 2005 Download: [PDF] Entry Submitted: 12/08/2005 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  