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 ProblemMany 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)
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.
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.
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.
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.
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.
Monitoring source codes and references simultaneously with dual displays.
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.
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.
Research activities in AL-lab are divided mainly into three groups: