An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm

DOI10.1007/S10898-019-00867-XMaRDI QIDQ2176284zbMATH OpenOpenAlexFDO

Authors Francisco J. Aragón Artacho, Rubén Campoy, Veit Elser

Publication date 4 May 2020

Published in Journal of Global Optimization (Search for Journal in Brave)

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

zbMATH Keywords

Douglas-Rachford algorithmfeasibility problemgraph coloringnonconvex constraints

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Combinatorial optimization (90C27)

Abstract: We study the behavior of the Douglas-Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. In spite of the combinatorial nature of this problem, the Douglas-Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work we consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas-Rachford algorithm, with this new approach, is demonstrated through various numerical experiments.

Review text

In this paper, the authors study the behavior of the Douglas-Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. Many problems arising from different fields can be formulated as graph coloring problems. Since the graph coloring problem is proved to be NP-complete, most commonly used solvers rely on heuristics. In spite of the combinatorial nature of this problem, the Douglas-Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work, the authors consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas-Rachford algorithm, with this new approach, is demonstrated through various numerical experiments.

Recommendations

• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• Recent results on Douglas-Rachford methods.
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• Fractional programming formulation for the vertex coloring problem
• New algorithm for calculating chromatic index of graphs and its applications

Cites work

• A graph coloring algorithm for large scheduling problems
• A guide to graph colouring. Algorithms and applications
• A survey of graph coloring -- its types, methods and applications
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• An application of graph coloring to printed circuit testing
• Applications of convex analysis within mathematics
• Approximate graph coloring by semidefinite programming
• Benchmarking optimization software with performance profiles.
• Convex analysis and monotone operator theory in Hilbert spaces
• Decomposition through formalization in a product space
• Douglas-Rachford feasibility methods for matrix completion problems
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3671159 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Iterative methods for fixed point problems in Hilbert spaces
• Linear convergence of the Douglas-Rachford method for two closed sets
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• On the local convergence of the Douglas-Rachford algorithm
• Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
• Recent results on Douglas-Rachford methods for combinatorial optimization problems
• Reducibility among combinatorial problems
• Regularity properties of non-negative sparsity sets
• Searching with iterated maps
• Solving graph coloring problems with the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for the case of the sphere and the line

Cited in

(8)

• Solving graph coloring problems with the Douglas-Rachford algorithm
• General splitting methods with linearization for the split feasibility problem
• An incremental search heuristic for coloring vertices of a graph
• Circumcentering reflection methods for nonconvex feasibility problems
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Douglas–Rachford algorithm for control-constrained minimum-energy control problems
• Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach

Describes a project that uses

Uses Software

• gCol
• OEIS

This page was built for publication: An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm

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