Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem

DOI10.1007/978-3-319-59776-8_29MaRDI QIDQ2011610zbMATH OpenOpenAlexFDO

Authors Maël Minot, Samba Ndojh Ndiaye, Christine Solnon

Publication date 4 August 2017

Full work available at URL https://doi.org/10.1007/978-3-319-59776-8_29

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorics in computer science (68R05) Integer programming (90C10)

Recommendations

• ILP models and column generation for the minimum sum coloring problem
• A tabu search approach for the sum coloring problem
• New algorithm for the sum coloring problem
• A branch-and-price algorithm for the minimum sum coloring problem
• A memetic algorithm for the minimum sum coloring problem

Cites work

• A memetic algorithm for the minimum sum coloring problem
• Algorithm portfolios
• An \(O(n\log n)\) bound consistency algorithm for the conjunction of an \textit{alldifferent} and an inequality between a sum of variables and a constant, and its generalization
• An effective heuristic algorithm for sum coloring of graphs
• Graph Colorings
• Graph minors. II. Algorithmic aspects of tree-width
• Hybrid backtracking bounded by tree-decomposition of constraint networks
• Hybrid evolutionary search for the minimum sum coloring problem of graphs
• Lower bounds for the minimal sum coloring problem
• SATzilla: portfolio-based algorithm selection for SAT
• Tight bounds on the chromatic sum of a connected graph

Cited in

(1)

• ILP models and column generation for the minimum sum coloring problem

Describes a project that uses

Uses Software

• llama
• SATzilla
• Gecode
• Choco
• CPLEX

This page was built for publication: Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011610)