The INFORMS Journal of Computing has awarded Anuj Mehrotra, dean of the Georgia Tech Scheller College of Business, and Michael Trick, dean and chief academic officer of Carnegie Mellon University in Qatar, the "Test of Time Award" for papers published from 1995-1999 for their paper titled "A Column Generation Approach for Graph Coloring."
The INFORMS Journal of Computing Test of Time Award is presented by the INFORMS Journal on Computing to honor research papers that have demonstrated significant and enduring influence in the field. This award recognizes papers that remain relevant and impactful even years after publication, celebrating them as "classics" within the journal's scope.
Test of Time Award Citation 1995–1999
Graph coloring has a simple polynomial-sized integer-programming formulation, but, even for modest-sized graphs, the resulting IP models are notoriously difficult to solve. This difficulty is due in large part to the symmetry in the model, where color classes are not distinguished in the IP variables. The solution proposed in the Mehrotra-Trick paper is to break the symmetry, creating a model with a variable for each potential color class. The resulting exponential-sized formulation is handled by delayed column generation combined with an ingenious branching rule, designed to maintain the original graph-coloring structure in the newly created subproblems. The paper is beautifully written, developing and explaining difficult concepts in branch-cut-and-price methodology in an easy-to-grasp setting. Their elegant work has long served as an important template in the application of linear programming techniques to the solution of difficult optimization models. It will continue to do so for years to come.
Citation: Anuj Mehrotra and Michael Trick "A Column Generation Approach for Graph Coloring" INFORMS Journal on Computing, Volume 8, Issue 4, Fall 1996, pp. 344–354.