Ising-Machine-Based Solver for Constrained Graph Coloring Problems

Soma KAWAKAMI; Yosuke MUKASA; Siya BAO; Dema BA; Junya ARAI; Satoshi YAGI; Junji TERAMOTO; Nozomu TOGAWA

doi:10.1587/transfun.2023KEP0003

IEICE TRANSACTIONS on Fundamentals

Ising-Machine-Based Solver for Constrained Graph Coloring Problems

Soma KAWAKAMI, Yosuke MUKASA, Siya BAO, Dema BA, Junya ARAI, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA

Full Text Views

0

Cite this

Summary :

Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, 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 additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.1 pp.38-51

Publication Date: 2024/01/01

Publicized: 2023/09/12

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2023KEP0003

Type of Manuscript: Special Section PAPER (Special Section on Circuits and Systems)

Category

Authors

Soma KAWAKAMI
  Waseda University
Yosuke MUKASA
  Waseda University
Siya BAO
  Waseda University
Dema BA
  Nippon Telegraph and Telephone Corporation
Junya ARAI
  Nippon Telegraph and Telephone Corporation
Satoshi YAGI
  Nippon Telegraph and Telephone Corporation
Junji TERAMOTO
  Nippon Telegraph and Telephone Corporation
Nozomu TOGAWA
  Waseda University

Keyword

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

Cite this

Copy

Soma KAWAKAMI, Yosuke MUKASA, Siya BAO, Dema BA, Junya ARAI, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA, "Ising-Machine-Based Solver for Constrained Graph Coloring Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E107-A, no. 1, pp. 38-51, January 2024, doi: 10.1587/transfun.2023KEP0003.
Abstract: Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, 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 additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023KEP0003/_p

Copy

@ARTICLE{e107-a_1_38,
author={Soma KAWAKAMI, Yosuke MUKASA, Siya BAO, Dema BA, Junya ARAI, Satoshi YAGI, Junji TERAMOTO, Nozomu TOGAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Ising-Machine-Based Solver for Constrained Graph Coloring Problems},
year={2024},
volume={E107-A},
number={1},
pages={38-51},
abstract={Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, 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 additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.},
keywords={},
doi={10.1587/transfun.2023KEP0003},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Ising-Machine-Based Solver for Constrained Graph Coloring Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 38
EP - 51
AU - Soma KAWAKAMI
AU - Yosuke MUKASA
AU - Siya BAO
AU - Dema BA
AU - Junya ARAI
AU - Satoshi YAGI
AU - Junji TERAMOTO
AU - Nozomu TOGAWA
PY - 2024
DO - 10.1587/transfun.2023KEP0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2024
AB - Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, 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 additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
ER -

IEICE TRANSACTIONS on Fundamentals