Topic Title: Learning to optimize: solving combinatorial optimization problems using machine learning


Technical Area:

Operations Research


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: