Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
From MaRDI portal
Publication:2815431
DOI10.1287/ijoc.1100.0436zbMath1461.05091OpenAlexW2021781365MaRDI QIDQ2815431
Federico Malucelli, Stefano Gualandi
Publication date: 29 June 2016
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.1100.0436
Related Items (30)
Constraint programming and operations research ⋮ Graph Coloring Lower Bounds from Decision Diagrams ⋮ Lower bounding techniques for DSATUR-based branch and bound ⋮ Branch-and-Cut-and-Price algorithms for the preemptive RCPSP ⋮ An exact algorithm for the partition coloring problem ⋮ Simple decentralized graph coloring ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation ⋮ A Wide Branching Strategy for the Graph Coloring Problem ⋮ Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Total coloring and total matching: polyhedra and facets ⋮ An integer programming approach to b-coloring ⋮ Fractional programming formulation for the vertex coloring problem ⋮ Symmetry-breaking inequalities for ILP with structured sub-symmetry ⋮ The maximum-impact coloring polytope ⋮ Coordinated cutting plane generation via multi-objective separation ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ Safe Lower Bounds for Graph Coloring ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments ⋮ Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ A lexicographic pricer for the fractional bin packing problem ⋮ A simple branching scheme for vertex coloring problems ⋮ Interval scheduling with economies of scale ⋮ Graph coloring with decision diagrams
Uses Software
Cites Work
- Unnamed Item
- Using tabu search techniques for graph coloring
- Branching in branch-and-price: A generic scheme
- A simple branching scheme for vertex coloring problems
- A \texttt{cost-regular} based hybrid column generation approach
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- Enhancing CP-based column generation for integer programs
- A fast algorithm for the maximum clique problem
- Cost based filtering for the constrained knapsack problem
- Crew assignment via constraint programming: Integrating column generation and heuristic tree search
- Facets of the graph coloring polytope
- Graph coloring for air traffic flow management
- Solving VRPTWs with constraint programming based column generation
- A new trust region technique for the maximum weight clique problem
- Generalised graph colouring by a hybrid of local search and constraint programming
- A cutting plane algorithm for graph coloring
- Accelerating column generation for aircraft scheduling using constraint propagation
- A branch-and-cut algorithm for graph coloring
- Integer Programming and Constraint Programming in Solving a Multimachine Assignment Scheduling Problem with Deadlines and Release Dates
- Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
- A survey on vertex coloring problems
- Solving a resource allocation problem in wireless mesh networks: A comparison between a CP-based and a classical column generation
- A Branch-And-Price Approach for Graph Multi-Coloring
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- Estimation of sparse hessian matrices and graph coloring problems
- A graph coloring algorithm for large scheduling problems
- A Column Generation Approach for Graph Coloring
- Selected Topics in Column Generation
- Improving the Cooperation Between the Master Problem and the Subproblem in Constraint Programming Based Column Generation
- Group Construction for Airline Cabin Crew: Comparing Constraint Programming with Branch and Price
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Integrating operations research in constraint programming
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Constraint programming-based column generation
- Constraint programming based column generation for crew assignment
This page was built for publication: Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
