arXiv:2412.13858

IDEQ: an improved diffusion model for the TSP

Mickael Basson, Philippe Preux

제출 2024-12-18

원문 초록

We investigate diffusion models to solve the Traveling Salesman Problem. Building on the recent DIFUSCO and T2TCO approaches, we propose IDEQ. IDEQ improves the quality of the solutions by leveraging the constrained structure of the state space of the TSP. Another key component of IDEQ consists in replacing the last stages of DIFUSCO curriculum learning by considering a uniform distribution over the Hamiltonian tours whose orbits by the 2-opt operator converge to the optimal solution as the training objective. Our experiments show that IDEQ improves the state of the art for such neural network based techniques on synthetic instances. More importantly, our experiments show that IDEQ performs very well on the instances of the TSPlib, a reference benchmark in the TSP community: it closely matches the performance of the best heuristics, LKH3, being even able to obtain better solutions than LKH3 on 2 instances of the TSPlib defined on 1577 and 3795 cities. IDEQ obtains 0.3% optimality gap on TSP instances made of 500 cities, and 0.5% on TSP instances with 1000 cities. This sets a new SOTA for neural based methods solving the TSP. Moreover, IDEQ exhibits a lower variance and better scales-up with the number of cities with regards to DIFUSCO and T2TCO.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2505.01353v3math.OC공통 태그 model공식 코드 · Papers with Code

미분 가능한 비선형 모델 예측 제어

Differentiable Nonlinear Model Predictive Control

매개변수적 해 민감도의 효율적인 계산은 학습 강화 방법을 비선형 모델 예측 제어와 통합하는 데 있어 핵심 과제이며, 이는 많은 학습 알고리즘에서 민감도의 가용성이 필수적이기 때문이다. 본 논문은 음함수 정리와 내점법(IPM)에서 다루는 평활화된 최적성 조건을 이용하여 일반 비선형 계획법의 해 민감도를 계산하는 방법을 논한다. 장벽 매개변수가 지정된 비음수 목표값에 접근하도록 허용하여 SQP와 IPM 이차계획법(QP) 풀이기를 일반화하고, 이 목표값이 0일 때 고전적 SQP를 복원하는 순차 장벽 이차계획법(sequential barrier quadratic programming, SBQP)을 도입한다. 기존 연구는 볼록 또는 제약 없는 정식화에 한정되거나 효율적인 민감도 평가를 위한 구현이 부족하다. 본 발표는 `acados` 프레임워크 내의 효율적인 오픈소스 구현을 동반하며, 일반 최적 제어 문제에 대해 순방향 및 수반(adjoint) 민감도를 모두 제공하고 최신 풀이기인 `mpc.pytorch` 및 `cvxpygen` 대비 3배를 넘는 속도 향상을 달성한다.

arXiv:2507.10539공통 태그 model공식 코드 · Papers with Code

Graph World Model

토론

이 논문과 연결된 포럼 글이 아직 없습니다.