A Constrained Graph Coloring Solver Based on Ising Machines

Soma Kawakami, Yosuke Mukasa, Siya Bao, Dema Ba, Junya Arai, Satoshi Yagi, Junji Teramoto, Nozomu Togawa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Optimum or quasi-optimum solutions of combinatorial optimization problems can be efficiently found by using Ising machines. The graph coloring problem (GCP) is known as a difficult combinatorial problem. Given a graph, each vertex should be assigned a color and any two vertices connected by an edge must not be colored the same. Although methods to map the GCP onto the Ising model are proposed, none of them considers minimizing the number of colors. In this paper, we propose a mapping method of the GCP including minimizing the number of colors and additional constraints to the QUBO (Quadratic Unconstrained Binary Optimization) model. As well as the constraint terms for the GCP, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two more additional terms so that our proposed method can be applicable to practical consumer applications. The experimental evaluations on an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared with the existing baseline method. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

Original languageEnglish
Title of host publication2023 IEEE International Conference on Consumer Electronics, ICCE 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781665491303
DOIs
Publication statusPublished - 2023
Event2023 IEEE International Conference on Consumer Electronics, ICCE 2023 - Las Vegas, United States
Duration: 2023 Jan 62023 Jan 8

Publication series

NameDigest of Technical Papers - IEEE International Conference on Consumer Electronics
Volume2023-January
ISSN (Print)0747-668X

Conference

Conference2023 IEEE International Conference on Consumer Electronics, ICCE 2023
Country/TerritoryUnited States
CityLas Vegas
Period23/1/623/1/8

Keywords

  • Ising machine
  • QUBO model
  • additional constraint
  • constrained graph coloring problem
  • minimizing the number of colors

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Constrained Graph Coloring Solver Based on Ising Machines'. Together they form a unique fingerprint.

Cite this