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
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
