組合せ最適化問題の解の列挙と組合せ遷移

　私は2019年に情報学研究科通信情報システム専攻（情報学科計算機コース）コンピュータアルゴリズム分野に着任しました。本記事では私の研究内容について紹介します。

　私の研究分野は組合せ最適化，特にグラフ最適化問題を解くためのアルゴリズム設計です。多くのグラフ最適化問題では「最も良い解」を1つ求めるためにアルゴリズム（計算手順）を設計します。例えば，地図上の2点間の経路を求める問題では，長さの最も短い経路を「最も良い解」として，それを求めるアルゴリズムを設計するのが基本的な問題です。これをスマートフォンの地図アプリなど，実際の問題への応用を考えると，1つの尺度で「良さ」を測るだけでは不十分です。道路の高低差や混雑の影響で通るのに時間がかかる道路があるかもしれません。個人の好みで通りたくない道路もあるでしょう。

　私の研究しているアプローチは，問題に対して可能な候補をすべて「列挙」する方法です。2点間の経路の例では，現在地から目的地までの経路を，遠回りのものまで含めてすべて求める手法です。候補の個数は，組合せ爆発と呼ばれる現象で，10の何十乗や何百乗もの莫大な数になり，1つずつ候補を出力するのは不可能です。そこで，これらの候補をすべて圧縮して保持することを考え，そのためのデータ構造を研究しています。このデータ構造は良い性質を持ち，単に候補を保持するだけでなく，指定した条件下での候補抽出が可能です。例えば，ある特定の道路を通らない経路候補だけを抽出できます。また，指定した長さ以下の経路候補のみの抽出や，似ている経路の除去が可能です。このように，複数の条件で抽出を繰り返すと，最後に候補が数十通りに残るので，その中から人間が好みの候補を選び出すことが可能になります。グラフの問題で，内部のデータ構造を意識せずに使用できるツールが graphillion という名前で公開されています（http://graphillion.org）。

　最近は，「組合せ遷移」と呼ばれる分野にも着目しています。携帯電話の周波数割当問題（のとても単純なモデル化）を例に考えると，平面上に複数の基地局が設置されており，各基地局は割当てられた周波数の電波を出すとします。定められた距離以下の基地局同士は同じ周波数の電波を出せないとします。このとき，周波数の種類を最小にする割当を求める問題が周波数割当問題です。従来は，種類数最小の割当を求めるアルゴリズム設計が主眼でした。しかしながら，種類数最小の割当が求まったとして，基地局の運用を止めずに1つずつ基地局の周波数を変えることで，現在の割当を種類数最小の割当に変化させることができるでしょうか。これを考えるのが組合せ遷移問題です。科研費学術変革(B)の「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」で組合せ遷移のプロジェクトが始まり，私も参加しており，特に工学のアプローチから，組合せ遷移のソルバー作成や，応用分野の開拓を目標にしています。もしかしたら本記事をお読みの皆様が取り組まれている問題も，組合せ遷移の側面があるかもしれません。ご興味のある方はお問い合わせいただけますと幸いです。

（情報学研究科　通信情報システム専攻）