More on a Binary-Encoded Coloring Formulation.pdf.pdf' (157.37 kB)
0/0

More on a Binary-Encoded Coloring Formulation

Download (157.37 kB)
journal contribution
posted on 01.03.1973 by Francois Margot, Jon Lee
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) 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.

History

Date

01/03/1973

Exports

Exports