ReDUCE: Reformulation of Mixed Integer Programs using Data from Unsupervised Clusters for Learning Efficient Strategies
This work addresses the data efficiency problem for hybrid learning-solver methods in optimization, enabling faster solutions for practical problems like robotic planning, though it appears incremental as it builds on existing algorithms.
The paper tackles the challenge of long solving times for mixed integer convex and nonlinear programs (MICP/MINLP) by proposing ReDUCE, a method that exploits structure in small to medium datasets to improve solver efficiency, resulting in solving the bookshelf organization problem within a few seconds, a significant improvement over the original formulation.
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.