On a binary-encoded ILP coloring formulation

On a binary-encoded ILP coloring formulation

0.00 Avg rating0 Votes
Article ID: iaor200953691
Country: United States
Volume: 19
Issue: 3
Start Page Number: 406
End Page Number: 415
Publication Date: Jul 2007
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: graphs
Abstract:

We further develop the 0/1 ILP formulation of Lee for edge coloring where colors are encoded in binary. 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) an introduction of matching inequalities, (iv) an introduction of switched path inequalities and their efficient separation, (v) a complete description for paths, and (vi) the promising computational results.

Reviews

Required fields are marked *. Your email address will not be published.