The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Ising 기계는 조합 최적화 문제의 최적 또는 준최적 솔루션을 효율적이고 효과적으로 찾을 수 있습니다. 어려운 조합최적화 문제 중 하나인 그래프 색칠 문제는 간선으로 연결된 두 꼭지점이 같은 색이 되지 않도록 그래프의 각 꼭지점에 색을 할당하는 문제입니다. 그래프 색상 문제를 Ising 모델이나 QUBO(Quadratic Unconstrained Binary Optimization) 모델에 매핑하는 방법이 제안되었지만 색상 수를 최소화하는 방법은 고려되지 않았습니다. 또한, 실제적인 문제에 적용하기 위해 추가적인 제약을 고려한 Ising-machine 기반의 방법은 없다. 본 논문에서는 QUBO 모델에 색상 수를 최소화하고 제약 조건을 추가하는 것을 포함하는 그래프 색칠 문제의 매핑 방법을 제안합니다. 그래프 채색 문제에 대한 제약항과 함께 사용되는 스핀 수가 기하급수적으로 증가하지 않도록 색상 수를 최소화할 수 있는 목적 함수항을 먼저 제안합니다. 둘째, 우리는 두 가지 추가 제약 조건을 제안합니다. 하나는 특정 정점이 지정된 색상으로 색칠되어야 한다는 것입니다. 또 하나는 특정 색상은 미리 정해진 횟수 이상 사용할 수 없다는 점이다. 우리는 제안된 QUBO 매핑의 에너지가 최소화되면 모든 제약 조건이 충족되고 목적 함수가 최소화된다는 것을 이론적으로 증명합니다. Ising 장비를 이용한 실험 결과, 제안하는 방법은 추가적인 제약 조건을 고려하지 않은 경우 기존 기준 방법에 비해 사용되는 색상의 수를 평균 최대 75.1% 감소시키는 것으로 나타났다. 추가적인 제약 조건을 고려하면 제안한 방법은 모든 제약 조건을 만족하는 실현 가능한 해를 효과적으로 찾을 수 있다.
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
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
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
부
@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},}
부
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 -