A Column Generation Approach for Graph Coloring
Session date: 12 February 2024
Session host: Konstantin Sidorov
Summary:
In this session, I will discuss the branch-and-price framework using graph coloring as an example problem. The branch-and-price approach involves restating the original problem as a MILP model with (exponentially) many variables and lazily introducing them via the duality reasoning, all while executing a normal branch-and-bound loop. The graph coloring case is particularly convenient here because (a) the reformulation is, in my opinion, relatively intuitive and (b) most of the typical branch-and-price technical complications are resolved straightforwardly.
I will largely follow the narrative of (Mehrotra & Trick, 1996) but I also hope to mention some of the more involved branch-and-price topics and how they are resolved, as well as some connections to (unsurprisingly) the proof-logging domain:)
Relevant papers
-
A Column Generation Approach for Graph Coloring
Anuj Mehrotra, and Michael A. Trick
INFORMS Journal on Computing, Nov 1996
We present a method for solving the independent set formulation of the graph coloring problem (where there is one variable for each independent set in the graph). We use a column generation method for implicit optimization of the linear program at each node of the branch-and-bound tree. This approach, while requiring the solution of a difficult subproblem as well as needing sophisticated branching rules, solves small to moderate size problems quickly. We have also implemented an exact graph coloring algorithm based on DSATUR for comparison. Implementation details and computational experience are presented.
-
Selected Topics in Column Generation
Marco E. Lübbecke, and Jacques Desrosiers
Operations Research, Nov 2005
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large-scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not yet found in textbooks. We emphasize the growing understanding of the dual point of view, which has brought considerable progress to the column generation theory and practice. It stimulated careful initializations, sophisticated solution techniques for the restricted master problem and subproblem, as well as better overall performance. Thus, the dual perspective is an ever recurring concept in our “selected topics.”