ReDUCE: 教師なしクラスタリングデータを用いた混合整数計画の再定式化による効率的戦略学習
ReDUCE: Reformulation of Mixed Integer Programs using Data from Unsupervised Clusters for Learning Efficient Strategies
小中規模データの構造を活用し混合整数計画問題を再定式化するReDUCEを提案し、ロボットアームの本棚整理問題で数秒での求解を実現した。
著者: Xuan Lin, Gabriel I. Fernandez, Dennis W. Hong
分類: cs.RO
原文アブストラクト
Mixed integer convex and nonlinear programs, MICP and MINLP, are expressive but require long solving times. Recent work that combines learning methods on solver heuristics has shown potential to overcome this issue allowing for applications on larger scale practical problems. Gathering sufficient training data to employ these methods still present a challenge since getting data from traditional solvers are slow and newer learning approaches still require large amounts of data. In order to scale up and make these hybrid learning approaches more manageable we propose ReDUCE, a method that exploits structure within small to medium size datasets. We also introduce the bookshelf organization problem as an MINLP as a way to measure performance of solvers with ReDUCE. Results show that existing algorithms with ReDUCE can solve this problem within a few seconds, a significant improvement over the original formulation. ReDUCE is demonstrated as a high level planner for a robotic arm for the bookshelf problem.
