「グラフ彩色問題：正確な解とヒューリスティックな解」

「グラフ彩色問題：正確な解とヒューリスティックな解」の魅力と効果

Pythonによるカスタム構成ヒューリスティックと整数プログラミングを通じた古典的な離散最適化問題の探索

グラフ彩色理論は、離散数学において中心的な位置を占めています。彩色とは、色分けに特定のルールに従ってオブジェクトの集合をクラスに分割する基本的な問題です（Jensen＆Toft、1995年）。

この問題を以下のようにまとめることができます：与えられた無向グラフG（V、E）に対して、隣接する2つのノードが同じ色を共有せず、使用する色の数を最小限にするように各ノード（頂点）に色を割り当てます。簡潔で明確な述べ方ですが、この問題はその計算の複雑さのために悪名高く、NP困難な問題のカテゴリーに属しています。

その組合せの複雑さのため、整数線形プログラミング（ILP）の正確なアプローチは、最良のソルバーを使用しても大規模なインスタンスを解決することができない場合があります。そのような状況では、ヒューリスティックおよびメタヒューリスティックは興味深い代替手段となります。最適性を証明することはできませんが、これらの手法は、素早く品質の良いソリューションを提供することができます。

今回の記事では、構造ヒューリスティックDSatur（Brélaz、1979年）とpyomo（Bynum et al.、2021年）を使用した整数線形プログラミングモデルとsolver HiGHSを使用して、グラフ彩色問題を解決します。他の記事と同様に、完全なコードは私のコードリポジトリで見つけることができます。

• 予測メンテナンスの理解-ユニットルートと安定性
• データ管理における機械学習の活用
• 分散システム設計におけるコンセンサスアルゴリズムの役割の探索

線形プログラミングにまだ慣れていない場合は、先行知識として私の以前の記事「Linear programming: Theory and applications」をお読みいただくことをおすすめします。

線形プログラミング：理論と応用

線形最適化の主要な概念とPythonにおける実装

towardsdatascience.com

さあ、このような素晴らしいソリューションを作成するための実践に入りましょう。

構成ヒューリスティック – DSatur

問題定義を思い出してみましょう：

• 無向グラフG（V、E）を考えます。
• 隣接する2つのノードが同じ色を共有しないように、各ノードに色を割り当てます。
• 使用される色の数を最小限にします。

単純な構成的な解決策は、空のノードを順次選択し、そのノードに色を割り当てることであり、その色がまだ隣接ノードで使用されていないことを確認します。これは最善の戦略ではないかもしれませんが、必要な色の上限を提供することができます。しかし、DSatur（Brélaz、1979年）アルゴリズムでは、次のノードの選択とこのヒューリスティックの改善のための新しい要素が含まれています。

• 次数：特定のノードに接続されたエッジの数。
• 彩色度：近隣で使用されている異なる色の数。

DSaturのアルゴリズムは、未彩色ノードのキューから始まり、彩色度が最大のノードを反復的に選択し、キューから削除し、色を割り当てます。彩色度に等しさがある場合、Brélaz（1979）は最大彩色度のいずれかを選択することを提案しています。私たちはやや異なるアプローチを選び、最大の全体的な次数を持つノードを選ぶことで優先順位をつけることで、この条件付きを解消します。与えられたノードへの割り当てられる色は、利用可能な最小のインデックスを持つものであるべきです。以下に擬似コードを示します。Nをノードの集合、Qを未彩色ノードのキュー（N自体と同じメモリ位置を参照）で参照し、Cを使用された色の集合としてください。

dsatur(N)  Q = [&n for n in N]  C = {}  while |Q| > 0:    sort(Q) // saturationとdegreeによる降順ソート    n = Q.pop(0)    assign_color(n, C)

関数assign_colorは、利用可能な最小のインデックスの色を検証し、現在のセットから適切な色がない場合は新しい代替案を追加してセットを増やす必要があります。

それでは、Pythonコードに変換しましょう。まず、パッケージのインポートから始めましょう。私たちのヒューリスティックは純粋なPythonで書かれており、型ヒントのみをインポートしています。

from typing import List, Tuple

次に、基本的なモデリング要素を定義しましょう。色とノード。クラスColorは、それぞれのインデックスの可変プレースホルダーとして定義されています。これは、Pythonでは複数の変数が同じメモリ位置を参照できるため、メモリ効率がよくなります。メソッドadd_nodeは、与えられた色で新しいノードが色付けされるたびに呼び出す必要があります。

class Color:    index: int    n_nodes: int    def __init__(self, index) -> None:        self.index = index        self.n_nodes = 0    def __repr__(self):        return f"C{self.index}"    def add_node(self):        self.n_nodes = self.n_nodes + 1

次に、クラスNodeです。Nodeの各インスタンスには、ノードのリスト（ポインタ）である属性neighborsがあります。したがって、ノードが変更されるたびに、近隣の情報を変更する必要はありません。メソッドadd_neighborを使用して近隣を追加し、メソッドset_colorを使用して色を設定し、近隣の現在の状態に依存するプロパティneighbor_colors、saturation、およびdegreeにアクセスできます。

class Node:    neighbors: List['Node']    index: int    color: Color    def __init__(self, index):        self.index = index        self.neighbors = []        self.color = None    def __repr__(self) -> str:        return f"N{self.index}|{self.color}"    def add_neighbor(self, node: 'Node'):        if node not in self.neighbors:            self.neighbors.append(node)    def set_color(self, color: Color):        self.color = color        color.add_node()    @property    def neighbor_colors(self):        return [n.color for n in self.neighbors if n.color is not None]    @property    def saturation(self):        return len(set((n.color for n in self.neighbors if n.color is not None)))    @property    def degree(self):        return len(self.neighbors)

それでは、DSaturアルゴリズムに入りましょう。実装するために、同じ名前のクラスを作成します。新しいDSaturインスタンスの作成には、グラフのノードの数n_nodesとedgesが引数として渡されます。その後、ノードをインスタンス化し、エッジに基づいて近隣を設定します。

class DSatur:    N: List[Node]    C: List[Color]    history: List[Node]    def __init__(self, nodes: List[int], edges: List[Tuple[int, int]]):        N = [Node(i) for i in nodes]        for e in edges:            i, j = e            N[i].add_neighbor(N[j])            N[j].add_neighbor(N[i])        self.N = N        self.C = []        self.history = []    def find_next_color(self, node: Node) -> Color:        next_color = None        for c in self.C:            if c not in node.neighbor_colors:                next_color = c                break        if next_color is None:            next_color = Color(len(self.C) + 1)            self.C.append(next_color)        return next_color    def solve(self, save_history=False):        Q = [n for n in self.N]  # 未着色のノードのプール        while len(Q) > 0:            Q.sort(key=lambda x: (x.saturation, x.degree), reverse=True)            n: Node = Q.pop(0)            next_color = self.find_next_color(n)            n.set_color(next_color)            if save_history:                self.history.append(n)        self.C.sort(key=lambda x: x.n_nodes, reverse=True)    @property    def cost(self):        return len(self.C)

さあ、難しい問題を解決するためにそれを使ってみましょう！ OR Library にいくつかの例があります。それらは「gcolX」として示されています。次のコードを使用して、それらのファイルのノード数とエッジ数を抽出することができます。

# Open and read filewith open($YOUR_FILE_PATH, mode="r") as file:    lines = file.readlines()    header = lines[0].strip().split()    n_nodes = int(header[2])    edges = []    node_set = set()    for line in lines[1:]:        if line.startswith('e'):            _, i, j = line.strip().split()            edges.append((int(i), int(j)))            node_set.add(int(i))            node_set.add(int(j))nodes = sorted(node_set)assert len(nodes) == n_nodes, "Wrong number of nodes specified"

それから、新しいDSaturインスタンスにそれらを解析して問題を解決します（または少なくとも良質な近似値を得ます）。

dsatur = DSatur(nodes, edges)dsatur.solve()

導入から結果を興味深く可視化するためのコードはここに含めるには冗長すぎるかもしれませんが、私のコードリポジトリで見つけることができます。これはいくつかのノードを処理する際にどれだけ難しくなるかの一般的なアイデアを伝えることができます…

では、正確な手法でどのように対処できるか見てみましょう。

整数線形計画法

ヒューリスティクスを使用して得られた解を洗練させ、解の最適性を証明しようとするには、グラフ彩色問題をILPモデルとして定式化しましょう。ただし、大規模なインスタンスでは対応できない可能性もあります。このセクションで紹介されているモデルと他の正確なアルゴリズムは、Lewis (2021) の第3章で説明されています。

このアプローチで考慮される集合を定義しましょう：

• C：色
• N：ノード（または頂点）
• E：エッジ

最初の質問は「何色を考慮すべきか」というものです。最悪の場合、すべてのノードが接続されているため、CのサイズをNと同じにする必要があります。ただし、このアプローチでは必要としない決定変数の数を不必要に増やし、モデルの線型緩和を悪化させる可能性があります。カラーバッチの数を上限とするためのヒューリスティック手法（例えば、DSatur）を使用するのが良い代替手段です。

この問題では、2つのグループの決定変数があります：

• x_{i, c}：ノードiが色cで彩色されていることを示すバイナリ変数
• y_{c}：色cが使用されていることを示すバイナリ変数

また、次の制約を設ける必要があります：

• すべてのノードには色がつけられなければなりません
• エッジのいずれかのノードに色がある場合、その色が使用されていることを保証する
• 各エッジのノードのうち、1つのノードだけが特定の色で彩色されている
• 対称性を破る（必須ではありませんが、役立つ場合があります）

最後に、使用される色の総数を最小化する目的を持つ必要があります。これはyの合計です。まとめると、次の方程式があります。

さあ、整数計画モデルのためにpyomoをインポートしましょう。

import pyomo.environ as pyo

pyomoで問題をモデル化するためには、2つのアプローチがあります：抽象モデルと具体モデルです。最初のアプローチでは、問題の代数的な式がデータ値の供給前に定義されますが、2番目のアプローチでは、モデルインスタンスがその要素が定義されるとすぐに作成されます。これらのアプローチについての詳細は、ライブラリのドキュメントまたはBynum et al. (2021) の書籍で確認することができます。本記事では具体モデルの考え方を採用します。

model = pyo.ConcreteModel()

さて、Setsをインスタンス化しましょう。
dsaturの属性NとCから直接イテラブルを解析することは有効ですので、initializeキーワード引数でそれらを使用することができます。また、私は元のノードとエッジを入力データから渡し、DSaturの範囲を色の初期化として作成します。

model.C = pyo.Set(initialize = range(len(dsatur.C)))  # Colorsmodel.N = pyo.Set(initialize = nodes)  # Nodesmodel.E = pyo.Set(initialize = edges)  # Edges

次に、決定変数をインスタンス化します。

model.x = pyo.Var(model.N, model.C, within = pyo.Binary)model.y = pyo.Var(model.C, within = pyo.Binary)

そして、制約条件を設定します。

# 各ノードに色を割り当てるdef fill_cstr(model, i): return sum(model.x[i, :]) == 1

# エッジ上で色を繰り返さないことと、色が使用されていることを示すdef edge_cstr(model, i, j, c): return model.x[i, c] + model.x[j, c] <= model.y[c]

# 偏在を破るための優先順位の設定（必須ではない）def break_symmetry(model, c): if model.C.first() == c: return 0 <= model.y[c] else: c_prev = model.C.prev(c) return model.y[c] <= model.y[c_prev]

model.fill_cstr = pyo.Constraint(model.N, rule=fill_cstr)model.edge_cstr = pyo.Constraint(model.E, model.C, rule=edge_cstr)model.break_symmetry = pyo.Constraint(model.C, rule=break_symmetry)

他の偏在破壊の制約を追加して、使用可能なソルバーとの組み合わせでどのように動作するか確認してみることもできます。私が行った実験では、特定の色に割り当てられた総ノードを使用した優先順位の設定を含めると、それを無視するよりも悪い結果となりました。おそらく、ソルバー固有の偏在破壊戦略のためです。

# 偏在破壊を総合した優先順位の設定def break_symmetry_agg(model, c): if model.C.first() == c: return 0 <= sum(model.x[:, c]) else: c_prev = model.C.prev(c) return sum(model.x[:, c]) <= sum(model.x[:, c_prev])

最後に、目標を設定します…

# 使用された色の総数def obj(model): return sum(model.y[:])model.obj = pyo.Objective(rule=obj)

そして、モデルは解決する準備ができています！そのためには、HiGHSパーシステントソルバーを使用しています。もしPythonの環境にhighspyがインストールされている場合、pyomoで利用できます。

solver = pyo.SolverFactory("appsi_highs")solver.highs_options["time_limit"] = 120res = solver.solve(model)print(res)

大規模な問題では、ソルバーはヒューリスティックな解を改善するのに苦労することがあります。ただし、32ノードの問題では、ソルバーは使用する色の数を9から8に減らすことができました（コードリポジトリで利用可能）。なお、実行には24秒かかりましたが、同じ問題についてのDSaturアルゴリズムは6ミリ秒しかかかりませんでした（インタプリタ言語である純粋なPythonを使用）。

さらに詳しく読む

DSaturは直感的なヒューリスティックであり、高速で良質な解を提供しますが、複雑なインスタンスでは他の手法の方がより良い結果をもたらすことがあります。グラフ彩色問題における最も有名なメタヒューリスティックの1つはTabucolです（Hertz＆Werra、1987）。著者らは、k色を持つ初期解から始め、おそらく同じ色のノードを接続するエッジを持つような解を提供します。そして、使用可能な場所で違反を最小化するように、特定のノードの色を変更するローカルな移動を行います。ローカル最適解から逃れるためにTabuリストを使用します。

この記事では、グラフ彩色問題を解くための、ここで紹介されたものよりも効率的な手法が、Branch & Priceと呼ばれるアルゴリズムを使用したカラム生成に頼っています。このトピックに興味を持つ読者は、別のVoAGIの記事で簡潔な概要を見つけることができます。

線形計画法と切削ストック問題におけるカラム生成

Pythonの例を使って、多数の決定変数を持つ線形問題を解く方法

towardsdatascience.com

結論

この記事では、グラフ彩色問題を解くための2つの手法が紹介されました。構築性ヒューリスティックDSatur（Brélaz、1979年）と整数線形プログラミング（ILP）モデルです。ヒューリスティックは、中程度のサイズの問題に対して高速で高品質な解を提供することができ、その解はILPモデルを使用してさらに改善されました。実装されたコードは、パブリックリポジトリでのさらなる利用が可能です。

参考文献

Brélaz, D., 1979. New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256.

Bynum, M. L. et al., 2021. Pyomo-optimization modeling in Python. Springer.

Hertz, A., & Werra, D. D., 1987. Using tabu search techniques for graph coloring. Computing, 39(4), 345–351.

Jensen, T. R., & Toft, B., 1995. Graph coloring problems. John Wiley & Sons.

Lewis, R.M.R., 2021. Advanced Techniques for Graph Colouring. In: Guide to Graph Colouring. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-81054-2_4

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!