CMU Artificial Intelligence Seminar Series sponsored by
Tuesday, Feb 22, 2022
Time: 12:00 - 01:00 PM ETGaurav Manek -- Hough and Cover: 2D Bin Packing with Classic Computer Vision Techniques
Relevant Paper(s): N/A
Abstract:
Classic computer vision has, unfortunately, fallen by the wayside in favor of neural networks. In this talk I introduce a novel use-case for some such techniques, applying them to 2D bin-packing.
The 2D bin packing problem is a classic NP-hard optimization problem in which a number of rectangles need to be packed into a minimal number of larger rectangular bins. I present Hough and Cover, a technique that leverages transformations found in classic computer vision to greatly reduce the number of constraints of a novel integer linear programming (ILP) formulation. This approach is evaluated on classic datasets against a state-of-the-art ILP approach, where it achieves a speed-up of 5× in many cases.
This problem has many industrial applications such as wood or glass industries, sheet metal fabrication, and even in scheduling heterogeneous resources. Solving this optimization problem optimally is important since it can save money, human resources, and time.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
Bio: Gaurav Manek is a PhD student at Carnegie Mellon University, advised by Zico Kolter. Gaurav's research centers around novel ways to learn dynamics models and value functions for reinforcement learning and similar applications, and to understand the subtle mechanisms at work when these models fail. His interests stretch from theoretical contributions to industry-facing applications.