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

 

Technical Area:

Operations Research

Optimization

Machine Learning

 

Background

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.

 

Target

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: