More on a Binary-Encoded Coloring Formulation

We further develop a parsimonious 0/1 ILP formulation of (Lee, 2002) for edge coloring. With respect to that formulation, our main contributions are: (i) an efficient separation algorithm for general block inequalities, (ii) an efficient LP-based separation algorithm for stars (i.e., the all-different polytope), (iii) introduction of matching inequalities, and (iv) introduction of switched path inequalities and their efficient separation, (v) a complete description for paths, (vi) promising computational results.

By: Jon Lee, François Margot

Published in: Lecture Notes in Computer Science, volume 3064, (no ), pages 271-82 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .