Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
From MaRDI portal
Publication:2806865
DOI10.1287/IJOC.2015.0667zbMATH Open1338.90431arXiv1401.5820OpenAlexW2964309041MaRDI QIDQ2806865FDOQ2806865
E. C. Sewell, David R. Morrison, Sheldon H. Jacobson
Publication date: 19 May 2016
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
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 (ZDD) 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.
Full work available at URL: https://arxiv.org/abs/1401.5820
Recommendations
- A Branch-And-Price Approach for Graph Multi-Coloring
- A branch-and-price algorithm for the (\(k,c\))-coloring problem
- A branch-and-price algorithm for the robust graph coloring problem
- A branch-and-price approach for the partition coloring problem
- A branch-and-price algorithm for the minimum sum coloring problem
- A branch and price algorithm for list coloring problem
- Exact weighted vertex coloring via branch-and-price
- A Wide Branching Strategy for the Graph Coloring Problem
- Efficient bounds on a branch and bound algorithm for graph colouration
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph-Based Algorithms for Boolean Function Manipulation
- Branch-and-price: Column generation for solving huge integer programs
- A branch-and-cut algorithm for graph coloring
- An exact approach for the vertex coloring problem
- Branching in branch-and-price: A generic scheme
- Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem
- Decomposition Principle for Linear Programs
- A Branch-and-Price Algorithm for the Generalized Assignment Problem
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Robust branch-and-cut-and-price for the capacitated vehicle routing problem
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
- Binary Decision Diagrams
- A Column Generation Approach for Graph Coloring
- Branch-and-price algorithms for the one-dimensional cutting stock problem
- An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset
- Exact solution of graph coloring problems via constraint programming and column generation
- A Wide Branching Strategy for the Graph Coloring Problem
- Improving the variable ordering of OBDDs is NP-complete
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- A metaheuristic approach for the vertex coloring problem
- Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems
- Depth-first iterative-deepening: An optimal admissible tree search
- Optimization Bounds from Binary Decision Diagrams
- Title not available (Why is that?)
- Characteristics of the maximal independent set ZDD
- A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
Cited In (14)
- Characteristics of the maximal independent set ZDD
- Graph coloring with decision diagrams
- Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem
- Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms
- Extended formulations via decision diagrams
- A branch-and-price algorithm for the robust graph coloring problem
- Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search
- An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints
- Uncertain vertex coloring problem
- Graph Coloring Lower Bounds from Decision Diagrams
- A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching
- Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
- Exact solution of network flow models with strong relaxations
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
Uses Software
This page was built for publication: Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806865)
