An Annealing-Inspired Gradient-Descent Based Suboptimal Solver for Combinatorial Problems
Part Of
APSIPA ASC 2024 - Asia Pacific Signal and Information Processing Association Annual Summit and Conference 2024
Start Page
1
End Page
6
ISBN
979-835036733-1
Date Issued
2024-12-03
Author(s)
Shu-Ping Chang
Cheng-Che Lee
Hsin-Jung Lee
Chieh-Hsiung Kuan
Jason Gemsun Young
Chia-Yu Yao
DOI
10.1109/APSIPAASC63619.2025.10849129
Abstract
Combinatorial optimization problems, such as IC layout and industrial scheduling, have significant industrial applications but are challenging due to exponential time complexity. In this work, we propose a novel annealing-inspired heuristic algorithm that treats combinatorial problems as function optimization problems using nonlinear programming. The proposed gradient-descent-based solver significantly improves the convergence rate and includes a new regularization constraint to escape local minima by increasing convexity. Applied to the Traveling Salesman Problem (TSP) with various city counts, the proposed algorithm demonstrates polynomial time complexity. It much reduces the complexity from (n−1)!/2 to n4 and has a marked improvement in computation efficiency. Notably, for a 50-city TSP, the relative error is just around 5%, indicating the accuracy and efficiency of the proposed algorithm in solving high-dimensional instances.
Event(s)
2024 Asia Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA ASC 2024
SDGs
Publisher
IEEE
Type
conference paper