[ICML 2024] Solving Combinatorial Optimization with the Diffusion Model

As one of the premier academic conferences in the field of machine learning, the International Conference on Machine Learning (ICML) annually hosts events at the forefront of AI and data science research. This year’s ICML 2024, held in Vienna, Austria, brought together researchers from a wide range of fields to share the latest research directions. At ICML 2024, LG AI Research’s Data Intelligence (DI) Lab presented a paper, “CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL fine-tuning,” which combines reinforcement learning with a diffusion model, a type of generative model that has recently gained attention, to solve combinatorial optimization problems, and discussed combinatorial optimization algorithms using AI technology with researchers.

This post will provide a brief introduction to how LG AI Research views real-world problems as combinatorial optimization problems, and introduce three combinatorial optimization studies using diffusion models.

1. Sun et al. Difusco: Graph-based diffusion solvers for combinatorial optimization. NeurIPS 2023. 2. Yoon et al. CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL fine-tuning. ICML Workshop 24 (2nd SPIGM). 3. Sanokowski et al. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.

What Is Combinatorial Optimization?

Combinatorial optimization is a branch of optimization that refers to the field of finding a solution that satisfies an objective value from a finite set of candidate discrete solutions. Consider one of the most famous combinatorial optimization problems, the “traveling salesman problem.”^[4] Given a set of cities that the traveling salesman must visit, the traveling salesman problem is to determine the order in which to visit the cities so that the total distance traveled is minimized, with each city being visited exactly once. In this case, the objective value of the traveling salesman problem is the total distance traveled between cities.

Image 1 . Example of the traveling salesman problem^[5]

Combinatorial Optimization Problems in Industry

Many problems in industry can be viewed as combinatorial optimization. Examples include logistics services, flight scheduling at airports, and the recently popular fields of genetic analysis and systems biology. The printed circuit board (PCB) design automation challenge that LG AI Research is currently working on can also be viewed as a type of combinatorial optimization problem.

A printed circuit board is the core component of electronic devices, and in the image below, you can see the golden pins connected to each other by light green wires.

Image 2. Example of a printed circuit board (PCB)^[6]

The goal of LG AI Research’s PCB automated wiring task is to wire these components so that their wiring does not overlap. When viewed as a combinatorial optimization problem, it is converted to the following Rectilinear Steiner Tree Packing Problem (RSTPP). In the figure below, we need to find the optimal solution with the lowest total wire length, which is the objective value, among the various wires that connect the same-colored components without conflicting with each other.

Image 3. PCB instance and solution converted to RSTPP format^[7]

How to Solve Combinatorial Optimization Problems

So how do we find the optimal solution to these combinatorial optimization problems? In the case of the traveling salesman problem, the most intuitive and easiest way is to calculate the length of the visit for each of the “n!” sequences of visits to each city, which is the number of all possible ways to visit when there are “n” cities and choose the shortest solution. This method is called a brute force algorithm, and while it is simple and can yield the most accurate solution, it has the disadvantage that the number of combinations needed to be calculated grows exponentially as the number of cities grows.

Unfortunately, the traveling salesman problem is NP-hard, which is theoretically proven to be impossible to calculate an accurate solution for within a reasonable amount of time^[12]. Most of the combinatorial optimization problems mentioned above are also NP-hard, so when solving combinatorial optimization problems with large “n,” there are many different approaches that try to solve an approximation that is as close to the correct answer as possible, even if it is not the correct answer, in the shortest possible time.

Algorithms for obtaining approximate solutions of combinatorial optimization can be broadly classified into two types:

1. Heuristic algorithm: A human-designed method that takes into account the characteristics of the problem. It is still a mainstream method as it has the advantage of providing good solutions to many combinatorial optimization problems in a short period of time. However, this heuristic-based method requires a long time to create an algorithm for each combinatorial optimization problem, and the more complex the combinatorial optimization problem, the more difficult the algorithm design.

2. Utilizing an artificial neural network: A method that learns the pattern of a given combinatorial optimization problem and provides an appropriate optimal solution. This method is divided into supervised learning (SL), which is based on collecting data on optimization problem solutions in advance and learning similarly, and reinforcement learning (RL), which selects multiple solutions on its own and evolves to select the solution that produces a better objective value.

Pathfinder: Automatic PCB Wiring

LG AI Research is currently developing a heuristic algorithm called Pathfinder++, which is an improvement of an existing network-related algorithm, Pathfinder^[14], to effectively solve the Rectilinear Steiner Tree Packing Problem (RSTPP) problem, to perform automatic PCB wiring. This algorithm has the following characteristics:

1. Constraint Handling: If each wire violates a constraint, it penalizes that area.

2. Iterative Improvement: Rewiring is done to avoid the penalized areas, and the process is repeated to finally obtain a wiring result that satisfies all constraints.

3. Reflecting Industrial Requirements: It is designed to take into account the requirements of different affiliates, such as maintaining spacing between PCB wiring, the distances between component pads and wiring, and controlling the number of vertical vias (holes for electrical connections) between PCB layers.

Image 4. Example of Pathfinder++ heuristic algorithm in action

Pathfinder++ has been validated against several real-world products from LG affiliates, and it was found that, for the majority of these products, it is possible to wire them to meet key requirements. However, there are still areas for further improvement, including the following:

1. Handling Fine-Grained Requirements: Different affiliates and products have very different PCB constraints. While Pathfinder++ currently does a good job of satisfying the essential requirements, it is inefficient and expensive to redesign the algorithm each time to satisfy dozens to hundreds of detailed requirements.

2. Reflecting Qualitative Considerations: In actual industrial PCB design, there are various recommendations that are difficult to clearly articulate quantitatively. While engineers reflect these qualitative factors empirically, it is relatively difficult to incorporate them into algorithms.

To address these issues, LG AI Research is expanding our research to improve Pathfinder++ in the following ways.

1. Human Data-Driven Learning: By learning from real PCB wiring data designed by existing LG affiliate engineers to produce results that resemble real-world designs, not just satisfy constraints.

2. Utilizing Generative Models: Utilizing diffusion models, which have recently shown strong performance in many fields, allows artificial neural networks to naturally learn from existing PCB wiring data. This is expected to capture complex patterns and implicit design rules.

With this approach, we expect to develop a more flexible and effective PCB automated wiring system. It is expected to be able to handle a variety of requirements and efficiently reflect the experiential knowledge of engineers.

Study of Combinatorial Optimization Using Diffusion Models

Diffusion models^[13], a type of generative model, were originally proposed to solve problems in the image field. For a detailed explanation of the structure of diffusion models, please refer to another post by LG AI Research, [NeurIPS 2021] Part 1: Generative model - Diffusion model Review^[15]. In recent years, diffusion models have been used in combinatorial optimization to generate good approximations that fit the problem well when given a problem. Here, three related papers will be introduced.

Image 5. Comparison of the image generation example of the diffusion model^[16] and the combinatorial optimization solution generation. 
This image is fictitious and does not represent the real world
.

1. Difusco: Graph-based Diffusion Solvers for Combinatorial Optimization^[1]

Difusco is a paper that proposed a method for solving combinatorial optimization using diffusion models, utilizing a method for learning diffusion models of images. For a given combinatorial optimization problem, multiple optimal solutions for different instances are generated in advance. Afterward, through forward and backward denoising processes commonly used in diffusion models, the model learns to recover the optimal solution even from noisy inputs.

Therefore, if learning is done well, it can approximate the solution of a given combinatorial optimization problem through a denoising process as shown in the figure below. In addition, as shown in the figure, as the target of noise is basically expressed in the form of a graph in the combinatorial optimization problem, an Anisotropic Graph Neural Network^[10], a type of Graph Neural Network that can handle data in the form of a graph structure well, is used. This differs from existing studies that utilize a U-net structure based on Convolutional Neural Networks, which are better at handling image data.

Image 6. Comparison of diffusion processes in image and combinatorial optimization

2. CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL Fine-tuning^[2]

DIFUSCO^[1] utilizes a diffusion model and has shown good performance for large-scale combinatorial optimizations, but it has some limitations. First of all, in combinatorial optimization, the standard for a solution to be good or bad is not simply how similar it is to the optimal solution, but how good the objective value of the actual solution is.

Image 7. Comparison of two solutions to the traveling salesman problem

In the example above, both solutions A and B select two wrong edges when compared to the optimal solution, but the actual objective value is better for B. Therefore, to find good approximations in combinatorial optimization, it is necessary to refine the diffusion model to generate solutions with the best possible objective value during the generation process, rather than merely producing solutions similar to the learned optimal solution.

In our study, we fine-tuned the trained diffusion model using reinforcement learning. In this process, we provided larger rewards for solutions with better objective values, enabling the trained generative model to produce solutions with improved objective values. This technique is widely used in other generative models, such as the famous Chat GPT and image generation models.

Image 8. CADO framework for RL fine-tuning of the learned diffusion model

We define the Markov Decision Process (MDP) for fine-tuning the diffusion model with reinforcement learning, as shown in the figure below, and utilize the REINFORCE^[11] algorithm for learning.

Image 9. Re-defining the diffusion process as a Markov Decision Process (MDP)

The difference between DIFUSCO and CADO can be made clearer by looking at the formulas in the following figure. DIFUSCO’s learning function, represented by the SL objective in light green, does not consider the objective value during the learning process; it simply tries to resemble the actual optimal solution. In contrast, CADO’s objective is designed to improve the objective value of the generated solution.

Image10 . Comparison of the Supervised Objective (DIFUSCO) and Reinforcement Learning Objective (CADO)

Finally, we found that the fine-tuned CADO, which takes objective values into account, improved by 20% to 70% in performance evaluation metrics for combinatorial optimization compared to the original DIFUSCO.

3. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization^[3]

A common limitation of DIFSUCO^[1] and CADO^[2] is that they initially require data consisting of sufficient optimal solutions for the diffusion model to learn to be prepared in advance. Preparing such a dataset of sufficient size can be expensive or even impossible if the combinatorial optimization problem is large or difficult. Of course, it is possible to have a diffusion model learn without training data using the reinforcement learning technique proposed by CADO. However, directly applying reinforcement learning to large and complex combinatorial optimization problems without any training data generally results in lower efficiency and instability. To use an analogy, it is like trying to teach elementary school students the theory of relativity without providing them with the necessary basic knowledge.

This paper addresses this difficulty by utilizing the following ideas. First, we define the following Boltzmann distribution over the possible solution $x$ that can emerge from combinatorial optimization. This distribution is defined as $q_{\beta }\left(x\right)=\frac{e^{-\beta c\left(x\right)}}{Z} \mathrm{where} Z={\sum }_x{e}^{-\beta c\left(x\right)}$, in which $c\left(x\right)$is the objective value of solution $x$. $\beta$ is how skewed the distribution is.

For $\beta =0$, $q_{\beta }$ is a uniform distribution, and as ${\pi }_{\theta }$gets larger, the probability of a good objective value increases. In the extreme case of $\beta =\infty$, it will only generate the optimal solution. is learned so that ${\pi }_{\theta }$ is ${\pi }_{\theta }\approx q_{\beta }$, which is the distribution of solutions generated by the diffusion model. The loss function used is $KL\left({\pi }_{\theta }\right|\left|q_{\beta }\right)$, which is called Reverse KL divergence.

It is initially learned based on $\beta =1$, and then gradually increases the value of $\beta$ to learn a better-performing distribution. $\left(KL\right({\pi }_{\theta }\left|\right|q_1)\to KL({\pi }_{\theta }\left|\right|q_2)\to \dots \to KL({\pi }_{\theta }\left|\right|q_{100})\to \dots ).$ This process led to a complex diffusion model being learned reliably without any training data so that it could generate an appropriately difficult distribution, $q_{\beta }$ step by step, rather than $q_{\infty }$ which is harder to learn from scratch.

Conclusion

This post provided a brief introduction to combinatorial optimization problems that LG AI Research is working on and introduced various papers that use diffusion models to solve combinatorial optimization problems. Due to the NP-hard nature of combinatorial optimization, there are many different approaches available. Even when limited to methods using diffusion models, we observed that there are several different approaches, each with its own unique characteristics, strengths, and weaknesses. In particular, it was found that when using diffusion models for combinatorial optimization, it is important to properly consider the objective value, unlike in the image.

As mentioned earlier, the PCB wiring problem we are working on at LG AI Research is a very difficult problem with many more factors to consider than a general combinatorial optimization problem. Therefore, even with the best-performing diffusion models introduced, it is difficult to achieve a perfect PCB wiring that can replace commercial engineers right away. At LG AI Research, we are trying to improve performance step by step by combining the diffusion model with the rule-based heuristic algorithm that we have been working on.

In addition, rather than sticking to one approach to solve combinatorial optimization problems, we are considering various methods such as large language models and reinforcement learning, which have recently gained a lot of attention. In the future, we plan to continue to expand the scope of our research beyond PCB chip design and process optimization to combinatorial optimization in various industrial fields.

▶ICML 2024 Review Series : Tabular Learning Research Trends