Neural Network Architecture for Solving Geometric Optimization Problems
Combinatorial optimization problems arise naturally in many areas of computer science and other disciplines, such as business analytics, operations research, bioinformatics and electronic commerce. Since many of these optimization problems are NP-hard, applications typically rely on meta-heuristic frameworks, approximation algorithms and carefully designed heuristics for specific instance classes to solve them efficiently. However, the resultant solutions can be very far from optimal, and the development of good algorithms often requires significant human effort. The goal of this PhD project is to augment the human ability to design good algorithms and data structures by using machine learning techniques to explore the search space efficiently.
Over the last two decades, a large number of neural network architectures have been proposed to deal with a range of NLP and image processing tasks. However, these architectures (e.g., CNN) heavily rely on temporal and/or spatial coherence in the input sequence. In recent years, researchers have attempted to adapt these frameworks for solving combinatorial optimization problems with limited success. The combinatorial optimization problems often have long-ranged and complex correlations in the input element sequence. Therefore, the traditional architectures do not generalize as well as they do for the NLP and image processing tasks. In this project, we plan to consider restricted domains of combinatorial optimization problems (e.g., geometric optimization problems) and design neural network architectures that can learn efficient features for problems from the domain and leverage those features to find good solutions for large instances of the problems.