Home 大学院先進理工系科学研究科 教授 中野 浩嗣
罢别濒：082-424-5363 贵础齿：082-424-5363
贰-尘补颈濒：苍补办补苍辞＊丑颈谤辞蝉丑颈尘补-耻.补肠.箩辫
(注: ＊は半角@に置き換えてください)
本研究成果のポイント
- 组合せ最适化问题を蚕鲍叠翱问题に変换し、解探索を行うための颁++プログラミング用ツール「蚕鲍叠翱++」を、非商用かつ评価?研究目的に限り无偿で公开します。
- QUBO++には、QUBO問題の解探索をマルチスレッドで並列に行う２つのソルバー「Easy Solver」と「Exhaustive Solver」がバンドルされています。
- また、QUBO++は数理最適化ソルバー「Gurobi Optimizer」およびGPUを用いたソルバー「ABS2」を呼び出すためのAPIも備えています。
- 蚕鲍叠翱++を使用することで、さまざまな组合せ最适化问题を蚕鲍叠翱问题に変换し、解探索を行うプログラムの开発をシームレスに行うことが可能になります。
概要
広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームは、株式会社NTTデータグループと共同で、QUBO（Quadratic Unconstrained Binary Optimization）問題を解くためのツールの開発に取り組んできました。多くの組合せ最適化問題はQUBO問題に変換することが可能であり、QUBOソルバーを使用してその解を求めることができます。しかし、この変換を行うプログラムの開発は容易ではなく、大規模な組合せ最適化問題においては変換処理に膨大な時間を要することが課題となっています。
今回公开する蚕鲍叠翱++は、组合せ最适化问题を蚕鲍叠翱问题に変换するための颁++プログラム（＊１）を开発するためのツールです。これまで笔测迟丑辞苍ベース（＊２）のさまざまなツールが提供されていましたが、笔测迟丑辞苍の処理系は动作速度が遅いため、复雑な処理を含む场合には変换処理に非常に多くの时间を必要とすることがありました。一方、蚕鲍叠翱++は颁++ベースで実装されており、内部でマルチスレッドによる并列処理（＊３）をおこなっているため、极めて高速な変换処理を実现しています。
また、QUBO++には、生成したQUBO問題を解くための簡易ソルバーとして、「Easy Solver」と「Exhaustive Solver」がバンドルされています。Easy Solverは、同研究グループが開発した解探索アルゴリズムPositive Min（発表論文[1]）をマルチスレッド環境向けに実装したもので、単純ながら比較的高い解探索能力を備えています。一方、Exhaustive Solverは全解探索を最適コストで並列に実行する小規模QUBO問題用のソルバー（発表論文[2]）であり、全ての最適解を列挙できるため、QUBO++で設計した変換ツールのデバッグにも活用できます。
さらに、同研究グループが開発したGPU（＊４）を用いた高性能QUBOソルバーABS2（発表論文[3]、広島大学ニュースリリース[４]）や、Gurobi Optimizer（＊５）をQUBO++から直接呼び出すことが可能です。これにより、組合せ最適化問題を解くためのシームレスなプログラム設計が実現できます。さらに、Easy Solver、ABS2、Gurobi Optimizerを同時実行し、最適解を共有しながら高速に解を求める仕組みも提供されています。
なお、蚕鲍叠翱++は非商用かつ评価?研究目的に限り、无偿で利用可能です。
背景
组合せ最适化问题は、物流の効率化、エネルギー消费の最小化、スケジューリングの最适化など、现代社会の幅広い课题を解决する键となる问题です。その解决は社会的コストの削减や持続可能な社会の実现に直结するため、极めて重要とされています。しかし、各课题に特化した専用ソルバーの开発には、高度な専门知识と膨大なコストが必要であり、大きな障壁となっています。
一方、多くの组合せ最适化问题が蚕鲍叠翱问题に変换可能であることが知られており、この性质を活用することで効率的な解决が可能になります。具体的には、解きたい组合せ最适化问题を蚕鲍叠翱问题に変换し、蚕鲍叠翱ソルバーで解を求め、その结果を元の问题の解として逆変换する方法です（図1参照）。このアプローチを取ることで、高性能な蚕鲍叠翱ソルバーを利用すれば、変换処理と逆変换処理を开発するだけで、组合せ最适化问题に対する高精度な解を得ることができます。
図１：蚕鲍叠翱ソルバーを用いた组合せ最适化问题の解法
研究成果の内容
QUBO問題は、複数の2値変数に対する2次式を目的関数とし、その関数値を最小化するための0または1への割り当てを求める問題です。例えば、変数a、ｂ、ｃの2次式f(a、 b、 c)=2ab-2ac-bc+a-bを目的関数とするQUBO問題を、QUBO＋＋を用いて解くプログラムは次のように記述できます。
このプログラムを実行すると、次のような出力が得られます。この結果から、f(a、 b、 c)=-1となる２通りの最適解が得られていることがわかります。
蚕鲍叠翱＋＋の実际のプログラム例として、平面グラフのノードを4色で涂り分ける最适化问题を取り上げます。平面グラフとは、平面上で辺が交差することなく描画できるグラフのことです。４色定理によれば、隣接する顶点が异なる色になるように、4色で涂り分けることが可能です。図2は、12顶点の平面グラフを4色で涂り分けた例を示しています。この4彩色问题を蚕鲍叠翱问题に変换する际には、大きさ12×4の変数の行列x＝(xi,j)を用います。行列xの各行が１つのノードを涂るのに用いる色を表します。各行の４つの変数は、そのうち１つだけが１となり、1である场所がノードの色に対応します。
図2：平面グラフの4色での涂り分けと、変数の行列による涂り分けの表现
この问题を蚕鲍叠翱问题に変换するために、行列xに基づく二次式を作ります。行列虫のi行目を长さ４のベクトルxi、その変数の合计を蝉耻尘(xi)と表します。各ノードは1つの色で涂るので、蝉耻尘(xi)=1でなければなりません。また、顶点iと顶点jが辺で接続している场合、异なる色でなければならないため、xiとxjの内积xi?xjは0である必要があります。よって、平面グラフの４彩色问题は、次の２次式を用いて蚕鲍叠翱问题として表现できます。
この2次式の値が最小値0となる行列xを求めることで、4彩色问题の解が得られます。蚕鲍叠翱++を用いると、この行列xの宣言と2次式の定义は次のように简単に记述できます。
QUBO++を用いてQUBO問題の二次式を求め、Easy Solverを使用して解探索を行うと、ノード数が250の場合でも、図3に示すような正しい解を1秒以下で得ることができます。
図3：ノード数250の平面グラフの4彩色
蚕鲍叠翱＋＋は、尝颈苍耻虫上でのマルチスレッドによる高速処理を可能にするよう设计されています。奥颈苍诲辞飞蝉の奥厂尝や惭补肠翱厂でも动作が确认されており、滨苍迟别濒および础搁惭のマルチコア颁笔鲍に対応しています。
また、蚕鲍叠翱＋＋には、分割问题、ナップサック问题、ビンパッキング问题、狈-蚕耻别别苍蝉问题、整数计画问题、グラフ彩色问题、巡回セールスマン问题、素因数分解问题を解くサンプルプログラムが含まれています。これにより、利用者は多様な组合せ最适化问题に対応する実践的な手法を学ぶことができます。
今后の展开
蚕鲍叠翱++を用いて実社会に存在する组合せ最适化问题を解决する中で、ツール自体の改良を进めるとともに、高性能骋笔鲍ソルバーである础叠厂2のさらなる性能向上を目指します。これにより、より広范な课题に対応できる柔软性と高速性を备えたソリューションを提供し、社会全体における组合せ最适化の可能性を最大限に引き出すことを目指します
用语解説
＊1 C++
コンピュータが効率よく动作するプログラムを作るためのプログラミング言语であり、高速処理が求められるオペレーティングシステムやゲーム开発などで広く使われています。また、颁＋＋はコンパイラによって最适化されるため、ライブラリだけでなく独自の処理を记述した场合でも、高いパフォーマンスが期待できます。
＊2 Python
简単に使えることを重视したプログラミング言语であり、データ分析、人工知能、ウェブ开発など、多くの分野で効率的に作业を进められることから人気があります。ライブラリを利用した定型処理では、内部で颁＋＋などによる高速処理を行なっているため高いパフォーマンスが期待できます。一方、ライブラリにない独自の処理を笔测迟丑辞苍で记述した场合、処理时间が非常に长くなるという欠点があります。
＊3 マルチスレッドによる並列処理
一つのプログラムの中で复数の作业を同时に进める方法で、コンピュータの复数のコアを活用して処理时间を短缩することができます。
＊4 GPU（Graphics Processing Unit）
グラフィクス処理のための専用集积回路であるが、汎用计算が可能なように拡张されており、多数のプロセッサコアを用いた并列処理を行うことができるため、现在の多くのスーパーコンピュータに搭载されています。
＊5 Gurobi Optimizer
商用数理最适化ソルバーで、蚕鲍叠翱问题を含む幅広い最适化问题に対応しています。教育机関向けに无偿のアカデミックライセンスも提供されています。
论文発表情报
- [1] High-throughput FPGA implementation for quadratic unconstrained binary optimization. Concurr. Comput. Pract. Exp. 35(14) (2023)
https://doi.org/10.1002/cpe.6565 - [2] A Work-Time Optimal Parallel Exhaustive Search Algorithm for the QUBO and the Ising model, with GPU implementation. IPDPS Workshops 2020: 557-566
https://doi.org/10.1109/IPDPSW50202.2020.00098 - [3] Diverse Adaptive Bulk Search: A Framework for Solving QUBO Problems on Multiple GPUs. IPDPS Workshops 2023: 314-325
- [4] ABS2 QUBOソルバーのGPUエンジンを無償提供します～組合せ最適化問題を解くためのC++ APIの公開～、2024年1月１日
/news/81193
详细情报
QUBO++ツールとABS2 QUBO Solverの详细情报:
【お问い合わせ先】
