Reproduce “ReDUCE: Reformulation of Mixed Integer Programs using Data from Unsupervised Clusters for Learning Efficient Strategies” on OpenResearch

About this paper

Xuan Lin, Gabriel I. Fernandez, Dennis W. Hong

ReDUCE from UCLA's Robotics and Mechanisms Laboratory accelerates the solution of Mixed Integer Nonlinear Programs (MINLPs) and Mixed Integer Convex Programs (MICPs) by combining unsupervised clustering with problem reformulation. This approach enables the efficient generation of training data for supervised learning models, reducing solution times for a complex robotic task from over 851 seconds to an average of 1.21 seconds with 99.2% feasibility.

Key insights

• Optimal solutions to complex MINLPs and MICPs often exhibit inherent structure, clustering into distinct modes or regions in the solution space.
• Exploiting these solution clusters allows for dynamic problem reformulation, where the number of integer variables can be drastically reduced for specific operational modes, accelerating solution times.
• Combining unsupervised learning for efficient data generation with supervised learning for real-time strategy prediction offers a scalable pipeline to make otherwise intractable optimization problems solvable in real-time.

Summary by alphaXiv.