## Abstract

Branch-and-price algorithms combine a branch-and-bound search with an exponentially sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch and bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram can be used to solve the pricing problem in a branch-and-price algorithm for the graph coloring problem, even in the presence of constraints imposed by branching decisions. This approach facilitates a much more direct solution method and can improve convergence of the column generation subroutine.

Original language | English (US) |
---|---|

Pages (from-to) | 67-82 |

Number of pages | 16 |

Journal | INFORMS Journal on Computing |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1 2016 |

## Keywords

- Binary decision diagrams
- Branch and price
- Graph coloring

## ASJC Scopus subject areas

- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research