Grid
Grid班ではグラフ問題などの組み合わせ最適化問題を解くための新たなアルゴリズムや高速化手法について研究開発を行っています。
今までに知られている最適化手法の多くは数値最適化を対象としたものですが、
Grid班ではより計算が困難なグラフ問題などを解くための最新のアルゴリズムを改良・応用する手法について研究しています。
本研究室では、新たな近似解法の改良および考案、並列処理による高速化手法、現実世界での応用を考慮した問題への適用、
そして深層学習を用いた新たな解法などが主なテーマとなっています。
●最適化問題
●研究例
●研究環境
The Grid group researches latest optimization techniques and develops algorithm for solving an discrete optimization problem faster and better.
The Grid group is studying method that can deal with a combinatorial optimization problem
(e.g. graph theory problem) by improving or applying latest algorithm.
Presently, we have several main themes : speeding up with massively parallel computing,
extending an algorithm considering to apply in real world, and developing a new method using deep learning.
●Optimization Problem
●Research Examples
●Development Environment
最適化問題
最適化問題
Optimization Problem
最適化問題の中にはNP困難という分類があり、これらの問題では実用的な時間で最適解を計算することが困難となっています。
そこで、Grid班では最適解になるべく近い解を高速に見つける近似解法（ヒューリスティクス）の研究開発を行っています。
●Traveling Salesman Problem (TSP)
TSPは巡回セールスマン問題とも呼ばれ、与えられたすべての頂点を1度だけ通るような経路のうち、総距離が最も短いものを求めるという問題です。
荷物の配送計画などへの応用例が考えられています。
頂点数が増えるにつれて最適解を求めることが非常に困難になるという性質を持ち、組合せ最適化問題の代表例として知られています。
Many of optimization problems are belong to NP-hard class and difficult to find a exact solution in a practical time.
So we are trying to develop a new heuristic algorithm which can find the approximate solution in more shorter time.
●Traveling Salesman Problem (TSP)
The Travelling Salesman Problem (TSP) is a classic algorithmic problem :
"find the shortest path visiting all given vertices only once".
This problem is expected to be applied in the delivery planning (as vehicle routing problem) for example.
●Integer Programming (IP)
IPは整数計画法とも呼ばれ、与えられた条件式を満たすような整数の組を求める問題です。
IPはLinear Programming (LP)と同様に目的関数と制約条件が線形不等式・等式によって定義されますが、
LPでは解空間が連続であるのに対して、IPは離散空間として与えられます。
これにより、LPでは多項式時間で解くことができるアルゴリズムが存在するのに対して、IPでは見つかっていません。
●Integer Programming (IP)
Integer Programming (IP) is a problem belongs to the field of mathematical optimization :
"find a solution that maximize/minimize a objective function in the discrete solution space".
As same as Linear Programming (LP), IP is defined with objective functions and equations/inequalities as constraints,
but the solution space is discrete.
And no algorithms that can solve this problem in polynomial time have been found yet.
研究例
研究例
Research Examples
●ハイブリッドアルゴリズム
複数のアルゴリズム同士を組み合わせることで、互いの短所を長所で打ち消し合うという手法です。
例えば「良い解を見つけることができるが、膨大な計算時間がかかる」アルゴリズムと
「ある程度良い解を短時間で見つける」アルゴリズムがあったとき、
後者の手法で「ある程度良い解」を高速に求め、この解を前者の手法に与えることで「良い解」を見つける、
といった方法で計算時間と解の品質を両立することができます。
●Hybrid Algorithm
A hybrid algorithm is a combination method of two or more algorithms.
For example, one algorithm can find a very good solution by taking long time,
and another algorithm can find a slightly nice solution in short time. Then we can combine them such that first of all,
the solution is found at high speed by the latter algorithm, and this solution is input to former algorithm to find better one,
and make it faster and better.。
etc...
●超並列アルゴリズム
複数のタスクを一つのコア(CPU)で計算するのではなく、複数のコアでタスクを分配して処理することで計算を高速化することができます。
しかし、メニーコアなど大量のコアを持つ環境では、効率よくコアにタスクを分配することが難しくなります。
そこで、待機状態のコアがなるべく発生しないような手法など、コア数を増やしても効率が落ちにくい並列アルゴリズムの開発を行っています。
●Massively Parallel Computing
We can perform a job more faster by using parallel computing, that is distributing tasks to multiple cores.
However, Massively Parallel Computing using many cores is difficult to distribute tasks to cores effectively.
So we are trying to develop an efficient algorithm,
such as a method that makes a core idle as little as possible when increase number of cores.
etc...
●深層学習を用いた解法
近年、囲碁などのゲームAIやデータマイニング、画像処理など、さまざまな分野において深層学習を用いた技術が研究されています。
大量の学習データを用いてデータの特徴量を抽出し、人間のように複雑な判断能力を獲得できるということが深層学習の大きな特徴です。
これらの深層学習の能力を組合せ最適化問題に適用することで、高精度で高速なアルゴリズムの構築を目指しています。
●Solving with Deep Learning
Recently, deep learning shows its highly performance in various fields : image processing, natural language processing,
data mining and game AI. Using deep learning can extract features from enormous datas and obtain complex discrimination ability
which is comparable to humans.
Our group is trying to apply deep learning to combinatorial optimization problem and create a new algorithm that can find a good solution.
etc...
研究環境
研究環境
Development Environment
●Intel Core-i CPUシリーズ＋デスクトップ付きLinux（Ubuntu、Fedora、CentOS、etc...）
最新のプロセッサファミリ搭載PCをデスクトップ環境として利用します。
グラフィカルな統合開発環境(IDE)をパワフルなPC上で動作させることで開発効率を向上させます。
●Intel Core-i CPU Series ＋ Desktop with Linux(Ubuntu、Fedora、CentOS、etc...)
Improving the development efficiency
by using the latest processors based PCs and by operating the graphical integrated development environment (IDE) on powerful PC.
●マルチディスプレイ
ライブラリリファレンスなどの資料を見ながら開発を進めたり、その他の雑務を効率よく進めるために一台のPCで複数のディスプレイを利用することが可能です。
●Multi-Display
Monitoring source codes and references simultaneously with dual displays.
●統合開発環境(IDE)＋言語
研究においてはプログラムやアプリケーションを作成するために様々なプログラミング言語を使用しており、その開発の際には統合開発環境（IDE）を利用します。
例えば、C++ならQt Creator、JavaならEclipse、PythonならPyCharmなどを利用しています。
●Integrated Development Environment (IDE) and Programming Languages
An integrated development environment (IDE) is a software application that provides comprehensive facilities to computer programmers
for software development. It makes use of various integrated development environment in order to use different languages.
For example, we use Qt Creator for C++, Eclipse for Java, PyCharm for Python, etc.
●コプロセッサ
超並列アルゴリズムを支えるインフラストラクチャとして、Grid班ではXeon Phiを利用します。
200を超えるスレッド、200-300GB/sクラスのメモリ帯域幅、1TFLOPSクラスの高い並列演算性能を利用することができます。
●Co-processor
Since the Infrastructure has able to support massively parallel algorithm, the Grid team is using the Xeon Phi co-processor.
It has performance of 1 Tera FLOPS, 200 over threads, and memory bandwidth with 200-300 GB/s.
Study
当研究室では、スタッフが３つのグループに別れて研究を行っています。
Research activities in AL-lab are divided mainly into three groups: