Presentation information

General Session

General Session » [GS] J-2 Machine learning

[1Q3-J-2] Machine learning: structural modeling

Tue. Jun 4, 2019 3:20 PM - 5:00 PM Room Q (6F Meeting room, Bandaijima bldg.)

Chair:Koh Takeuchi Reviewer:Akisato Kimura

4:20 PM - 4:40 PM

[1Q3-J-2-04] Learning to Find Hard Instances of Graph Problems

〇Ryoma Sato1, Makoto Yamada1,2,3, Hisashi Kashima1,2 (1. Kyoto University, 2. RIKEN Center for AIP, 3. JST PRESTO)

Keywords:hard instance, graph, algorithm, reinforcement learning

Finding hard instances, which needs a long time to solve, of graph problems is important for building a good benchmark for evaluating the performance of algorithms and analyzing algorithms to accelerate algorithms.
In this paper, We aim at automatically generating hard instances of graph problems. We formulate finding hard instances of graph problems as an optimization problem and propose a method to automatically find hard instances by solving the optimization problem. The advantage of the proposed algorithm is that it does not require any task-specific knowledge. To the best of our knowledge, it is the first non-trivial method in the literature to automatically find hard instances by using optimization.
Through experiments on various problems, we show that our proposed method can generate a few to several orders of magnitude harder instances than the random based approach in many settings, and especially our method outperforms rule-based algorithms in the 3-coloring problem.