LG AI Research: Diffusion Model Research for Combinatorial Optimization Problems

At ICML 2024, a prestigious conference in the machine learning field, the Data Intelligence (DI) Lab of LG AI Research introduced a new approach to solving combinatorial optimization problems.

The research team proposed CADO (Cost-Aware Diffusion Solvers), which combines reinforcement learning (RL) with the recently spotlighted generative model, the Diffusion Model. This model efficiently solves combinatorial optimization problems through cost-aware diffusion solvers.

Combinatorial Optimization is a field that finds the optimal solution satisfying a specific objective function within a finite set of candidates. A representative example is the Traveling Salesman Problem, which involves visiting all cities exactly once while minimizing the total distance traveled.

These problems are critical across industries such as logistics services, airport flight scheduling, and genome analysis. LG AI Research is currently carrying out a task to automate PCB (Printed Circuit Board) auto-routing design, converting it into a combinatorial optimization problem in the form of RSTPP (Rectilinear Steiner Tree Packing Problem) to solve it.

Existing brute-force methods have limitations as NP-hard problems, where computation increases exponentially as the number of cities grows. To overcome this, LG AI Research continues to explore the latest research leveraging diffusion models.