PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization

Federico Berto, Chuanbo Hua, Laurin Luttmann, Jiwoo Son, Junyoung Park, Kyuree Ahn, Changhyun Kwon, Lin Xie, Jinkyoo Park

KAIST· Omelet· Radical Numerics· Leuphana University· Brandenburg University of Technology· AI4CO

Multi-agent Combinatorial Optimization; Multi-agent Reinforcement Learning; Neural Combinatorial Optimization

⋅ NeurIPS ⋅ Project Page ⋅OpenReview

Abstract

Combinatorial optimization problems involving multiple agents are notoriously challenging due to their NP-hard nature and the necessity for effective agent coordination. Despite advancements in learning-based methods, existing approaches often face critical limitations, including suboptimal agent coordination, poor generalization, and high computational latency.

To address these issues, we propose PARCO (Parallel AutoRegressive Combinatorial Optimization), a general reinforcement learning framework designed to construct high-quality solutions for multi-agent combinatorial tasks efficiently. To this end, PARCO integrates three key novel components:

transformer-based communication layers to enable effective agent collaboration during parallel solution construction,
a multiple pointer mechanism for low-latency, parallel agent decision-making, and
priority-based conflict handlers to resolve decision conflicts via learned priorities.

We evaluate PARCO in multi-agent vehicle routing and scheduling problems, where our approach outperforms state-of-the-art learning methods, demonstrating strong generalization ability and remarkable computational efficiency. We make our source code publicly available to foster future research: https://github.com/ai4co/parco.