Branch-and-price algorithms combine a branch-and-bound search with anexponentially-sized LP formulation that must be solved via column generation.Unfortunately, the standard branching rules used in branch-and-bound forinteger programming interfere with the structure of the column generationroutine; therefore, most such algorithms employ alternate branching rules tocircumvent this difficulty. This paper shows how a zero-suppressed binarydecision diagram (ZDD) can be used to solve the pricing problem in abranch-and-price algorithm for the graph coloring problem, even in the presenceof constraints imposed by branching decisions. This approach facilitates a muchmore direct solution method, and can improve convergence of the columngeneration subroutine.
展开▼
