Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912230247759872 |
|---|---|
| author | Hong, Seong-Hyun Kim, Hyun-Sung Jang, Zian Yoon, Deunsol Song, Hyungseok Lee, Byung-Jun |
| author_facet | Hong, Seong-Hyun Kim, Hyun-Sung Jang, Zian Yoon, Deunsol Song, Hyungseok Lee, Byung-Jun |
| contents | Recent advancements in neural combinatorial optimization (NCO) methods have shown promising results in generating near-optimal solutions without the need for expert-crafted heuristics. However, high performance of these approaches often rely on problem-specific human-expertise-based search after generating candidate solutions, limiting their applicability to commonly solved CO problems such as Traveling Salesman Problem (TSP). In this paper, we present IC/DC, an unsupervised CO framework that directly trains a diffusion model from scratch. We train our model in a self-supervised way to minimize the cost of the solution while adhering to the problem-specific constraints. IC/DC is specialized in addressing CO problems involving two distinct sets of items, and it does not need problem-specific search processes to generate valid solutions. IC/DC employs a novel architecture capable of capturing the intricate relationships between items, and thereby enabling effective optimization in challenging CO scenarios. IC/DC achieves state-of-the-art performance relative to existing NCO methods on the Parallel Machine Scheduling Problem (PMSP) and Asymmetric Traveling Salesman Problem (ATSP). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00003 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization Hong, Seong-Hyun Kim, Hyun-Sung Jang, Zian Yoon, Deunsol Song, Hyungseok Lee, Byung-Jun Artificial Intelligence Machine Learning Optimization and Control Recent advancements in neural combinatorial optimization (NCO) methods have shown promising results in generating near-optimal solutions without the need for expert-crafted heuristics. However, high performance of these approaches often rely on problem-specific human-expertise-based search after generating candidate solutions, limiting their applicability to commonly solved CO problems such as Traveling Salesman Problem (TSP). In this paper, we present IC/DC, an unsupervised CO framework that directly trains a diffusion model from scratch. We train our model in a self-supervised way to minimize the cost of the solution while adhering to the problem-specific constraints. IC/DC is specialized in addressing CO problems involving two distinct sets of items, and it does not need problem-specific search processes to generate valid solutions. IC/DC employs a novel architecture capable of capturing the intricate relationships between items, and thereby enabling effective optimization in challenging CO scenarios. IC/DC achieves state-of-the-art performance relative to existing NCO methods on the Parallel Machine Scheduling Problem (PMSP) and Asymmetric Traveling Salesman Problem (ATSP). |
| title | Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization |
| topic | Artificial Intelligence Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2411.00003 |