Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
From MaRDI portal
Publication:2806865
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.
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
Cites work
- scientific article; zbMATH DE number 956839 (Why is no real title available?)
- A BB\&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times
- A Branch-and-Price Algorithm for the Generalized Assignment Problem
- A Column Generation Approach for Graph Coloring
- A Wide Branching Strategy for the Graph Coloring Problem
- A branch-and-cut algorithm for graph coloring
- A metaheuristic approach for the vertex coloring problem
- An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset
- An exact approach for the vertex coloring problem
- Binary Decision Diagrams
- Branch-and-price algorithms for the one-dimensional cutting stock problem
- Branch-and-price: Column generation for solving huge integer programs
- Branching in branch-and-price: A generic scheme
- Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem
- Characteristics of the maximal independent set ZDD
- Decomposition Principle for Linear Programs
- Depth-first iterative-deepening: An optimal admissible tree search
- Exact solution of graph coloring problems via constraint programming and column generation
- Graph-Based Algorithms for Boolean Function Manipulation
- Improving the variable ordering of OBDDs is NP-complete
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Optimization Bounds from Binary Decision Diagrams
- Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems
- Robust branch-and-cut-and-price for the capacitated vehicle routing problem
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
Cited in
(14)- A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching
- Graph coloring lower bounds from decision diagrams
- 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
- Uncertain vertex coloring problem
- Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
- Exact solution of network flow models with strong relaxations
- An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
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)
