(A) polyhedral cutting plane algorithm for the edge coloring problem

Abstract

Edge coloring problem is to find a coloring of the edges of a given graph with minimum number of colors so that any pair of edges that are incident to a common node have different colors. This is one of the combinatorial optimization problem on graphs and related to such diverse fields as several scheduling problems in operations research, electrical network analysis and statistics. We consider the edge coloring problem on a simple graph as the integer program of covering edges by matchings. In this paper we describe an implementation of algorithm for it. The algorithm uses a polyhedral cutting plane. And linear programming based weighted matching procedure is introduced for generating columns. Moreover the algorithm adopts an efficient branching scheme that makes the graph smaller by deleting some matchings. The implementation of the algorithm is described in details and computational results are given.