Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams

DOI10.1287/ijoc.2015.0667zbMath1338.90431arXiv1401.5820OpenAlexW2964309041MaRDI QIDQ2806865

Edward C. Sewell, David R. Morrison, Jacobson, Sheldon H.

Publication date: 19 May 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.5820

zbMATH Keywords

graph coloringbinary decision diagramsbranch and price

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)

Related Items

Graph Coloring Lower Bounds from Decision Diagrams, Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms, An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints, Characteristics of the maximal independent set ZDD, Decision Diagrams for Discrete Optimization: A Survey of Recent Advances, Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem, Exact solution of network flow models with strong relaxations, A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Uncertain vertex coloring problem, Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search, Graph coloring with decision diagrams

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Characteristics of the maximal independent set ZDD
• 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
• Depth-first iterative-deepening: An optimal admissible tree search
• Branch-and-price algorithms for the one-dimensional cutting stock problem
• A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
• Maximum-weight stable sets and safe lower bounds for graph coloring
• An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• A branch-and-cut algorithm for graph coloring
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
• A Metaheuristic Approach for the Vertex Coloring Problem
• A Wide Branching Strategy for the Graph Coloring Problem
• Optimization Bounds from Binary Decision Diagrams
• Decomposition Principle for Linear Programs
• Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems
• Graph-Based Algorithms for Boolean Function Manipulation
• Binary Decision Diagrams
• A Column Generation Approach for Graph Coloring
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• Improving the variable ordering of OBDDs is NP-complete