Topic Title: Learning to optimize: solving combinatorial optimization problems using machine learning
Combinatorial optimization has wide and important applications such as social networks, telecommunication networks, transportation, air fleet assignment, etc.
Most of combinatorial optimization problems are NP-hard, thus it is computationally intractable to achieve the optimality for large-scale problems. The popular branch-and-bound framework is not sufficient for solving large scale combinatorial optimization problems. Heuristics such as local search are commonly used. However, the design of heuristics and approximate algorithms requires strong domain knowledge. It is hard to apply those hand-crafted heuristics to generic combinatorial optimization problems. In real world applications, one of common scenarios is that the same type of combinatorial optimization problems need to be solved many times, which share a similar structure and only have the difference in data. Based on this observation, it is possible to utilize machine learning techniques to learn and solve the combinatorial optimization problems directly.
This project aims to build a learning framework to solve general combinatorial optimization problems. For instance, machine learning techniques such as reinforcement learning and graph embedding can be used to automatically learn the heuristics suitable for the structure of problems, policies of problem reduction, or policies of problem decomposition.
Related Research Topics:
Some related research topics are listed as follows:
- Representation learning: employ deep learning and embedding techniques to extract the underlying structure information of optimization problems and build representation learning model based on the historical data.
- Learning to optimize: use machine learning techniques such as reinforcement learning and graph embedding to automatically learn the heuristics suitable for the structure of problems, policies of problem reduction, policies of problem decomposition, etc.
- Parallel computing: parallel and distributed computing for learning to optimize.